Calculate a limit of recursive sequence

Question

Prove that infinite recursive sequence has limit and calculate it.

$x_{1}=0, x_{2}=1$

$x_{n+2}=\frac{1}{2}(x_{n}+x_{n+1})$

I've tried to separate it to even and odd partial series and it looks like one of them is increasing and another is decreasing. But I can't prove that they are increasing and decreasing, because I don't know how to express $x_{n}$ from a recurrence relation.

What should I do for example with $x_{n+1}$ when I work with the even partial series?

And that is why I can't calculate the limits too, because I need to express somehow $x_{n}$.

Answer 1

This is "easily" solvable if you interpret the meaning of this recurrence formula!

$x_{n+2} = \frac12(x_{n+1} + x_n)$ is the same as saying that $x_{n+2}$ is the average of the last two terms! Because $x_0 = 0$ and $x_1 = 1$ we can see that $x_2 = \frac12$, $x_3 = \frac34$, $x_4 = \frac38$ and so on and so forth.

We can now see that each step we add/subtract a power of $\frac12$. If you separate the sums where you add powers of $\frac12$ from the one where you subtract powers of $\frac12$ you can compute each sum individually and then add everything together to find your answer.

You should arrive at $\frac23$.

Answer 2

Your hunches are indeed correct. For instance,

• a) Show by induction that if $n$ is even, then $x_n > x_{n-1}$.
• b) Use a) to show that if $n$ is even, then $x_n < x_{n-2}$.

Answer 3

Notice $|x_n-x_{n-1}|=|\frac{1}{2}(x_{n-1}-x_{n-2})|=\dots= |\frac{1}{2^{n-1}} (x_1-x_0)|=\frac{1}{2^{n-1}}$, this approaches to $0$ as $n$ grows, the sequence is then cauchy and converges in $\mathbb{R}$.

Answer 4

$\mathbf x_n = \begin{bmatrix} x_{n+1}\\x_{n}\end{bmatrix}$

$\mathbf x_n = \begin{bmatrix} \frac 12 &\frac 12\\1&0\end{bmatrix}\mathbf x_{n-1}$

$\mathbf x_n = \begin{bmatrix} \frac 12 &\frac 12\\1&0\end{bmatrix}^n\mathbf x_{0}$

$\begin{bmatrix} \frac 12 &\frac 12\\1&0\end{bmatrix} = P D P^{-1}$

$\begin{bmatrix} \frac 12 &\frac 12\\1&0\end{bmatrix} = P D^n P^{-1}$

$\begin{bmatrix} \frac 12 &\frac 12\\1&0\end{bmatrix} =\frac 13\begin{bmatrix} 1 &-1\\1&2\end{bmatrix}\begin{bmatrix} 1 &0\\0&-\frac 12\end{bmatrix}\begin{bmatrix} 2 &1\\-1&1\end{bmatrix}$

The limit exists if one of the eigenvalues equals 1 and absolute value of the other eigenvalue is less than 1, which is indeed the case.

$\lim_\limits{n\to\infty} \mathbf x_n = \frac 13\begin{bmatrix} 1 &-1\\1&2\end{bmatrix}\begin{bmatrix} 1 &0\\0&0\end{bmatrix}\begin{bmatrix} 2 &1\\-1&1\end{bmatrix}\begin{bmatrix} 1\\0\end{bmatrix}=\begin{bmatrix} \frac 23\\\frac23\end{bmatrix}$

Answer 5

$\newcommand{\bbx}[1]{\,\bbox[15px,border:1px groove navy]{\displaystyle{#1}}\,} \newcommand{\braces}[1]{\left\lbrace\,{#1}\,\right\rbrace} \newcommand{\bracks}[1]{\left\lbrack\,{#1}\,\right\rbrack} \newcommand{\dd}{\mathrm{d}} \newcommand{\ds}[1]{\displaystyle{#1}} \newcommand{\expo}[1]{\,\mathrm{e}^{#1}\,} \newcommand{\ic}{\mathrm{i}} \newcommand{\mc}[1]{\mathcal{#1}} \newcommand{\mrm}[1]{\mathrm{#1}} \newcommand{\pars}[1]{\left(\,{#1}\,\right)} \newcommand{\partiald}[3][]{\frac{\partial^{#1} #2}{\partial #3^{#1}}} \newcommand{\root}[2][]{\,\sqrt[#1]{\,{#2}\,}\,} \newcommand{\totald}[3][]{\frac{\mathrm{d}^{#1} #2}{\mathrm{d} #3^{#1}}} \newcommand{\verts}[1]{\left\vert\,{#1}\,\right\vert}$

$\ds{x_{1} = 0\,,\quad x_{2} = 1}$.

\begin{align} \sum_{n = 1}^{\infty}x_{n + 2}\,\, z^{n} & = {1 \over 2}\sum_{n = 1}^{\infty}x_{n}z^{n} + {1 \over 2}\sum_{n = 1}^{\infty}x_{n + 1}\,\,z^{n} \\[5mm] \implies 2\sum_{n = 3}^{\infty}x_{n}z^{n} & = z^{2}\sum_{n = 1}^{\infty}x_{n}z^{n} + z\sum_{n = 2}^{\infty}x_{n}\,\,z^{n} \\[5mm] \implies 2\sum_{n = 1}^{\infty}x_{n}z^{n} - 2x_{1}z - 2\, x_{2}\, z^{2} & = z^{2}\sum_{n = 1}^{\infty}x_{n}z^{n} + z\sum_{n = 1}^{\infty}x_{n}\,\,z^{n} - z\,x_{1}z \end{align}

---

\begin{align} \sum_{n = 1}^{\infty}x_{n}z^{n} & = -2\,{z^{2} \over z^{2} + z - 2} = -2\,{z^{2} \over \pars{z + 2}\pars{z - 1}} = -\,{2 \over 3}\,\pars{{z^{2} \over z -1 } - {z^{2} \over z + 2}} \\[5mm] & = -\,{2 \over 3}\,\braces{\bracks{{1 \over z -1} + 2 + \pars{z - 1}} - \bracks{{4 \over z + 2} - 4 + \pars{z + 2}}} \\[5mm] & = {2 \over 3}\,{1 \over 1 - z} + {4 \over 3}\,{1 \over 1 + z/2} - 2 = {2 \over 3}\sum_{n = 1}^{\infty}z^{n} + {4 \over 3}\sum_{n = 1}^{\infty}\pars{-\,{z \over 2}}^{n} \\[5mm] & = \sum_{n = 1}^{\infty}\bracks{{2 \over 3} + 2\,\pars{-1}^{n}\,{2^{1 - n} \over 3}}z^{n} \end{align}

---

$$ \bbx{x_{n} = {2 \over 3}\bracks{1 + {\pars{-1}^{n} \over 2^{n - 1}}}} $$

Answer 6

As each term is the average of the last two terms, the step size is halved each time and with an alternating sign step size, i.e. difference between consecutive terms is $1, -\frac12, \frac 14, -\frac 18,\cdots$ which is a geometric progression (GP) with $r=-\frac 12$. As the first term is zero, the limit of the original series of the sum to infinity of the series of differences (the GP), as given by $$\frac 1{1-(-\frac 12)}=\color{red}{\frac 23}$$