Discrete Math-Proof by Induction

Question

Could someone please check my work and see if this is correct? Thanks. For all integers $n \geq 1$, prove the following statement using mathematical induction. $$1+2^1+2^2+...+2^n = 2^{n+1}- 1$$ 1) Base Step:

$$n = 0: 2^0=2^{0+1}-1 = 1$$

2) Inductive Hypothesis: Assume that any non-negative integer $n$ that $1+2^1+2^2…2^n=2^{n+1}-1$

3) We must show that $1+2^1+2^2…+2^{n+1} = 2^{n+1}-1$

4) Proof: \begin{align*} 1+2^1+2^2…2^n & = 2^{n+1}-1\\ & = 2^{n+1}-1 + 2^{n+1}\\ & = 2(2^{n+1})-1\\ & = 2^{n+1} -1 \end{align*}

Answer 1

There are several mistakes:

1. Your base step should be from $n=1$.

2. In step 3), right hand side should be $2^{n+2}-1$.

3. You should start from the left hand side of step 3, using your assumption in 2, try to derive the right hand side. Please try again.

Answer 2

I am going to prove something more general (note that your specific problem will be solved by taking $r=2$ in the scenario I consider).

Problem: Let $a,r\in\mathbb{R}$ with $a\neq 0$ and $r\neq 1$. Then for each integer $n\geq 1$, $$ a+ar+ar^2+\cdots+ar^n=a\frac{r^{n+1}-1}{r-1}. $$

Solution. Fix $r\in\mathbb{R}, r\neq -1$, and let $S(n)$ denote the following statement for $n\geq 1$: $$ S(n) : 1+r+r^2+\cdots+r^n=\frac{r^{n+1}-1}{r-1}. $$ It is sufficient to prove that $S(n)$ holds for each $n\geq 1$; that is, it is sufficient to consider only $a=1$. For $r=0$, we note that $S(n)$ becomes $1=1$. Thus, assume, without loss of generality, that $r\neq 0$.

Base step ($n=1$:) For $S(1)$, we have that $1+r=\frac{r^2-1}{r-1}$, and this is true since $r^2-1=(r+1)(r-1)$ and $r\neq 1$.

Inductive step ($S(k)\to S(k+1)$): Fix some $k\geq 1$ and suppose that $S(k)$ holds; that is, assume $$ S(k) : 1+r+r^2+\cdots+r^k=\frac{r^{k+1}-1}{r-1} $$ is true. In order to complete the inductive step, we must show that $$ S(k+1) : 1+r+r^2+\cdots+r^k+r^{k+1}=\frac{r^{k+2}-1}{r-1} $$ follows. Starting with the left-hand side of $S(k+1)$, \begin{align} 1+r+r^2+\cdots+r^k+r^{k+1}&=\frac{r^{k+1}-1}{r-1}+r^{k+1}\tag{by $S(k)$}\\[1em] &= \frac{r^{k+1}-1}{r-1}+\frac{r^{k+1}(r-1)}{r-1}\\[1em] &= \frac{r^{k+1}-1+r^{k+1}(r-1)}{r-1}\\[1em] &= \frac{r^{k+1}-1+r^{k+2}-r^{k+1}}{r-1}\\[1em] &= \frac{r^{k+2}-1}{r-1}, \end{align} we see that the right-hand side of $S(k+1)$ follows. Thus, $S(k)\to S(k+1)$, completing the inductive step.

By mathematical induction, $S(n)$ is true for all $n\geq 1$.

---

For your problem specifically, consider $S(n)$ where $r=2$.

Answer 3

You need to start with base step $n = 1$.

Then, yes, you assume that for $n = k$, $$1 + 2^1 + 2^2 +\cdots + 2^k = 2^{k+1} - 1\tag{Inductive Hypothesis (IH)}$$

Now we aim to show that $$(IH) \implies 1 + 2^1 + 2^2 + \cdots + 2^k + 2^{k+1} = 2^{k+2}-1$$

---

$$\begin{align}\color{blue}{(1 + 2^1 + 2^2 +\cdots + 2^k)} + 2^{k+1}& = \color{blue}{(2^{k+1} - 1)} + 2^{k+1} \tag{Inductive step}\\ &= 2(2^{k+1}) - 1 \\ &= 2^{k+1+1} - 1 \\ & = 2^{k+2} - 1 \end{align}$$

And we are done. We have shown that $(IH) \implies 1 + 2^1 + 2^2 + \cdots + 2^k + 2^{k+1} = 2^{k+2}-1$, and hence, together with (the correct) base step verified, we have proven $1 + 2^1 + 2^2 +\cdots + 2^n = 2^{n+1}-1$.