Proving $\sum_{i=1}^n 2^i = 2^{n+1} - 2$ using strong induction

Question

I just started learning proof by induction in class, but got a problem requiring proof by strong induction.

Here is the problem.

Prove by strong induction: $$\sum_{i=1}^n 2^i = 2^{n+1} - 2$$

I've done the base, showing that the statement holds for $n=1$, $n=2$, and $n=3$. (I won't show the simple math here). For $n=k$, the statement would be $2^{k+1}-2$. But that's where I get stuck, as I'm still trying to grasp the concept of strong induction.

For $n=k+1$, do I do the following and simplify?

$$\sum_{i=1}^{k+1} 2^i = \sum_{i=1}^k 2^i + 2^{(k+1)+1} - 2$$ $$=[2^{k+1}-2]+[2^{k+2}-2]$$ $$=\text{etc}\ldots?$$

Answer 1

For strong induction, a proof goes something like this:

Proof of a base case: here $n= 1$ will do:

$2 = 4 - 2$.

The only thing different between "strong" and "regular" induction is how we state the inductive step:

We assume that for ALL $n_0 \leq k < n$, the theorem holds, and then use that to show it holds for $k = n$. This means we have access to ANY previous non-negative integer $k$ in that range, not just "the previous integer", $n-1$.

In this case, that means we can assume the result for all $1 \leq k < n$.

Of course, since $k = n - 1 < n$, we can use that case, too.

So we have:

$\sum\limits_{i = 1}^n 2^i = \sum\limits_{i = 1}^{n-1} 2^i + 2^n = (2^n - 2) + 2^n = \dots ?$

Answer 2

Your calculation $$\sum_{i=1}^{k+1}2^i=\sum_{i=1}^{k}2^i+2^{(k+1)+1}-2$$ is false. What's true is that $$\sum_{i=1}^{k+1}2^i=\sum_{i=1}^k2^i+2^{k+1},$$ and $2^{k+1}\neq 2^{(k+1)+1}-2$ in general. You can apply the induction hypothesis to the first term on the right to get what you want, although this is normal induction, rather than strong induction.

Answer 3

We have to prove, $$\sum_{i=1}^{n}2^{i}=2^{n+1}-2$$ Step 1: Setting $n=1$ in the above equality, we get $$\sum_{i=1}^{1}2^{i}=2^{1+1}-2\iff 2=4-2\iff 2=2$$ hence it holds for $n=1$

Step 2: Assuming that it holds for $n=k$, we get $$\sum_{i=1}^{k}2^{i}=2^{k+1}-2$$

Step 3: Now, setting $n=k+1$ in the given equality, we get $$\sum_{i=1}^{k+1}2^{i}=2^{k+1+1}-2 $$$$\sum_{i=1}^{k}2^{i}+2^{k+1}=2^{k+2}-2$$ $$\sum_{i=1}^{k}2^{i}=2.2^{k+1}-2-2^{k+1}$$ $$\sum_{i=1}^{k}2^{i}=2^{k+1}-2$$ Which is true from (2), hence it holds for $n=k+1$

It is clear from (1), (2) & (3) that the given equality holds for all positive integers $\color{blue}{n\geq 1}$

Answer 4

Suppose $\sum_{i=1}^k 2^i = 2^{k+1} - 2 $ for all $k < n$.

Then, choose some $k$ with $1 < k < n$.

$\begin{array}\\ \sum_{i=1}^n 2^i &=\sum_{i=1}^k 2^i +\sum_{i=k+1}^n 2^i\\ &=2^{k+1} - 2 +2^k\sum_{i=k+1}^n 2^{i-k}\\ &=2^{k+1} - 2 +2^k\sum_{i=1}^{n-k} 2^{i}\\ &=2^{k+1} - 2 +2^k(2^{n-k+1}-2)\\ &=2^{k+1} - 2 +2^{n+1}-2^{k+1}\\ &=2^{n+1} - 2 \\ \end{array} $

This is the only way I could think of to use strong induction.