Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
Tiny nitpick: Base case in 1) must also include $x_2 = 3 \ge 1$. Or an easier bound is 0. –  Ishfaaq Aug 15 at 8:14
    
Why must the second term be included? –  The Substitute Aug 15 at 8:18
3  
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 at 8:26
1  
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 at 8:31
    
@Ishfaaq, got it. –  The Substitute Aug 15 at 8:32

3 Answers 3

up vote 9 down vote accepted

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

share|improve this answer

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

share|improve this answer

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

share|improve this answer
    
"Then we take the limes" Assuming convergence. –  Did Aug 15 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 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 at 9:31
    
I see now. It is not proven by the OP. –  miracle173 Aug 15 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 at 9:48

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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