Convergence of a sequence given by $x_{n+1}=\frac 23(x_n+1)$

A sequence $(x_n)_{n\in\mathbb N}$ is defined by $$x_0=0, \qquad x_{n+1}=\frac23(x_n+1)\text{ for }n=1,2,\dots$$ Prove that this sequence converges and find the limit.

The infimum of $(x_n)$ here is obviously 0, however, I do not know how to find the supremum and the limit of $(x_n)$.

• Hint: If the sequence converges, then for large $n$ we have $x_n \approx x_{n+1} = \frac23(x_n+1)$. Suppose the "$\approx$" were "$=$"; that would give you an equation to solve. The equation should give you a pretty good guess at what the limit it; once you have the guess it's much easier to come up with an actual proof that it is right. – Henning Makholm Dec 23 '14 at 15:06
• For some basic information about writing math at this site see e.g. here, here, here and here. – Martin Sleziak Dec 23 '14 at 15:18

If $L$ denotes the limit value, we should have $L = \frac23(L+1)$ or $L=2$. Then writing $y_n = 2- x_n$, we want to show that $y_n \to 0$ and our recursion becomes $y_{n+1} = \frac23 y_n$, with starting value $y_0 = 2$.

• One of my math sayings is "always expand around zero". This is a nice example of that. – marty cohen Dec 24 '14 at 4:55

To guess the limit in this sort of question, note that, if the limit is $L$, then both $x_n$ and $x_{n+1}$ tend to $L$. So replace them both by $L$ in the recurrence relation and solve for $L$. Then you just have to show that the sequence converges to this limit.

$3x_{n+1}-3x_n=2x_n+2-2x_{n-1}-2\implies 3x_{n+1}-5x_n+2x_{n-1}=0$

Therefore the characteristic equation is,

$$3t^2-5t+2=0$$

$\therefore t=\dfrac{2}{3}, 1$

$${x_n=a+b\left(\dfrac{2}{3}\right)^n}\tag{1}$$

To find $a$ and $b$ we note that,

$x_0=0=a+b\tag{2}$ $x_1=\dfrac{2}{3}=a+b\left(\dfrac{2}{3}\right)\tag{3}$

Solving we get $a=2,b=-2$.

Thus $${x_n=2\left(1-\left(\dfrac{2}{3}\right)^n\right)}$$

Therefore,

$$\color{blue}{\boxed{\displaystyle\lim_{n\to\infty}x_n=2}}$$

I have intentionally skipped the proof of existence of $\displaystyle\lim_{n\to\infty}x_n$. Why can we assume that the limit indeed exists?

If you can show that $$x_{n-1}\le x_n \qquad\Rightarrow\qquad \frac23(x_{n-1}+1)\le \frac23(x_n+1),$$ you should be able to see that this sequence is monotone.

If you can show that $$x_n\le 2 \qquad\Rightarrow\qquad \frac23(x_n+1)\le2,$$ you should be able to show that $x_n\le 2$. The inequality $x_n\ge0$ is easy, so this sequence is bounded.

Every bounded monotone sequence is convergent.

From the other answers you already know how to find the limit.

Make a guess of the limit and then use the monotone convergence theorem. You have to show that the sequence is bounded and monotonic (i.e. increasing) and then conclude by MCT that it converges.

To guess the limit solve $L=\frac{2}{3}(L+1)$.

Edit: The guess of the limit is used in the MCT part. Show that $x_n \leq 2 \forall n \in \mathbb{N}$

If a recurrence relation has a limit, then it is a fixed point of the recurrence. So the only possible limit of

$$x_{n+1}=\frac23(x_n+1)$$

... is $x$ such that

$$x =\frac23(x+1)$$

i.e. $$x = 2$$

... independent of the initial value $x_0$.

If we now define

$$y_n = x_n - 2 \text{ for }n=1,2,\dots$$

then

$$y_{n+1} + 2 = \frac23(y_n+3)$$

so

$$y_{n+1} = \frac23y_n$$

... which clearly converges to $0$ for any $y_0$.

• I've just noticed that this is just a slightly expanded version of what user133281 did. – Thumbnail Dec 23 '14 at 15:46