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.
 A: Alternative approach
Notice that
$$x_{n}=x_{n-1} - 2 \left(-\frac12\right)^{n-1}\qquad (1),$$
and so
$$x_n = x_1 + \sum_{k=1}^{n}(-2)\left(-\frac12\right)^k\qquad (2).$$
Now let $n\to \infty.$
You should try to prove $(1)$ and $(2)$ formally.
A: As you already noted, $$x_{2n+1} = 1 + \sum_{i=1}^{n-1}\frac1{2^{2i-1}} = \frac13\left(5-\frac1{2^{2n-1}}\right).$$
You might also note that $$x_{2n+2} = 3 - \sum_{i=0}^n\frac1{2^{2i}} = \frac13\left(5+\frac1{2^{2n}}\right).$$
Combine these two, you have
$$x_n = \frac13\left(5 + 4\left(-\frac12\right)^n\right) \qquad(1).$$
Now, let's prove $(1)$ using induction. First,
$n = 1$, $x_1 = 1$, so $(1)$ is true.  Assume $(1)$ is true for all integers from 1 to $k$, then
$$x_{k+1} = \frac12\left(x_k+x_{k-1}\right) = \frac13\left(5+4\left(-\frac12\right)^{k+1}\right).$$
So $(1)$ is true for $k+1$, so $(1)$ is true for all $k > 0$.
A: 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.
