Proving a general rule which states where a recursive series converges

Question

The recursive formula is

$t_n=\frac {t_{n-1}+t_{n-2}}2$

Changing $t_1$ and $t_2$ changes the number where the sequence converges as $n \to \infty$. With the help of everyone at StackExchange, I found that the relationship between $t_1$ and $t_2$ and where the series converges is

$\frac{t_1+2t_2}{3}$

However, how do I prove that that equation describes the relationship between $t_1$ and $t_2$ and where the series converges?

The way I found the formula

sidenote: if someone could explain here the first equation in the picture I uploaded comes from it would be much appreciated.

Answer 1

Let $a=t_1,\ b=t_2,$ then you're trying to show that $t_n$ approaches $(a+2b)/3$ as $n \to \infty.$ Note that the recursion $t_n=(t_{n-1}+t_{n-2})/2$ continues to hold when $t_n$ is replaced everywhere by $t_n-c$ where $c$ is any constant independent of $n.$ [One is subtracting $c$ from the left side and $(c/2+c/2)$ from the right side.] In this suppose we use $c=(a+2b)/3.$

So now we are looking at $u_n=t_n-(a+2b)/3$ and hoping that $u_n$ approaches zero as $n$ goes to infinity.

Note that $u_1=2(a-b)/3$ and $u_2=(b-a)/3,$ so that we have the nice relation that $u_2=(-1/2)\cdot u_1.$ We can now show this continues to be so for higher index values $n.$ That is, we claim in general that $$u_{n+1}=(-1/2)\cdot u_n \tag{1}$$ This is shown by "induction" meaning we show if it holds for a pair $n,n+1$ then it holds for the next pair $n+1,n+2.$ Now since it holds for the first pair, we have $u_{n+1}=(-1/2)\cdot u_n.$ To get $u_{n+2}$ we average $u_n$ and $u_{n+1}$: $$u_{n+2}=\frac{u_n+u_{n+1}}{2}=\frac{u_n+(-1/2)u_n}{2} =\frac{u_n}{4}.$$ And now, since $u_{n+1}=(-1/2)\cdot u_n,$ we see that indeed $u_{n+2}=(-1/2)\cdot u_{n+1}$

A look at $(1)$ shows that $t_n \to 0$ as $n \to \infty$ since we are repeatedly changing sign and dividing by 2 to get the next one. And that as already noted shows the sequence of $t_k$ approaches $(a+2b)/3.$

Answer 2

There is a systematic theory for finding closed forms of such linear recurrences with constant coefficients (link). This order $d=2$ recurrence $$ t_n = (1/2) t_{n-1} + (1/2) t_{n-2} $$ has characteristic polynomial $$ p(t) = t^2 - (1/2) t - 1/2 $$ with roots $$ 0 = p(r) = (r - 1/4)^2 - 1/16 - 1/2 \iff \\ r = \frac{1 \pm 3}{4} \in \{ 1, -1/2 \} $$ which gives the general solution $$ t_n = k_1 1^n + k_2 (-1/2)^n = k_1 + k_2 (-1/2)^n $$ We need two values of $t_n$ to select the solution, e.g. $t_1$ and $t_2$: $$ t_1 = k_1 + k_2 (-1/2)^1 = k_1 - (1/2) k_2 \\ t_2 = k_1 + k_2 (-1/2)^2 = k_1 + (1/4) k_2 $$ adding two times the second to the first equation gives $$ t_1 + 2 t_2 = 3 k_1 \iff \\ k_1 = (1/3) t_1 + (2/3) t_2 $$ Subtracting the second from the first equation gives $$ t_1 - t_2=-(3/4) k_2 \iff \\ k_2 = (4/3)(t_2 - t_1) $$ So we find the closed form $$ t_n = (1/3) t_1 + (2/3) t_2 + (4/3)(t_2-t_1)(-1/2)^n $$ We can now go for the limit: $$ \lim_{n\to\infty} t_n = \lim_{n\to\infty} (1/3) t_1 + (2/3) t_2 + (4/3)(t_2-t_1)(-1/2)^n = (1/3) t_1 + (2/3) t_2 $$