<s>[INST] Prove that $|x_n-x_{n+1}|=\frac{1}{2^{n-1}}$ using Mathematical induction $x_1=1$ $x_2=2$
$x_n=\frac{1}{2}(x_{n-2}+x_{n-1})$ for n $\gt$ 2. We have to prove that $|x_n-x_{n+1}|=\frac{1}{2^{n-1}}$
What I tried :
For n=1, $|x_1-x_{2}|=1 =\frac{1}{2^{0}}$
Let for n=k assumption be true. Hence $|x_k-x_{k+1}|=\frac{1}{2^{k-1}}$
For $n=k+1$
$|x_{k+1}-x_{k+2}|=\frac{1}{2}|x_{k-1}+x_{k}-x_{k}-x_{k+1}|=                               \frac{1}{2}|(x_{k-1}-x_{k})+(x_{k}-x_{k+1})| \le \frac{1}{2}|\frac{1}{2^{k-2}}+\frac{1}{2^{k-1}}|$
I'm stuck here, what do i do now? Can anyone help please?
 [/INST] Using triangle inequality will probably not help you, as you're supposed to prove an exact equality, not an inequality. Instead, just substitute $x_{k+2} = \frac{1}{2}(x_k + x_{k+1})$. Then,
\begin{align*}
|x_{k+1} - x_{k+2}| &= \left|x_{k+1} - \frac{1}{2}(x_k + x_{k+1})\right| \\
&= \left|\frac{1}{2}x_k - x_{k+1}\right| \\
&= \frac{1}{2} \cdot \frac{1}{2^{k -1}} = \frac{1}{2^k},
\end{align*}
as required.
</s>