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

## 3 Answers

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 minor point is you don't really have to consider the $k$ even and $k$ odd cases separately to prove your stated fact. Instead, you can directly use $2(-1)^{k}+3(-1)^{k+1} = 2(-1)^{k} + (-3)(-1)^{k} = (-1)(-1)^{k} = (-1)^{k+1}$. – John Omielan Feb 24 at 8:34
• Thank you. I was trying to find where to further simplify for a several minutes. I completely missed that expression after getting the common denominator. – Isaac Rodriguez Feb 24 at 9:00

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}

\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}