wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> easy >> A Mean Seqeunce
        
(Message started by: Sir Col on Mar 5^th, 2005, 5:53am)

Title: A Mean Seqeunce
Post by Sir Col on Mar 5^th, 2005, 5:53am

The sequence 2, 5, 3.5, 4.25, ... is defined by the second order recurrence relation, u_n+1=(u_n+u_n-1)/2, where u₁=2 and u₂=5.

Investigate the nature of this sequence.
Generalise for difference starting values: u₁ and u₂?

Title: Re: A Mean Seqeunce
Post by Icarus on Mar 5^th, 2005, 6:59am

::u_n = (1/3)(2u₂ + u₁ + (-1/2)^n-2(u₂ - u₁))::

Title: Re: A Mean Seqeunce
Post by THUDandBLUNDER on Mar 5^th, 2005, 7:24am

Quote:

Investigate the nature of the nature of this sequence.

Sorry, that's too deep for me.

:However, Maple gives u_n = [(u₁ + 2u₂ - (u₁ - u₂)(-1/2)^n-2] / 3

As n tends to infinity, u_n tends to (u₁ + 2u₂) / 3
When u₁ = 2, u₂ = 5
u_n = 4 + (-1/2)^n-2

Title: Re: A Mean Seqeunce
Post by Sir Col on Mar 5^th, 2005, 8:42am

Nicely done!

on 03/05/05 at 07:24:00, THUDandBLUNDER wrote:

Sorry, that's too deep for me.

Do you think that such an analysis of sequence is beyond "easy"? ;D

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...

Title: Re: A Mean Seqeunce
Post by Icarus on Mar 5^th, 2005, 7:40pm

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: u_n 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 u_n, I am sure that the constant term in it (and limit as n -> infinity) will be 2(ku_k + (k-1)u_k-1 + ... 2u₂ + u₁)/k(k+1)

Title: Re: A Mean Seqeunce
Post by Barukh on Mar 6^th, 2005, 1:50am

Am I mistaken, or Icarus presented once or twice a general method of solving the linear recurrences?

Title: Re: A Mean Seqeunce
Post by THUDandBLUNDER on Mar 6^th, 2005, 3:43am

on 03/05/05 at 19:40:03, Icarus wrote:

The recurrence yields the characteristic equation
2x² - x - 1 = 0
(2x + 1)(x - 1) = 0
Hence
u_n = A(-1/2)ⁿ + B
and
A = -4(u₁ - u₂) / 3
B = (u₁ + 2u₂) / 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.)
:P

on 03/05/05 at 19:40:03, Icarus wrote:

While I am not particularly anxious to factor the order k polynomial to get the non-recursive formula for u_n

If ku_n = u_n-1 + u_n-2 + ....... + u_n-k
we get characteristic equation
(x - 1)(1 + 2x + 3x² +.......+ kx^k-1) = 0

on 03/05/05 at 19:40:03, Icarus wrote:

I am sure that the constant term in it (and limit as n -> infinity) will be 2(ku_k + (k-1)u_k-1 + ... 2u₂ + u₁)/k(k+1)

How did you find this? FWIW, Maple agrees. ::)

Title: Re: A Mean Seqeunce
Post by Eigenray on Mar 6^th, 2005, 9:00am

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.

Title: Re: A Mean Seqeunce
Post by Icarus on Mar 6^th, 2005, 12:29pm

on 03/06/05 at 03:43:12, 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 u₁ to u_k is determined by their effect on elements u_k+1 to u_2k. But looking at these, we see that u₁ to u_k are treated equally except that:
u₁ is picked up by u_k+1 only.
u₂ is picked up twice: by u_k+1 and by u_k+2.
u₃ is picked up 3 times: by u_k+1, u_k+2,u_k+3
...
u_k is picked up k times: by each of u_k+1 to u_2k

The value I gave is just the average of 1 copy of u₁, 2 copies of u₂, ..., k copies of u_k.

And yes, it is nice to receive confirmation, because I arrived at the formula heuristically.

Title: Re: A Mean Seqeunce
Post by Icarus on Mar 6^th, 2005, 12:35pm

on 03/06/05 at 03:43:12, THUDandBLUNDER wrote:

Spending 20 minutes on the above simple, yet tedious, calculation is not the best way to demonstrate the futility of using Maple.

How did you find this? FWIW, Maple agrees.