0
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ it seems you only have one choice. try to define $a_n$ in terms of $b_n$ and $c_n$ from the theorem. $\endgroup$ – The Count Nov 21 '18 at 2:53
  • $\begingroup$ 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. $\endgroup$ – Tom Arbuckle Nov 21 '18 at 2:57
  • $\begingroup$ i mean write the equation for a general $a_n$. $\endgroup$ – The Count Nov 21 '18 at 2:58
  • $\begingroup$ 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}$ $\endgroup$ – Tom Arbuckle Nov 21 '18 at 3:02
  • $\begingroup$ A similar question here $\endgroup$ – rtybase Nov 21 '18 at 10:32
4
$\begingroup$

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. $$

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – Tom Arbuckle Nov 22 '18 at 1:22
  • $\begingroup$ @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}. $$ $\endgroup$ – user587192 Nov 22 '18 at 13:24
1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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}$$

$\endgroup$
0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Could you help me and guide me to show that, for example, $b_n$ is monotone increasing? $\endgroup$ – Tom Arbuckle Nov 21 '18 at 3:10
  • $\begingroup$ @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. $\endgroup$ – GNUSupporter 8964民主女神 地下教會 Nov 21 '18 at 3:17
0
$\begingroup$

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}$$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.