# Determining if a recursively defined sequence converges and finding its limit

Define $\lbrace x_n \rbrace$ by $$x_1=1, x_2=3; x_{n+2}=\frac{x_{n+1}+2x_{n}}{3} \text{if} \, n\ge 1$$ The instructions are to determine if this sequence exists and to find the limit if it exists.

I prove that the sequence is eventually decreasing and that it is bounded below (see work below). Hence, if my work is correct, the sequence will have a limit. The problem is that if the limit is, say, $L$ then it should satisfy $L=\frac{L+2L}{3}$; however, every real number satisfies the latter equality. So, if this limit exists, how do I actually find it?

Proving the limit exists:

1) The sequence is bounded below by $1$. Base Case: $x_1=1\ge 1$.

Induction: Suppose $x_n\ge 1$ for all $k=1,\ldots ,n+1$. Then $x_{n+2}=\frac{x_{n+1}+2x_{n}}{3}\ge \frac{3}{3}=1$.

2) The sequence is eventually decreasing: It actually starts decreasing after the 4th term. So I take as my base case $x_5<x_4$. Base Case: Note that $$x_3=\frac{x_2+2x_1}{3}=\frac{3+2}{3}=5/3$$ and hence $$x_4=\frac{x_{3}+2x_{2}}{3}=\frac{5/3+2\times3}{3}=23/9$$ so $$x_5=\frac{x_{4}+2x_{3}}{3}=\frac{23/9+2\times5/3}{3}=\frac{53}{27}<x_4$$

Induction: Suppose $x_{n}<x_{n-1}.$ Then $$x_{n+1}-x_n=\frac{x_{n}+2x_{n-1}}{3}-x_n \\=2\frac{x_{n-1}-x_n}{3}<0$$ Therefore, the sequence is bounded below and is eventually decreasing.

-
Tiny nitpick: Base case in 1) must also include $x_2 = 3 \ge 1$. Or an easier bound is 0. – Ishfaaq Aug 15 '14 at 8:14
Why must the second term be included? – The Substitute Aug 15 '14 at 8:18
Your proof that the sequence is eventually decreasing is flawed. If $x_n < x_{n-1}$ then $x_{n-1} - x_n > 0$. It follows from Ewan Delanoy's answer that the sequence is not eventually monotone. – Zoe H Aug 15 '14 at 8:26
Think of your inductive statement as $P(n)$ which includes correctness for $n + 1$ too. But then $P(1)$ is not true. – Ishfaaq Aug 15 '14 at 8:31
@Ishfaaq, got it. – The Substitute Aug 15 '14 at 8:32

This is a linear recurrent sequence of order $2$. The characteristic polynomial $X^2-\frac{X+2}{3}$ has roots $1$ and $-\frac{2}{3}$. So there are two constants $a$ and $b$ such that $x_n=a(1^n)+b(\frac{-2}{3})^n$. Using the initial conditions, we obtain $a=\frac{11}{5}$ and $b=\frac{9}{5}$. The limit is therefore $\frac{11}{5}$.

-

Setting $$y_n=x_{n+1}-x_n \quad \forall n\in \mathbb{N},$$ we have $$y_{n+1}=x_{n+2}-x_{n+1}=\frac{x_{n+1}+2x_n}{3}-x_{n+1}=-\frac23(x_{n+1}-x_n)=-\frac23y_n.$$ It follows that $$y_n=\left(-\frac23\right)^{n-1}y_1=2\left(-\frac23\right)^{n-1} \quad \forall n \in \mathbb{N}.$$ Finally, for every $n\in \mathbb{N}$, we get: \begin{eqnarray} x_n&=&x_1+\sum_{k=1}^{n-1}(x_{k+1}-x_k)=x_1+\sum_{k=1}^{n-1}y_k=1+2\sum_{k=1}^{n-1}\left(-\frac23\right)^{k-1}=1+2\frac{1-(-2/3)^{n-1}}{1+2/3}\\ &=&1+\frac65\left[1-\left(-\frac23\right)^{n-1}\right]=\frac{11}{5}-\frac65\left(-\frac23\right)^{n-1}. \end{eqnarray} We can now see that $\{x_n\}$ converges and its limit is $\frac{11}{5}$.

-

So, if this limit exists, how do I actually find it?

We add $\frac{2}{3}x_{n-1}$ to the recurrence relation term to get $$x_n+\frac{2}{3}x_{n-1}=x_{n-1}+\frac{2}{3}x_{n-2}, \; \forall n\gt 2$$ and therefore $$x_n+\frac{2}{3}x_{n-1}=x_{2}+\frac{2}{3}x_{1}=3+\frac{2}{3}$$ Assuming that the sequence is convergent we can take the limits $$(1+\frac{2}{3}) \lim x_n = \frac{11}{3}$$ to find $$\lim x_n=\frac{11}{5}$$

checking the convergence

From the defining relation $$x_{n+2}=\frac{x_{n+1}+2x_{n}}{3}$$ we get $$x_{n+2}-x_{n+1}=-\frac{2}{3}(x_{n+1}-x_{n})$$

so that we can conclude that the sign of two successing elements of the sequence is alternating:

From this we get $$\text{sgn}(x_{n+2}-x_{n+1})=-\text{sgn}(x_{n+1}-x_{n})=(-1)^n\text{sgn}(x_{2}-x_{1})=(-1)^n$$ $$x_{n+2}-x_{n}=\frac{x_{n+1}-x_{n}}{3}$$

$$\text{sgn}(x_{n+2}-x_{n})=\text{sgn}(\frac{x_{n+1}-x_{n}}{3})=(-1)^{n+1}$$

so the sequence element with odd indexes are increasing and the sequence elements with the evben indexes are decreasing. We have

$$x_{2r+1} \le x_{2s-1} \le x_{2s} , \; r\lt s$$

so $\lim\limits_{n \to \infty}x_{2n}$ and $\lim\limits_{n \to \infty}x_{2n+1}$ exist and the difference is $0$ so the sequence converges. $[x_{2n+1},x_{2n+2}]$ is a sequence of nested intervals. Their length converges to $0$.

-
"Then we take the limes" Assuming convergence. – Did Aug 15 '14 at 9:09
@Did Thank's. This necessary assumption is already proved in the OP. The question was "So, if this limit exists, how do I actually find it?" – miracle173 Aug 15 '14 at 9:26
"This necessary assumption is already proved in the OP" This assumption does not hold hence it is problematic to base the proof of anything on it. – Did Aug 15 '14 at 9:31
I see now. It is not proven by the OP. – miracle173 Aug 15 '14 at 9:43
I had the same question about the assumption of convergence, but @miracle173 does use the given values for $x_1, x_2$, so I assume it is not necessary. – The Substitute Aug 15 '14 at 9:48