# Does $x_{n+2} = (x_{n+1} + x_{n})/2$ converge?

Let $0 < a < b < \infty$. Define $x_1=a$, $x_2=b$, and $x_{n+2} = \frac{x_n + x_{n+1}}{2}$ for $n \geq 1$. Does $\{x_n\}$ converge? If so, to what limit?

-
What have you tried? In what context does this problem arise? –  JavaMan Nov 28 '12 at 5:35
First find out what's going on. Then you can probably do it yourself. Put points $a$, $b$ on the $x$-axis. Where is $x_3$? Where is $x_4$? where is $x_5$? If at first you cant't do it for general $a$ and $b$, use $2$ and $15$. –  André Nicolas Nov 28 '12 at 5:47

HINT: Note that $\dfrac{x_n+x_{n+1}}2$ is just the arithmetic mean of $x_n$ and $x_{n+1}$, so geometrically it’s their midpoint: it’s halfway between $x_n$ and $x_{n+1}$. Now make a rough sketch of the first few terms:

   -|------------------------------|--------|---|---|--------------|----
a = x(0)                      x(2)     x(4) | x(3)             b = x(1)
x(5)


This should suggest the following program:

Show that the subsequence $\langle x_{2n}:n\in\Bbb N\rangle$ is strictly increasing, the subsequence $\langle x_{2n+1}:n\in\Bbb N\rangle$ is strictly decreasing,

$$x_0<x_2<x_4<\ldots~\ldots<x_5<x_3<x_1\;,$$

and $$\lim_{n\to\infty}(x_{2n}-x_{2n+1})=0\;.$$

These imply that $\langle x_n:n\in\Bbb N\rangle$ converges; why?

To get the actual limit, consider the series

$$\sum_{n\ge 0}\frac{(-1)^n}{2^n}\;;$$

can you see how to relate it to the original problem?

-
To get the actual limit... one can also note that $2x_{n+1}+x_n$ is independent of $n$. –  Did Nov 28 '12 at 6:36

$$x_3 = \dfrac{a+b}2$$ $$x_4 = \dfrac{a+3b}4$$ $$x_5 = \dfrac{3a+5b}8$$ $$x_6 = \dfrac{5a+11b}{16}$$ $$x_7 = \dfrac{11a+21b}{32}$$ In general, (by induction) $$x_n = \dfrac{J_{n-2} a + J_{n-1}b}{2^{n-2}}$$ where $J_n$'s are Jacobsthal sequence i.e. they satisfy the recurrence $$J_{n+1} = J_n + 2J_{n-1}$$ with $J_0 = 0$ and $J_1 = 1$. Once we have this recurrence, it is not hard (by induction) to find that $$J_n = \dfrac{2^n - (-1)^n}3$$ Hence, $$x_n = \dfrac{(2^{n-2} - (-1)^{n-2})a + (2^{n-1} - (-1)^{n-1})b}{3 \cdot 2^{n-2}} \to \dfrac{a + 2b}{3}$$

-
wow, cooool is this! –  doniyor Dec 26 '12 at 9:11