# How to prove that the sequence defined by $a_1=0$, $a_2=1$, $a_n=\frac{a_{n-1}+a_{n-2}}{2}$ converges to $\frac23$?

How to prove that the sequence defined by $$a_1=0$$, $$a_2=1$$, $$a_n=\frac{a_{n-1}+a_{n-2}}{2}$$ converges to $$\frac23$$?

If we analyse terms: $$0,1,\frac{1}{2},\frac{3}{4},\frac{5}{8},\cdots.$$

I'm asked to do this using a previously proved theorem which says that

if you have two sequences $${b_n}$$ and $${c_n}$$ converging both to the same limit $$L$$, then the sequence $$a_n$$ defined as $$b_1,c_1,b_2,c_2,b_3,\dots$$ converge to $$L$$.

In this case, $$b_n$$ would be $$0,\cfrac{1}{2},\cfrac{5}{8},\cfrac{21}{32},\dots$$ and $$c_n$$ would be $$1,\cfrac{3}{4},\cfrac{11}{16},\cfrac{43}{64},\dots$$

From here it's seems all I need to do is prove that $$b_n$$ and $$c_n$$ converge to $$\cfrac{2}{3}$$ and then, by the theorem, $$a_n$$ converges to $$\cfrac{2}{3}$$.

I need to define them because I need to prove $$b_n$$ and $$c_n$$ are monotone and bounded, in order to use the monotone convergence theorem. I've got troubles when trying to define $$b_n$$ and $$c_n$$. Can anyone help me to define them?

• it seems you only have one choice. try to define $a_n$ in terms of $b_n$ and $c_n$ from the theorem. – The Count Nov 21 '18 at 2:53
• But i need to define $b_n$ and $c_n$ to prove each one is monotone and bounded, in order to use the monotone convergence theorem. – Tom Arbuckle Nov 21 '18 at 2:57
• i mean write the equation for a general $a_n$. – The Count Nov 21 '18 at 2:58
• If you read carefully, you will see that it´s a date they´re giving me. The title says it: $a_n=\frac{a_{n-1}+a_{n+2}}{2}$ – Tom Arbuckle Nov 21 '18 at 3:02
• A similar question here – rtybase Nov 21 '18 at 10:32

Here is an alternative (maybe easier) way.

By definition of the sequence one has \begin{align} a_1+a_2&=2a_3\\ a_2+a_3&=2a_4\\ &\vdots\\ a_{n-1}+a_{n}&=2a_{n+1} \end{align} Adding together these identities one gets $$a_{n+1}=1-\frac12 a_{n},\quad n\geqslant 3.\tag{1}$$ Let $$b_n=a_n-\frac23$$. Then (1) implies that $$b_{n+1}=-\frac12 b_n\tag{2}$$ [Note: One can easily find the form of $$b_n$$ by setting $$a_{n+1}+b=-\frac12(a_n+b)$$.] Now one only needs to show that $$\lim_{n\to\infty}b_n=0.$$ But (2) gives: $$b_{n}=q^{n-3}b_3,\quad n\geqslant 3\tag{3}$$ where $$|q|=\frac12$$.

Your $$(b_n)$$ and $$(c_n)$$ can be read from (3) if you want.

[Added later.] Yet, there is another way to do this problem using linear algebra. Noticing that $$a_{n+1}=\frac{1}{2}a_n+\frac12a_{n-1},\quad a_{n+2}=\frac34a_n+\frac14a_{n-1},\quad n\ge 1,$$ one can write $$b_{n+2}=Ab_n$$ where $$b_n=(a_{n-1},a_n)^T$$ and $$A=\frac14\begin{pmatrix} 2&2\\ 1&3 \end{pmatrix} =SJS^{-1}$$ where $$J=\begin{pmatrix} \frac14&0\\ 0&1 \end{pmatrix},\quad S=\begin{pmatrix} -2&1\\ 1&1 \end{pmatrix},\quad S^{-1}=\frac13\begin{pmatrix} -1&1\\ 1&2 \end{pmatrix}.$$ Now, $$b_{2n+1}=A^{n}b_1,\quad n\ge1.\tag{4}$$ But as $$n\to\infty$$, $$A^{n}=SJ^{n}S^{-1}\to S \begin{pmatrix} 0&0\\0&1 \end{pmatrix}S^{-1}= \frac13\begin{pmatrix} 1&2\\1&2 \end{pmatrix}.\tag{5}$$ Combining (4) and (5) one gets $$(a_{2n},a_{2n+1})\to (\frac23,\frac23)\quad\text{as }n\to\infty.$$ Now you can apply the theorem you have to conclude that $$\lim_{n\to\infty}a_n=\frac23.$$

• Excuse me, i don't understand how do you get (1) from $a_{n-1}+a_n=2a_{n+1}$. Could you explain me more that step? – Tom Arbuckle Nov 22 '18 at 1:22
• @TomArbuckle: Adding up all the identities above (1), one has $$(a_1+\cdots+a_{n-1})+(a_2+\cdots+a_n)=2(a_3+\cdots+a_{n+1}),$$ which implies that $$a_1+2a_2+\color{red}{(2a_3+\cdots+2a_{n-1})}+a_n =\color{red}{2(a_3+\cdots+a_{n-1})}+2a_n+2a_{n+1}.$$ So $$0+2\times 1=a_1+2a_2=a_n+a_{n+1}.$$ – user587192 Nov 22 '18 at 13:24

Note that $$0,1,5,21,85,...$$ is the sequence $$\frac{4^n -1}{3}$$ for $$n \geq 0$$. Also, $$*, 2, 8,32,128,\dots = 2^{2n-1}$$. Note that the missing term $$*$$ will fit any pattern, so we need only worry about larger values. These observations show the first sequence converges to $$2/3$$.

The other sequence is harder to spot the pattern: $$1,3,11,43,\dots = \frac{2^{2n+1}+1}{3}$$. You should have no problem finding a pattern for the denominators.

Rewriting the recursion you obtain

• $$a_n=\frac{a_{n-1}+a_{n-2}}{2} \Leftrightarrow a_n - \frac{1}{2}a_{n-1}-\frac{1}{2}a_{n-2}= 0$$

This is a linear difference equation with the characteristic polynomial $$x^2 -\frac{1}{2}x-\frac{1}{2} = 0 \Leftrightarrow \left(x + \frac{1}{2} \right)(x-1)= 0$$ So, the general solution is $$a\cdot 1^n + b \cdot \left(-\frac{1}{2} \right)^n = a+b\left(-\frac{1}{2} \right)^n \stackrel{a_1 =0, a_2 = 1}{\Longrightarrow}\frac{2}{3} + \frac{4}{3}\left(-\frac{1}{2} \right)^n \stackrel{n \to \infty}{\longrightarrow}\frac{2}{3}$$

Guide: Define $$b_n := \frac{b_{n-1}+c_{n-1}}{2} \qquad c_n := \frac{b_{n}+c_{n-1}}{2}$$ with $$b_1 := a_1$$ and $$c_1 := a_2$$ for all $$n \in \Bbb{N}$$. It's not hard to see that $$b_n = a_{2n-1} \qquad c_n = a_{2n}$$ by induction.

• Could you help me and guide me to show that, for example, $b_n$ is monotone increasing? – Tom Arbuckle Nov 21 '18 at 3:10
• @TomArbuckle That's again a straightforward exercise of induction. Since this site in called Mathematics Stack Exchange, it's an exchange of ideas, rather than a do-my-HW site. – GNUSupporter 8964民主女神 地下教會 Nov 21 '18 at 3:17

We have that $$2a_n=a_{n-1}+a_{n-2}$$therefore $$2(a_n-a_{n-1})=a_{n-2}-a_{n-1}$$defining $$b_n= a_n-a_{n-1}$$ we obtain$$2b_n=-{b_{n-1}}$$since $$b_2=a_2-a_1=1$$ we have $$b_n=4(-{1\over 2})^n$$which yields to $$a_n=a_1+\sum_{k=2}^{n}b_k=\sum_{k=2}^{n}b_k$$and we can write $$\lim_{n\to \infty}a_n=\sum_{k=2}^{\infty}b_k=b_2+b_3+b_4+\cdots= {1\over 1-\left(-{1\over 2}\right)}={2\over 3}$$