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.

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