Proof of convergence of a recursive sequence

How do I prove that

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

$x_1=1$

$x_2=2$

is convergent?

• Do you have an initial value? It will make things considerably easier – frogeyedpeas Mar 17 '15 at 21:27
• The sequence is defined by two initial values, but the proof of convergence depends only on the assumption that they are both real numbers. – David K Mar 17 '15 at 21:37
• yeah I updated my question – geek4079 Mar 17 '15 at 21:39
• $$a^{n+2} = 1/2 a^{n+1} + 1/2 a^{n} \rightarrow 2a^2 - a - 1 = 0.$$ Thus: $$a = \frac{1 \pm \sqrt{1 + 4}}{4} = \frac{1 \pm \sqrt{5}}{4}$$ Note that $$2 < \sqrt{5} <3 \rightarrow |\frac{1 \pm \sqrt{5}}{4}| \le 1$$ Thus as n approaches infinity this expression approaches 0 (a much stronger result) – frogeyedpeas Mar 17 '15 at 21:50
• @frogeyedpeas, actually that quadratic factors into $(2a+1)(a-1)$. The square root portion in the quadratic formula is $\sqrt{b^2-4ac}=\sqrt{1^2-4\cdot2\cdot(-1)}=\sqrt{1+8}$. – Barry Cipra Mar 17 '15 at 22:19

Hint: how does $x_{n+2} - x_{n+1}$ relate to $x_{n+1} - x_n$?

• This is by far the most efficient solution; it does not even require initial conditions. – Yves Daoust Mar 17 '15 at 22:05

Given:

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

It follows that if

$$x_n \le x_{n+1}$$

$$x_n \le x_{n+2} \le x_{n+1}$$

Or if:

$$x_n \ge x_{n+1}$$

Then:

$$x_n \ge x_{n+2} \ge x_{n+1}$$

We note that equality only occurs if

$$x_n = x_{n+1}$$

Thus consider the difference

$$|x_{n+1} - x_n| = r$$

It then follows that

$$|x_{n+2} - x_{n+1}| = \frac{r}{2}$$

(Verify this for the case of $x_{n+2} > x_{n+1}$ vs. $x_{n+2} < x_{n+1}$)

Thus

$$|x_{n+k} - x_{n+k-1}| = \frac{r}{2^{k-1}}$$

(Verify this by induction)

Therefore as k approaches infinity

$$|x_{n+k} - x_{n+k-1}| \rightarrow 0$$

• I'm missing the link between $x_n=x_{n+1}$ and $x_{n+1} - x_n=r$, sorry – geek4079 Mar 17 '15 at 21:43
• Try to reason this one out, what happens every time you calculate: $x_{n+2} = \frac{1}{2}(x_{n+1} + x_{n})$. You are taking the average of the previous two values – frogeyedpeas Mar 17 '15 at 21:51
• Thus you know that $x_{n+2}$ will be midway between $x_{n+1}, x_{n}$ – frogeyedpeas Mar 17 '15 at 21:52
• Therefore if the distance between $x_{n+1}, x_{n}$ is r, the distance between $x_{n+2}, x_{n+1}$ is now $\frac{r}{2}$ – frogeyedpeas Mar 17 '15 at 21:53
• Each time you move up to $x_{n+3}$, $x_{n+4}$ ... $x_{n+k}$ your distance between the current term and the most recent term is HALF the previous distance, yielding $r$, $\frac{r}{2}$ ... $\frac{r}{2^{k-1}}$ – frogeyedpeas Mar 17 '15 at 21:54

Let $$y_n \equiv x_n - \frac{x_0-x_1}{2}$$ Then it is easy to see that $$y_0 = \frac{x_0-x_1}{2} \\ y_1 = \frac{x_1-x_0}{2} = - y_0$$ and with a wee bit of algebra, the relation $x_{n+2}= \frac{1}{2}(x_n+x_{n+1}$ becomes $$y_{n+2}= \frac{1}{2}(y_n+y_{n+1})$$

But because $y_1 = -y_0$ the behavior of $y_n$ is easy to see: $$y_0 = y_0\\y_1 = -y_0 y_2 = 0 \\ y_3 = -\frac{1}{2} y_0 \\ y_4 = -\frac{1}{4} y_0 \\ y_5 = -\frac{3}{8} y_0 \\ y_6 = -\frac{5}{16} y_0 \\ y_7 = -\frac{11}{32} y_0 \\$$ and in general, it is easy to show by induction that for $n > 3$ $$y_n = -\left( \frac{2}{3} + \frac{(-1)^{n-1} }{3\cdot 2^{n-2}} \right) y_0$$ the limit of $y_n$ is always $\frac{2}{3}$ Then $x_n$ is obtained by adding back the average of $x_0$ and $x_1$ so it too has a finite limit.

As pointed by @RobertIsrael,

$$x_{n+2}-x_{n+1}=-\frac12(x_{n+1}-x_n).$$

The first order differences decrease geometrically so that their sum converges.

• You can even tell that this sum is $2(x_2-x_1)/3$, so convergence is to $(2x_2+x_1)/3$. – Yves Daoust Mar 17 '15 at 22:24
• @Sorry for asking: I see that the sum is equal to $2(x_2-x_1)/3$ so I get convergence to $2(x_2-x_1)/3$ and not to $(2x_2+x_1)/3$ (as it is the correct result) as follows: \begin{align}\lim_{N\to+\infty}x_{N+1}&=\lim_{N\to+\infty}\sum_{n=0}^{N-1}{x_{n+2}-x_{n+1}}\\&=\lim_{N\to+\infty}\sum_{n=0}^{N-1}(-1/2)^n(x_2-x_1)\\&=\lim_{N\to +\infty}\frac23(x_2-x_1)(1-(-1/2)^N)=\frac23(x_2-x_1)\end{align} Thanks. Edit: Is it only that I have to start from $n=1$ instead of $n=0$? – Jimmy R. Jan 31 '16 at 10:22
• $x_5=\cdots x_5-x_4+x_4-x_3+x_3-x_2+x_2-x_1+x_1=\left(\cdots\left(-\frac12\right)^4+\left(-\frac12\right)^3+\left(-\frac12\right)^2+\left(-\frac12\right)\right)(x_2-x_1)+x_1$ – Yves Daoust Jan 31 '16 at 12:28
• Of course. Sorry for bothering you for something so trivial. Sometimes, I just get stacked with something that is obvious. Thanks anyway +1 – Jimmy R. Jan 31 '16 at 12:32

If $x_{n+1}=x_n$ then $x_{n+2}=x_{n+1}$ and by induction the sequence is constant, thus convergent.

If $x_{n+1}\ne x_n$ and w.l.o.g. $x_{n+1} > x_n$ then $x_{n+1} > x_{n+2} > x_n$. This makes each pair of adjacent terms closer than previous pair: $$|x_{n+2}-x_{n+1}|<|x_{n+1}-x_n|$$ Additionally, each term is a midpoint of the range defined by two preceding terms, so each pair distance is a half of the previous pair distance: $$|x_{n+2}-x_{n+1}|= \frac 12 |x_{n+1}-x_n| = \frac 1{2^n} |x_2-x_1|$$ so the sequence is Cauchy, which implies (in $\Bbb R$) it's convergent.

You can also note that the subsequences of every other term are monotone: $(x_{2i+1})_{i\in\Bbb N}$ is increasing and bounded by $x_2$, while $(x_{2i})_{i\in\Bbb N}$ is decreasing and bounded by $x_1$, so they are both convergent (however that alone does not prove $(x_n)$ is convergent).

EDIT

Let $d = x_2 - x_1$, then:

\begin{align} x_{2n+1} & = x_1 + d\sum_{i=1}^n\frac 1{2^{2i-1}} \\ x_{2n+2} & = x_2 - d\sum_{i=1}^n\frac 1{2^{2i}} \end{align}

For $n=0$ both sums are empty and expressions result in $x_1$ and $x_2$, respectively.

For $n\to\infty$ both sums are geometric series with ratio $\tfrac14$, so:

$\lim_{n\to\infty} x_{2n+1} = x_1 + d\frac {\frac 12}{1-\frac 14} = x_1 + \frac23d$
$\lim_{n\to\infty} x_{2n+2} = x_2 - d\frac {\frac 14}{1-\frac 14} = x_2 - \frac13d$

so they are equal, thus

$\lim_{n\to\infty} x_n = \frac13 x_1 + \frac23 x_2$