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.

  • $\begingroup$ Tiny nitpick: Base case in 1) must also include $x_2 = 3 \ge 1$. Or an easier bound is 0. $\endgroup$ – Ishfaaq Aug 15 '14 at 8:14
  • $\begingroup$ Why must the second term be included? $\endgroup$ – The Substitute Aug 15 '14 at 8:18
  • 3
    $\begingroup$ 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. $\endgroup$ – Zoe H Aug 15 '14 at 8:26
  • 1
    $\begingroup$ Think of your inductive statement as $P(n)$ which includes correctness for $n + 1$ too. But then $P(1)$ is not true. $\endgroup$ – Ishfaaq Aug 15 '14 at 8:31
  • $\begingroup$ @Ishfaaq, got it. $\endgroup$ – 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}$$


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

  • $\begingroup$ "Then we take the limes" Assuming convergence. $\endgroup$ – Did Aug 15 '14 at 9:09
  • $\begingroup$ @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?" $\endgroup$ – miracle173 Aug 15 '14 at 9:26
  • $\begingroup$ "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. $\endgroup$ – Did Aug 15 '14 at 9:31
  • $\begingroup$ I see now. It is not proven by the OP. $\endgroup$ – miracle173 Aug 15 '14 at 9:43
  • $\begingroup$ 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. $\endgroup$ – The Substitute Aug 15 '14 at 9:48

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.