Proof by induction: Inductive step struggles Using induction to prove that:
$$
1 - \frac{1}{2} + \frac{1}{4} - \frac{1}{8} +...+\left( \frac{1}{2}\right)^{n} = \frac{2^{n+1}+(-1)^{n}}{3\times2^{n}}
$$
where $ n $ is a nonnegative integer.
Preforming the basis step where $ n $ is equal to 0
$$
1 = \frac{2^{1}+(-1)^{0}}{3\times2^{0}} = \frac{3}{3} = 1
$$
Now the basis step is confirmed.
Then I started the inductive step where $ n = k $ is assumed true and I needed to prove $ n = k+1 $
$$
1 - \frac{1}{2} + \frac{1}{4} - \frac{1}{8} +...+\left(- \frac{1}{2}\right)^{k} + \left(- \frac{1}{2}\right)^{k+1} = \frac{2^{k+1+1}+(-1)^{k+1}}{3\times2^{k+1}}
$$
Using the inductive hypothesis
$$
\frac{2^{k+1}+(-1)^{k}}{3\times2^{k}} + \left(- \frac{1}{2}\right)^{k+1} = \frac{2^{k+1+1}+(-1)^{k+1}}{3\times 2^{k+1}}
$$
After this I am struggling here trying to get around to the end. I would appreciate any guidance.
 A: Multplying numerator and denominator of the first term by $2$ we get $$
\frac{2^{k+1}+(-1)^{k}}{3*2^{k}} + (- \frac{1}{2})^{k+1} =\frac{2^{k+2}+2(-1)^{k}}{3*2^{k+1}} + (- \frac{1}{2})^{k+1} =\frac  {2^{k+2}+2(-1)^{k}+3(-1)^{k+1}} {3*2^{k+1}}
$$ Now use the fact that $2(-1)^{k}+3(-1)^{k+1}=(-1)^{k+1}$ (which can be checked by considering the case $k$ even and $k$ odd separtely).
A: Use instead the perturbation method from Concrete Mathematics:
\begin{align}
S_{n} + (-1)^{n+1}\frac{1}{2^{n+1}}&= \sum_{k=0}^{n}(-1)^{k}\frac{1}{2^{k}} +(-1)^{n+1}\frac{1}{2^{n+1}}=1 -\frac{1}{2}\sum_{k=0}^{n}(-1)^{k}\frac{1}{2^{k}} \\
&= 1-\frac{1}{2}S_n
\end{align}
\begin{align}
\frac{3}{2}S_n&=1 - (-1)^{n+1}\frac{1}{2^{n+1}} \\
S_n &=\frac{2(1 - (-1)^{n+1}\frac{1}{2^{n+1}})}{3} = \frac{2^{n+2}-(-1)^{n+1}}{3\cdot2^{n+1}}
\end{align}
A: \begin{align}
\frac{2^{k+1}+(-1)^k}{3 \times 2^k}+\left(-\frac{1}{2}\right)^{k+1} 
&=\frac{2 \times 2^{k+1}+2 \times(-1)^k}{3 \times 2^{k+1}}+\frac{3 \times (-1)^{k+1}}{3 \times 2^{k+1}} \\
&=\frac{2^{k+2}+2 \times (-1)^k+3 \times (-1)^{k+1}}{3 \times 2^{k+1}} \\
&=\frac{2^{k+2}-2 \times (-1)^{k+1}+3 \times (-1)^{k+1}}{3 \times 2^{k+1}} \\
&=\frac{2^{k+2}+(-1)^{k+1}}{3 \times 2^{k+1}}
\end{align}
