# The sequence defined by $x_{n}=\frac{x_{n-1}+x_{n-2}}{2}.$

Let $x_{1}=0,x_{2}=1$ and for $n\geq3,$ define $x_{n}=\frac{x_{n-1}+x_{n-2}}{2}.$

Which of the following is/are true?

$1.\{x_{n}\}$ is a monotone sequence.

$2. \lim_{n\to\infty} x_{n}=\frac{1}{2}.$

$3.\{x_{n}\}$ is a cauchy sequence.

$4.\lim_{n\to\infty} x_{n}=\frac{2}{3}.$

From first three terms it is clear that the sequence is not a monotone sequence and limit can not be $\frac{1}{2}$ if it is convergent. How to prove that the sequence is convergent and its limit is $\frac{2}{3}$? Thanks a lot.

• – lab bhattacharjee Jun 24 '16 at 15:35
• – Martin Sleziak Jan 21 at 15:00
• @MartinSleziak thanks – neelkanth Jan 22 at 7:10

$$0,1,\frac 1 2, \frac 3 4, \frac 5 8, \frac{11}{16}, ...$$ Now, the trick is that if you take the common differences: $$1, -\frac 1 2, \frac 1 4, -\frac 1 8, \frac 1 {16}$$ It's a geometric series of first term $1$ and ratio $-\frac 1 2$. Thus, this sequence is just a sequence of partial sums of this geometric sequence, so we just use the partial sum formula: $$x_n=\frac{\left(-\frac 1 2\right)^{n-1}-1}{\left(-\frac 1 2\right)-1}=\frac 2 3\left(1-\left(-\frac 1 2\right)^{n-1}\right)$$ Hopefully, you can take it from here. Good luck!
Interpreted as linear recurrence with constant coefficients $$x_n = \frac{1}{2} x_{n-1} + \frac{1}{2} x_{n-2}$$ with characteristic polynomial $$p(t) = t^2 - \frac{1}{2} t - \frac{1}{2}$$ where we deduce the roots from $$0 = \left( t - \frac{1}{4} \right)^2 - \frac{1}{2} - \frac{1}{16} \iff \\ t = \frac{1 \pm 3}{4}$$ so we have the solutions $$x_n = k_1 \left( -\frac{1}{2} \right)^n + k_2 \, 1^n$$ where the coefficients have to be deduced from the initial conditions: $$0 = x_1 = k_1 \left( -\frac{1}{2} \right)^1 + k_2 = -\frac{1}{2} k_1 + k_2 \\ 1 = x_2 = k_1 \left( -\frac{1}{2} \right)^2 + k_2 = \frac{1}{4} k_1 + k_2$$ So $1 = (3/4) k_1$ or $k_1 = 4/3$ and $k_2 = 2/3$ which results in $$x_n = \frac{2}{3} \left( 1 + 2 \left( -\frac{1}{2} \right)^n \right) = \frac{2}{3} \left( 1 - \left( -\frac{1}{2} \right)^{n-1} \right)$$ This form helps to answer the question about the monotonicity of the sequence and the limit.
For some integers $m,n$ where $m>n>0$, $|x_n-x_{n+1}|=|x_n-\frac12(x_n-x_{n-1})|=\frac12|x_{n-1}-x_n|=...=\frac1{2^{n-1}}|x_1-x_2|=\frac1{2^{n-1}}\\ |x_n-x_m|=|(x_n-x_{n+1})+(x_{n+1}-x_{n+2})+...+(x_{m-1}-x_m)|\\ \leq \frac1{2^{n-1}}+\frac1{2^n}+...\\ =\frac1{2^n}\to 0\text{ as }n\to\infty$