Challenge Level

Well done to Ken from Blessed Robert Johnson
Catholic School who sent us his solution to this problem:

After a while of playing with the numbers on a spreadsheet I
have discovered that the formula to find the "limiting value" for
$2$ starting numbers is: $$\frac{x+2y}{3}$$ where $x$ is the first
number chosen and $y$ is the second number chosen.

The formula to find the "limiting value" for 3 starting
numbers will be: $$\frac{x+2y+3z}{6}$$

Some older
students also worked on this problem. Terence from Brumby
Engineering College has made a prediction for what the limit will
be when there are $n$ starting numbers. He thinks it will be

$$\frac{a_1+2a_2+3a_3+4a_4+\ldots+(n-1)a_{n-1}+n
a_n}{\frac{1}{2}n(n+1)}$$ where $a_1$, $a_2$, $\ldots$, $a_{n-1}$
and $a_n$ are the $n$ starting numbers.

Can you see why Terence has made this
prediction?

As mathematicians, we like to
prove
our answers, rather than just predict. Here
is an outline of how we might prove the formula when there are two
starting numbers.

Suppose that the first two numbers are $a$ and $b$. Let's work
out the next few terms of the sequence. We have

$$a,\:b,\:\frac{a+b}{2},\:\frac{a+3b}{4},\:\frac{3a+5b}{8},\:
\frac{5a+11b}{16},\:\frac{11a+21b}{32},\:\frac{21a+43b}{64}$$ and
so on. We'd like to show that in the limit the coefficient of $b$
is twice the coefficient of $a$, and also that the sum of these
coefficients is the denominator. Can you see why this will prove
the formula?

The $n^{\textrm{th}}$ term in the sequence is of the form
$$\frac{ \alpha_n a+\beta_n b}{2^{n-2}}$$ (for $n\geq 2$). We can
work out $\alpha_n$ in terms of $\alpha_{n-1}$ and $\alpha_{n-2}$.
Can you see how?

We have $\alpha_n=\alpha_{n-1}+2\alpha_{n-2}$ (for $n\geq 4$).
Similarly, we have $\beta_n=\beta_{n-1}+2\beta_{n-2}$ (for $n\geq
4$).

It turns out that we can use these formulae to prove that
$\beta_n=2\alpha_n +(-1)^n$ (for $n\geq 2$). Test this formula on
the above examples to see that it works for these cases.

We'd like to show that as $n$ tends to infinity, $\beta_n$
becomes twice $\alpha_n$. Let's think about $\beta_n/\alpha_n$.
From the above formula, this is $2+(-1)^n/\alpha_n$. But $\alpha_n$
is getting bigger and bigger, so the $(-1)^n/\alpha_n$ part of this
gets smaller and smaller. In fact, it tends to $0$, and so the
limit of the whole expression is $2$.

It is also possible to use the formulae for $\alpha_n$ and
$\beta_n$ to show that $\alpha_n+\beta_n=2^{n-2}$ (for $n\geq 3$)
(that is, the coefficients of $a$ and $b$ sum to the number on the
bottom of the fraction). Again, test this formula on the examples
above.

Combining the last two paragraphs, we find that the limit of
the sequence is $$\frac{a+2b}{3}$$ as predicted.