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.

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?

share|improve this question
2  
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
add comment

2 Answers

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?

share|improve this answer
2  
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
add comment

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

share|improve this answer
    
wow, cooool is this! –  doniyor Dec 26 '12 at 9:11
add comment

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.