## Mean Sequence

#### Problem

A second order recurrence relation is defined by `u`_{n+1} = (`u`_{n}+`u`_{n1})/2; that is, each new term is the mean of the previous two terms.

For example, when `u`_{1}=2 and `u`_{2}=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, `u`_{k+1} will lie between the two previous terms, `u`_{k} and `u`_{k1}. 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 `u`_{1}, the terms follow the following series:

S = 1 1/2 + 1/4 1/8 + ...

2S = 2 1 + 1/2 1/4 + 1/8 ...

3S = 2 S = 2/3

That is, the sequence converges towards a value, L, which is 2/3 above the first term: L = `u`_{1}+2(`u`_{2}`u`_{1})/3 = (`u`_{1}+2`u`_{2})/3.

If `u`_{1} `u`_{2} then the sequence follows the series:

S = -1 + 1/2 1/4 + ...

2S = -2 + 1 1/2 + 1/4 ...

3S = -2 S = -2/3

And we get the same limit, L = `u`_{1}2(`u`_{1}`u`_{2})/3 = (`u`_{1}+`u`_{2})/3.

What about the third order recurrence relation: `u`_{n+1} = (`u`_{n}+`u`_{n1}+`u`_{n2})/3 ?

Investigate the `k` th order recurrence relation.