mathschallenge.net logo

Mean Sequence

Problem

A second order recurrence relation is defined by un+1 = (un+unminus1)/2; that is, each new term is the mean of the previous two terms.

For example, when u1=2 and u2=5, we generate the following sequence:

2, 5, 3.5, 4.25, 3.875, ... .

Find the limit of the sequence for different starting values.


Solution

Consider the following diagram.


By the definition of the sequence, the next term, uk+1 will lie between the two previous terms, uk and ukminus1. Thus, as this process continues, each iteration will reduce the upper and lower bounds, demonstrating that the sequence converges towards a value.

Let the distance between the first and second term be defined as one unit, so that, from the first term u1, the terms follow the following series:

S = 1 minus 1/2 + 1/4 minus 1/8 + ...
2S = 2 minus 1 + 1/2 minus 1/4 + 1/8 minus ...
therefore 3S = 2 implies S = 2/3

That is, the sequence converges towards a value, L, which is 2/3 above the first term: L = u1+2(u2minusu1)/3 = (u1+2u2)/3.

If u1 greater than u2 then the sequence follows the series:

S = -1 + 1/2 minus 1/4 + ...
2S = -2 + 1 minus 1/2 + 1/4 minus ...
therefore 3S = -2 implies S = -2/3

And we get the same limit, L = u1minus2(u1minusu2)/3 = (u1+u2)/3.

What about the third order recurrence relation: un+1 = (un+unminus1+unminus2)/3 ?
Investigate the k th order recurrence relation.

Problem ID: 212 (06 Mar 2005)     Difficulty: 3 Star

Only Show Problem