Ytukyg

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?

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 ngeqslant 3.tag{1}
$$
Let $b_n=a_n-frac23$. Then (1) implies that
$$
b_{n+1}=-frac12 b_ntag{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_{ntoinfty}b_n=0.
$$
But (2) gives:
$$
b_{n}=q^{n-3}b_3,quad ngeqslant 3tag{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 nge 1,
$$
one can write $b_{n+2}=Ab_n$ where $b_n=(a_{n-1},a_n)^T$ and
$$
A=frac14begin{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}=frac13begin{pmatrix}
-1&1\
1&2
end{pmatrix}.
$$
Now,
$$
b_{2n+1}=A^{n}b_1,quad nge1.tag{4}
$$
But as $ntoinfty$,
$$
A^{n}=SJ^{n}S^{-1}to S
begin{pmatrix}
0&0\0&1
end{pmatrix}S^{-1}=
frac13begin{pmatrix}
1&2\1&2
end{pmatrix}.tag{5}
$$
Combining (4) and (5) one gets
$$
(a_{2n},a_{2n+1})to (frac23,frac23)quadtext{as }ntoinfty.
$$
Now you can apply the theorem you have to conclude that
$$
lim_{ntoinfty}a_n=frac23.
$$

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
$$acdot 1^n + b cdot left(-frac{1}{2} right)^n = a+bleft(-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.