Principles of Mathematical Induction

Question

Using the principles of mathematical induction prove:

$$\frac{1}{2}+\frac{1}{4}+\frac{1}{8}+ ...+\frac{1}{2^n}=\frac{2^n-1}{2^n}$$ for $n > 0$ and $n \in \mathbb N$

My attempt:

Let the statement $P(n)$ be: $$\frac{1}{2}+\frac{1}{4}+\frac{1}{8}+ ...+\frac{1}{2^n}=\frac{2^n-1}{2^n}$$

STEP 1: We first show that $P(1)$ is true.

Left Hand Side = $$\frac{1}{2}$$

Right Hand Side = $$\frac{2^1-1}{2^1} = 1/2$$

Both sides of the statement are equal hence $P(1)$ is true.

STEP 2: We now assume that $P(k)$ is true.

$$\frac{1}{2}+\frac{1}{4}+\frac{1}{8}+ ...+\frac{1}{2^k}=\frac{2^{k+1}-1}{2^{k+1}}$$

$$=\frac{1}{2}+\frac{1}{4}+\frac{1}{8}+ ...+\frac{1}{2^k}+2^{k+1}=\frac{2^{k+1}-1}{2^{k+1}}$$

$$=\frac{2^{k+1}-1}{2^{k+1}}=\frac{2^{k+1}-1}{2^{k+1}}$$

$$=2^{k+1}-1 + k+1 = 2^{k+1}-1$$

Hence, $$\frac{1}{2}+\frac{1}{4}+\frac{1}{8}+ ...+\frac{1}{2^n}=\frac{2^n-1}{2^n}$$

Is my attempt correct?

Answer 1

Your base case looks fine, but I am very confused about your induction step. First off, I don't understand how one line relates to the next (are these implications? or, as you have written, equalities?). Second, I don't follow the argument at all. If I were writing it up, I would likely do the following:

For induction, suppose that $$ \frac{1}{2} + \frac{1}{4} + \dotsb + \frac{1}{2^n} = \frac{2^k-1}{2^k}. \tag{IH}$$ This statement, labeled (IH) is the induction hypothesis. Then \begin{align} \frac{1}{2} + \frac{1}{4} + \dotsb + \frac{1}{2^{k+1}} &= \underbrace{\frac{1}{2} + \frac{1}{4} + \dotsb + \frac{1}{2^k}}_{\text{right-hand side of (IH)}} + \frac{1}{2^{k+1}} \\ &= \frac{2^{k}-1}{2^k} + \frac{1}{2^{k+1}} && (\text{by the induction hypothesis}) \\ &= \frac{2^{k}-1}{2^k}\cdot\color{red}{\frac{2}{2}} + \frac{1}{2^{k+1}} && (\text{to get a common denominator}) \\ &= \frac{2^{k+1} - 2}{2^{k+1}} + \frac{1}{2^{k+1}} \\ &= \frac{2^{k+1} - 1}{2^{k+1}}. \end{align} Therefore if (IH) holds, then $$ \frac{1}{2} + \frac{1}{4} + \dotsb + \frac{1}{2^{k+1}} = \frac{2^{k+1} - 1}{2^{k+1}}, $$ which completes the induction proof.$\tag*{$\square$}$

---

Alternatively, if you wish to start with an identity and manipulate that, you could assume (IH), then work as follows:

\begin{align*} &\frac{1}{2} + \frac{1}{4} + \dotsb + \frac{1}{2^k} = \frac{2^k-1}{2^{k+1}} \\ &\qquad\implies \frac{1}{2} + \frac{1}{4} + \dotsb + \frac{1}{2^k} \color{red}{+ \frac{1}{2^{k+1}}} = \frac{2^k-1}{2^{k+1}} \color{red}{+ \frac{1}{2^{k+1}}} = \frac{2^{k+1} - 1}{2^k}, \end{align*} where the last equality follows from the same argument as above. In any event, this also gives the proof.

Answer 2

Step 2: Assume that the formula is correck for $n=k$ and show that the formula will work for $n=k+1$. Thus, we assume that $$\frac{1}{2}+\frac{1}{4}+\frac{1}{8}+ ...+\frac{1}{2^k}=\frac{2^k-1}{2^k}$$ $$\frac{1}{2}+\frac{1}{4}+\frac{1}{8}+ ...+\frac{1}{2^{k+1}}=\frac{1}{2}+\frac{1}{4}+\frac{1}{8}+ ...+\frac{1}{2^k}+\frac{1}{2^{k+1}}=\frac{2^k-1}{2^k}+\frac{1}{2^{k+1}}=\frac{2\cdot 2^k-2+1}{2^{k+1}}=\frac{2^{k+1}-1}{2^{k+1}}$$

Answer 3

Actually, the part $\frac{1}{2}+\frac{1}{4}+\frac{1}{8}+ ...+\frac{1}{2^k}=\frac{2^{k+1}-1}{2^{k+1}}$ is incorrect, because $LHS=P(k)$ but $RHS=P(k+1)$.

Here's how you can continue:

Assume that $P(k)=\frac{1}{2}+\frac{1}{4}+\frac{1}{8}+ ...+\frac{1}{2^k}=\frac{2^{k}-1}{2^{k}}$ (not $2^{k+1}$)

We will have $P(k+1)=\frac{1}{2}+\frac{1}{4}+\frac{1}{8}+ ...+\frac{1}{2^k}+\frac{1}{2^k+1}=\frac{2^{k}-1}{2^{k}}+\frac{1}{2^{k+1}}=\frac{2^{k+1}-2}{2^{k+1}}+\frac{1}{2^{k+1}}=\frac{2^{k+1}-1}{2^{k+1}}$

The proof can be easily finished from there.

Answer 4

I can't follow your reasoning.

$$\frac{1}{2}+\frac{1}{4}+\frac{1}{8}+ ...+\frac{1}{2^k}=\frac{2^{k+1}-1}{2^{k+1}}\text{(index off by } 1)$$

$$=\frac{1}{2}+\frac{1}{4}+\frac{1}{8}+ ...+\frac{1}{2^k}+2^{k+1}=\frac{2^{k+1}-1}{2^{k+1}}\text{(Not true)}$$

$$=\frac{2^{k+1}-1}{2^{k+1}}=\frac{2^{k+1}-1}{2^{k+1}} \text{(True, but where does it comes from)}$$

$$=2^{k+1}-1 + k+1 = 2^{k+1}-1 \text{(Not true)}$$

Correction:

We assume $P(k)$ is true, that is

$$\frac{1}{2}+\frac{1}{4}+\frac{1}{8}+ \ldots+\frac{1}{2^k}=\frac{2^{k}-1}{2^{k}}$$

What we want to show is $P(k+1)$,

$$\frac{1}{2}+\frac{1}{4}+\frac{1}{8}+ \ldots+\frac{1}{2^{k+1}}=\frac{2^{k+1}-1}{2^{k+1}}$$

Start from LHS of $P(k+1)$, try to reach RHS of $P(k+1)$.

$$\frac{1}{2}+\frac{1}{4}+\frac{1}{8}+ \ldots+\frac{1}{2^{k+1}}=\frac{2^{k}-1}{2^{k}}+\frac{1}{2^{k+1}}$$

Try to simplify the expression to get RHS of $P(k+1)$.