Proof of convergence of a recursive sequence

Question

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?

Answer 1

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

Answer 2

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

Answer 3

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.

Answer 4

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.

Answer 5

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$