4
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ Do you have an initial value? It will make things considerably easier $\endgroup$ – frogeyedpeas Mar 17 '15 at 21:27
  • $\begingroup$ The sequence is defined by two initial values, but the proof of convergence depends only on the assumption that they are both real numbers. $\endgroup$ – David K Mar 17 '15 at 21:37
  • $\begingroup$ yeah I updated my question $\endgroup$ – geek4079 Mar 17 '15 at 21:39
  • 1
    $\begingroup$ $$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) $\endgroup$ – frogeyedpeas Mar 17 '15 at 21:50
  • 1
    $\begingroup$ @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}$. $\endgroup$ – Barry Cipra Mar 17 '15 at 22:19
15
$\begingroup$

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

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

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

$\endgroup$
  • 1
    $\begingroup$ I'm missing the link between $x_n=x_{n+1}$ and $x_{n+1} - x_n=r$, sorry $\endgroup$ – geek4079 Mar 17 '15 at 21:43
  • 1
    $\begingroup$ 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 $\endgroup$ – frogeyedpeas Mar 17 '15 at 21:51
  • 1
    $\begingroup$ Thus you know that $x_{n+2}$ will be midway between $x_{n+1}, x_{n}$ $\endgroup$ – frogeyedpeas Mar 17 '15 at 21:52
  • 1
    $\begingroup$ 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}$ $\endgroup$ – frogeyedpeas Mar 17 '15 at 21:53
  • 1
    $\begingroup$ 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}}$ $\endgroup$ – frogeyedpeas Mar 17 '15 at 21:54
1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ You can even tell that this sum is $2(x_2-x_1)/3$, so convergence is to $(2x_2+x_1)/3$. $\endgroup$ – Yves Daoust Mar 17 '15 at 22:24
  • $\begingroup$ @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$? $\endgroup$ – Jimmy R. Jan 31 '16 at 10:22
  • $\begingroup$ $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$ $\endgroup$ – Yves Daoust Jan 31 '16 at 12:28
  • $\begingroup$ Of course. Sorry for bothering you for something so trivial. Sometimes, I just get stacked with something that is obvious. Thanks anyway +1 $\endgroup$ – Jimmy R. Jan 31 '16 at 12:32
0
$\begingroup$

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$

$\endgroup$

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.