Author |
Topic: A Mean Seqeunce (Read 431 times) |
|
Sir Col
Uberpuzzler
impudens simia et macrologus profundus fabulae
Gender: 
Posts: 1825
|
 |
A Mean Seqeunce
« on: Mar 5th, 2005, 5:53am » |
 Quote  Modify
|
The sequence 2, 5, 3.5, 4.25, ... is defined by the second order recurrence relation, un+1=(un+un-1)/2, where u1=2 and u2=5.
Investigate the nature of this sequence.
Generalise for difference starting values: u1 and u2?
|
| « Last Edit: Mar 5th, 2005, 8:46am by Sir Col » |
 IP Logged |
mathschallenge.net / projecteuler.net
|
|
|
Icarus
wu::riddles Moderator
Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863
|
|
Re: A Mean Seqeunce
« Reply #1 on: Mar 5th, 2005, 6:59am » |
Quote Modify
|
::un = (1/3)(2u2 + u1 + (-1/2)n-2(u2 - u1))::
|
| « Last Edit: Mar 5th, 2005, 7:08am by Icarus » |
IP Logged |
"Pi goes on and on and on ...
And e is just as cursed.
I wonder: Which is larger
When their digits are reversed? " - Anonymous
|
|
|
ThudnBlunder
wu::riddles Moderator
Uberpuzzler
The dewdrop slides into the shining Sea
Gender:
Posts: 4489
|
|
Re: A Mean Seqeunce
« Reply #2 on: Mar 5th, 2005, 7:24am » |
Quote Modify
|
Quote:| Investigate the nature of the nature of this sequence. |
|
Sorry, that's too deep for me.
:However, Maple gives un = [(u1 + 2u2 - (u1 - u2)(-1/2)n-2] / 3
As n tends to infinity, un tends to (u1 + 2u2) / 3
When u1 = 2, u2 = 5
un = 4 + (-1/2)n-2
|
| « Last Edit: Mar 5th, 2005, 12:39pm by ThudnBlunder » |
IP Logged |
THE MEEK SHALL INHERIT THE EARTH.....................................................................er, if that's all right with the rest of you.
|
|
|
Sir Col
Uberpuzzler
impudens simia et macrologus profundus fabulae
Gender:
Posts: 1825
|
|
Re: A Mean Seqeunce
« Reply #3 on: Mar 5th, 2005, 8:42am » |
Quote Modify
|
Nicely done!
on Mar 5th, 2005, 7:24am, THUDandBLUNDER wrote:| Sorry, that's too deep for me. |
|
Do you think that such an analysis of sequence is beyond "easy"? 
Trust you to spot that, T&B!. I've corrected it.
Interestingly, I gave this investigation to one of my classes of 12/13 year olds and they "solved" it. 
Actually they discovered and then proved the value which, given a pair of starting values, the sequence converges towards. Although your methods of deriving the nth term formula to determine the limit is entirely valid, do bear in mind that I put this in "easy". There is a much simpler approach...
|
| « Last Edit: Mar 5th, 2005, 8:48am by Sir Col » |
IP Logged |
mathschallenge.net / projecteuler.net
|
|
|
Icarus
wu::riddles Moderator
Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863
|
|
Re: A Mean Seqeunce
« Reply #4 on: Mar 5th, 2005, 7:40pm » |
Quote Modify
|
Actually, using Maple or some other tool seems overkill. I found my formula by hand in ~20 minutes, and would have taken less time if I hadn't made a simple error (failed to divide by 2) early on that I needed to trace back out.
Perhaps they would be useful in finding the higher order version: un is the mean of the previous k elements. While I am not particularly anxious to factor the order k polynomial to get the non-recursive formula for un, I am sure that the constant term in it (and limit as n -> infinity) will be 2(kuk + (k-1)uk-1 + ... 2u2 + u1)/k(k+1)
|
|
IP Logged |
"Pi goes on and on and on ...
And e is just as cursed.
I wonder: Which is larger
When their digits are reversed? " - Anonymous
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: A Mean Seqeunce
« Reply #5 on: Mar 6th, 2005, 1:50am » |
Quote Modify
|
Am I mistaken, or Icarus presented once or twice a general method of solving the linear recurrences?
|
|
IP Logged |
|
|
|
ThudnBlunder
wu::riddles Moderator
Uberpuzzler
The dewdrop slides into the shining Sea
Gender:
Posts: 4489
|
|
Re: A Mean Seqeunce
« Reply #6 on: Mar 6th, 2005, 3:43am » |
Quote Modify
|
on Mar 5th, 2005, 7:40pm, Icarus wrote:| Actually, using Maple or some other tool seems overkill. I found my formula by hand in ~20 minutes, and would have taken less time if I hadn't made a simple error (failed to divide by 2) early on that I needed to trace back out. |
|
The recurrence yields the characteristic equation
2x2 - x - 1 = 0
(2x + 1)(x - 1) = 0
Hence
un = A(-1/2)n + B
and
A = -4(u1 - u2) / 3
B = (u1 + 2u2) / 3
giving the required result. (Spending 20 minutes on the above simple, yet tedious, calculation is not the best way to demonstrate the futility of using Maple.)
on Mar 5th, 2005, 7:40pm, Icarus wrote:| While I am not particularly anxious to factor the order k polynomial to get the non-recursive formula for un |
|
If kun = un-1 + un-2 + ....... + un-k
we get characteristic equation
(x - 1)(1 + 2x + 3x2 +.......+ kxk-1) = 0
on Mar 5th, 2005, 7:40pm, Icarus wrote:
I am sure that the constant term in it (and limit as n -> infinity) will be 2(kuk + (k-1)uk-1 + ... 2u2 + u1)/k(k+1) |
|
How did you find this? FWIW, Maple agrees. 
|
| « Last Edit: Mar 6th, 2005, 8:16am by ThudnBlunder » |
IP Logged |
THE MEEK SHALL INHERIT THE EARTH.....................................................................er, if that's all right with the rest of you.
|
|
|
Eigenray
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 1948
|
|
Re: A Mean Seqeunce
« Reply #7 on: Mar 6th, 2005, 9:00am » |
Quote Modify
|
Consider an equivalent formulation. With pie.
There are two people, A and B, and one pie. A takes half the pie, and B takes half of what's left. A takes half of what's left now, and B does the same. This repeats. After each step, A has twice as much pie as B. In the limit, they have all the pie. Therefore A ends up with 2/3 pie.
|
|
IP Logged |
|
|
|
Icarus
wu::riddles Moderator
Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863
|
|
Re: A Mean Seqeunce
« Reply #8 on: Mar 6th, 2005, 12:29pm » |
Quote Modify
|
on Mar 6th, 2005, 3:43am, THUDandBLUNDER wrote:| Spending 20 minutes on the above simple, yet tedious, calculation is not the best way to demonstrate the futility of using Maple. |
|
True, though the 20 minutes was a guestimate, the calculation was done in unused bits and corners of some scrap paper I had lying in front of me, and the calculation took far longer than it should of because I missed a simple step.
Quote:| How did you find this? FWIW, Maple agrees. |
|
By reasoning similar to that used by Eigenray.
The first k elements are independent. The next k elements are dependent on these, and all remaining elements get their values from the second set of k elements. So the total effect of u1 to uk is determined by their effect on elements uk+1 to u2k. But looking at these, we see that u1 to uk are treated equally except that:
u1 is picked up by uk+1 only.
u2 is picked up twice: by uk+1 and by uk+2.
u3 is picked up 3 times: by uk+1, uk+2,uk+3
...
uk is picked up k times: by each of uk+1 to u2k
The value I gave is just the average of 1 copy of u1, 2 copies of u2, ..., k copies of uk.
And yes, it is nice to receive confirmation, because I arrived at the formula heuristically.
|
|
IP Logged |
"Pi goes on and on and on ...
And e is just as cursed.
I wonder: Which is larger
When their digits are reversed? " - Anonymous
|
|
|
Icarus
wu::riddles Moderator
Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863
|
|
Re: A Mean Seqeunce
« Reply #9 on: Mar 6th, 2005, 12:35pm » |
Quote Modify
|
on Mar 6th, 2005, 3:43am, THUDandBLUNDER wrote:| Spending 20 minutes on the above simple, yet tedious, calculation is not the best way to demonstrate the futility of using Maple. |
|
True, though the 20 minutes was a guestimate, the calculation was done in unused bits and corners of some scrap paper I had lying in front of me, and the calculation took far longer than it should of because I missed a simple step.
Quote:| How did you find this? FWIW, Maple agrees. |
|
By reasoning similar to that used by Eigenray.
The first k elements are independent. The next k elements are dependent on these, and all remaining elements get their values from the second set of k elements. So the total effect of u1 to uk is determined by their effect on elements uk+1 to u2k. But looking at these, we see that u1 to uk are treated equally except that:
u1 is picked up by uk+1 only.
u2 is picked up twice: by uk+1 and by uk+2.
u3 is picked up 3 times: by uk+1, uk+2,uk+3
...
uk is picked up k times: by each of uk+1 to u2k
The value I gave is just the average of 1 copy of u1, 2 copies of u2, ..., k copies of uk.
And yes, it is nice to receive confirmation, because I arrived at the formula heuristically.
------------------------------------
[e]Just realized I missed commenting on this: Finding the x=1 root of kxk - xk-1 - xk-2 - ... - 1 is easy. But you need to know all the roots before you can find the general term of the recursion, and I was not particularly anxious to hunt up the rest.
|
| « Last Edit: Mar 6th, 2005, 12:36pm by Icarus » |
IP Logged |
"Pi goes on and on and on ...
And e is just as cursed.
I wonder: Which is larger
When their digits are reversed? " - Anonymous
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print