<s>[INST] Proving by Induction that $x_{2n+1} = 1+1/2+1/2^3+\cdots+1/(2^{2n-1})$ Let $x_1 = 1$, $x_2 = 2$ and $x_n = \frac{x_{n-1}+x_{n-2}}{2}$. The sequence $(x_n)$ is Cauchy, which I can easily prove. To find its limit I must first show (by Induction) the assertation
$$
P(n): x_{2n+1} = 1+\frac{1}{2}+\frac{1}{2^3}+\cdots+\frac{1}{2^{2n-1}},\quad\forall n\in\mathbb{N}.
$$
Base case.
For $n=1$, $x_{2n+1} = x_{3} = \frac{1+2}{2}  = 1+ \frac{1}{2},$ thus $P(1)$ holds.
Inductive step. Let $P(k)$ be true. Then for $P(k+1)$ we have
$$
x_{2(k+1)+1} = \frac{1}{2}(x_{2(k+1)}+x_{2(k+1)-1}) = \frac{1}{2}(x_{2k+2}+x_{2k+1}).
$$
But then I'm stuck. I am missing something here but, at present, I cannot think of a different approach.
 [/INST] After re-checking the algebra I finally found the solution I was looking for. The rest of the proof is thus as follows.
By definition $x_{2k+2} = \frac{x_{2k}+x_{2k+1}}{2}$ and $x_{2k+1} = \frac{x_{2k}+x_{2k-1}}{2}$. Thus $x_{2k} = 2x_{2k+1}-x_{2k-1}$; noting that $x_{2k-1} = x_{2(k-1)+1}$ and replacing $x_{2k+2}$ in the equation of the Inductive step gives
\begin{align*}
x_{2(k+1)+1} & = \frac{5}{4}x_{2k+1}-\frac{1}{4}x_{2(k-1)+1}\\
& = \frac{5}{4}(1+\frac{1}{2}+\frac{1}{2^3}+\cdots+\frac{1}{2^{2k-1}})-\frac{1}{4}(1+\frac{1}{2}+\frac{1}{2^3}+\cdots+\frac{1}{2^{2k-3}})\\
&= 1+\frac{1}{2}+\frac{1}{2^3}+\cdots+\frac{1}{2^{2(k+1)-1}},
\end{align*}
which is the desired result.
</s>