Convergence of an Arithmetic Mean Series

I found this problem on Mathstodon (can't remember exactly where though) and then saw that there was a source on Twitter, put up by James Tanton. So I saved it, and decided it to look at it over the weekend. It was a fun experience, and I solved it with help from Agilan. This post contains the solution in the general order of how I solved it.

Problem Statement

Given two initial numbers $a$ and $b,$ and a series $S$ defined as follows: $$S = \{a, b, s_1, s_2, s_3, \dots\}$$ where $s_n$ is the arithmetic mean of the previous two terms, prove that $S$ converges and find its limit $V.$

Initial Rules

Let a general term in the sequence $s_n$ be written as follows: $$s_n = \frac{i_{n}a + j_{n}b}{2^n},$$ where $i_n$ and $j_n$ are integers and coefficients of $a$ and $b$ respectively. The first rule we can deduce is that $i_n + j_n = 2^n.$ To highlight this, let us list out a few terms of the sequence: $$S = \Big\{\frac{a+b}{2}, \frac{a+3b}{4}, \frac{3a+5b}{8}, \frac{5a+11b}{16}, \frac{11a+21b}{32}, \frac{21a+43b}{64}, \frac{43a+85b}{128}, \dots\Big\}.$$ Secondly, we also notice that $i_{n+1}=j_n.$ Put these two together and we get our first important rule, $$i_{n+1} = 2^n - i_n.$$

Solution for $i_n$

Until here, our job was straightforward. We just needed to eliminate $i_n$ from the equation by finding a closed form representation for it. Again, looking at the sequence gave us the idea. $i_n$ was changing in a very predictable manner with each term. For odd terms, the next coefficient was double the previous one but with $1$ subtracted, and for even terms, the next coefficient was double the previous one with an additional $1$ added to it. This gave us second rule: $$i_{n+1} = 2i_n + (-1)^n.$$

These two can be put together to eliminate $i_n$ and get a closed form representation. Subtracting the second rule from the first, we get: $$ \begin{aligned} 0 &= 2^n - 3i_n - (-1)^n \\ i_n &= \frac{2^n - (-1)^n}{3} \\ \end{aligned} $$

Solving Limits

Now that we have a closed form representation for $i_n,$ we can plug it back in the original equation for $s_n$ and solve for the limit. We get: $$s_n = \frac{\Big[\frac{2^n - (-1)^n}{3}\Big]a+\Big[2^n-\frac{2^n - (-1)^n}{3}\Big]b}{2^n}.$$ Our objective now is to prove that $\displaystyle\lim_{n\rightarrow\infty} s_n$ converges to a final value $V$ and then, find $V.$

The limits are easy to solve, we just need the constants that are multiplied with the $2^n$ terms in each case, because all non-exponentials will go to $0$ as $n$ approaches infinity. We get: $$\displaystyle\lim_{n\rightarrow\infty} \frac{2^n - (-1)^n}{3\times 2^n} = \frac{1}{3},$$ and similarly, $$\displaystyle\lim_{n\rightarrow\infty} \frac{2^n - \frac{2^n - (-1)^n}{3}}{2^n} = \frac{2}{3}.$$ So, $$\displaystyle\lim_{n\rightarrow\infty} s_n = V = \frac{a+2b}{3}.$$

Visualizing Convergence

When we were stuck on the problem, we decided to visualize the sequence to see if we could find a pattern. We plotted a few terms of the sequence for different values of $a$ and $b$ and found that the sequence was converging to a single point. We also found that the sequence was converging faster for some values of $a$ and $b$ than others. The following code snippet shows how we plotted the sequence.

Denouement

Solving the problem didn't quite happen in this linear fashion, we got the first rule fairly quickly but the second rule eluded us for quite some time. I'll post the entirety of our thought process below, so you can see how we arrived at the solution. It is quite messy, but it was a lot of fun to work on.

There were some things that can be proven more concretely, like the first rule where we said that $i_{n+1}=j_n.$ But I didn't want to go into that much detail. I just wanted to solve the problem and move on. I'm sure there is a way to rigorously prove this rule. If you know how, please let me know in the comments below.

There are more elegant ways to solve this problem too. I found a solution in the Twitter comments that uses the fact that initializing with numbers in the same sequence gives the same limit and then solving two such equations for the two coefficients which will always turn out to be $1/3$ and $2/3.$