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.

If $x_1<x_2$ are arbitrary real numbers, and $x_n=\frac{1}{2}(x_{n-2}+x_{n-1})$ for $n>2$, show that $(x_n)$ is convergent. What is the limit?

The back of my textbook says that $\lim(x_n)=\frac{1}{3}x_1+\frac{2}{3}x_2$. I was thinking that if I show that the sequence is monotone increasing by induction, then I can "guess" (from the back of my textbook) that there is an upperbound of the limit and show by induction that all elements in $x_n$ are between $x_1$ and the upperbound and so it's bounded. Then by the monotone convergence theorem say it's convergent.

I'm not sure how to show that it is monotone, and then after showing convergence finding the limit, without magically guessing it.

share|improve this question

4 Answers 4

This sequence is not monotone - for example $x_3 = \frac12 (x_1 + x_2) < x_2$. You can prove convergence using the Cauchy criterion - the distance between consecutive terms halves every term:

$$ |x_n - x_{n-1}| = \frac12 |x_{n-1} - x_{n-2}|,$$ so iterating this equality to obtain $|x_n - x_{n-1}| = 2^{-n+2} |x_2 - x_1|$ we can use a geometric series bound (i.e. use $|r| < 1 \implies \sum_{n=0}^\infty r^n = 1/(1-r)$ as an upper bound) to show the sequence is Cauchy:

$$|x_{n+m} - x_n| \le \sum_{k=1}^m |x_{n+k} - x_{n+k-1}|\le 2^{-n}|x_2 - x_1|\sum_{k=1}^m 2^{-k} \le 2^{-n}|x_2-x_1| \to 0 \textrm{ as } n \to \infty.$$

To find the limit, write the sequence as a geometric series similar to the above:

$$ \begin{align} \lim_{n \to \infty} x_n &= x_1 + \sum_{n=2}^\infty (x_n - x_{n-1}) \\ &= x_1 + (x_2-x_1)\sum_{n=2}^\infty (-2)^{-n+2} \\ &= x_1 + (x_2-x_1)\frac{1}{1 - (-2)} \\ &= \frac{x_1}{3} + \frac{2 x_2}{3}. \end{align} $$

share|improve this answer
    
How do you come up with the geometric series? Why that? –  Desperate Fluffy Sep 23 '13 at 6:01
    
@DesperateFluffy: it's the standard way to show that contractions like this converge. In general the Cauchy criterion can be written as $\sum_{k=n}^\infty |x_{k+1} - x_{k}| \to 0$ as $n \to \infty$ if you want a systematic path to follow. As for finding the limit, the fact that the geometric series came up in the convergence proof is a big hint. Any time you have a sequence defined by a recurrence of differences like this, writing it as a series is likely to help. –  Anthony Carapetis Sep 23 '13 at 6:10

A related problem. To prove convergence, note that

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

$$ \implies |x_n-x_{n-1}|=\frac{1}{2}|x_{n-1}-x_{n-2}|<\frac{2}{3}|x_{n-1}-x_{n-2}|. $$

This proves that the sequence is a contraction and hence convergent by the Fixed point theorem. To solve it, then assume the solution $x_n=r^n$ and subs back in the equation and solve the resulting polynomial in $r$.

share|improve this answer

Equivalent question solved of Carothers (Real Analysis) in this spanish blog.

share|improve this answer

$\displaystyle{z \in {\mathbb C}\,,\quad \left\vert z\right\vert < 1}$.

$$ \sum_{n = 3}^{\infty}x_{n}\,z^{n} = {1 \over 2}\sum_{n = 3}^{\infty}x_{n - 2}\,z^{n} + {1 \over 2}\sum_{n = 3}^{\infty}x_{n - 1}\,z^{n} $$

\begin{align} ------------&------------------\\ \sum_{n = 1}^{\infty}x_{n}\,z^{n} - x_{1}z - x_{2}z^{2} &= {1 \over 2}\,z^{2}\sum_{n = 1}^{\infty}x_{n}\,z^{n} + {1 \over 2}\,z\sum_{n = 2}^{\infty}x_{n}\,z^{n} \\[3mm]&= {1 \over 2}\,z^{2}\sum_{n = 1}^{\infty}x_{n}\,z^{n} + {1 \over 2}\,z\left(\sum_{n = 1}^{\infty}x_{n}\,z^{n} - x_{1}z\right) \\------------&------------------ \end{align}

$$ \left(1 - {1 \over 2}\,z - {1 \over 2}\,z^{2}\right) \sum_{n = 1}^{\infty}x_{n}\,z^{n} = x_{1}z + x_{2}z^{2} - {1 \over 2}\,x_{1}\,z^{2} $$

\begin{align} ----&---------------------------\\ \sum_{n = 1}^{\infty}x_{n}\,z^{n} &= -\, {2x_{1}z + \left(2x_{2} - x_{1}\right)z^{2} \over z^{2} + z - 2} = -\, {2x_{1}z + \left(2x_{2} - x_{1}\right)z^{2} \over \left(z - 1\right)\left(z + 2\right)} \\[3mm]&= -\,{1 \over 3}\,z \left[% {2x_{1} + \left(2x_{2} - x_{1}\right)z \over z - 1} - {2x_{1} + \left(2x_{2} - x_{1}\right)z \over z + 2}\right] \\[3mm]&= -\,{1 \over 3}\,z \left\{% \left[% 2x_{2} - x_{1} + {x_{1} + 2x_{2} \over z - 1} \right] - \left[% 2x_{2} - x_{1} + {4x_{1} - 4x_{2} \over z + 2} \right] \right\} \\[3mm]&= {1 \over 3}\left(x_{1} + 2x_{2}\right)z\,{1 \over 1 - z} + {2 \over 3}\left(x_{1} - x_{2}\right)z\,{1 \over 1 + z/2} \\[3mm]&= {1 \over 3}\left(x_{1} + 2x_{2}\right)\sum_{n = 1}^{\infty}z^{n} + {2 \over 3}\left(x_{1} - x_{2}\right)\sum_{n = 1}^{\infty} \left(-1\right)^{n - 1}{z^{n} \over 2^{n - 1}} \\[3mm]&= \sum_{n = 1}^{\infty}\left[% {1 \over 3}\left(x_{1} + 2x_{2}\right) + {2 \over 3}\left(x_{1} - x_{2}\right)\,{\left(-1\right)^{n - 1} \over 2^{n - 1}} \right]z^{n} \\----&--------------------------- \end{align}

$$ x_{n} = {1 \over 3}\left(x_{1} + 2x_{2}\right) + {2 \over 3}\left(x_{1} - x_{2}\right)\, {\left(-1\right)^{n - 1} \over 2^{n - 1}}\,, \qquad\qquad n \geq 1 $$

$$ \begin{array}{|c|}\hline\\ \color{#ff0000}{\large\quad% \lim_{n \to \infty}x_{n} \color{#000000}{\ =\ } {1 \over 3}\,x_{1} + {2 \over 3}\,x_{2} \quad} \\ \\ \hline \end{array} $$

${\bf 'EASY\ WAY':}$ Look for a solution $x_{n} \propto \mu^{n}$. We get $\mu = 1$ and $\mu = -1/2$. The general solution is $x_{n} = A\ 1^{n} + B\left(-1/2\right)^{n} = A + B\left(-1\right)^{n}/2^{n}$. With $x_{1} = A - B/2$ and $x_{2} = A + B/4$ we get $A = x_{1}/3 + 2x_{2}/3 = \lim_{n \to \infty}x_{n}$. In addition, $B = 4\left(x1 - x_{2}\right)/3$.

share|improve this answer

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.