Proving $\sum_{i=1}^n 2^i = 2^{n+1} - 2$ using strong induction 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?$$
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 &lt; 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 &lt; n$.

Of course, since $k = n - 1 &lt; 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 ?$
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) &amp; (3) that the given equality holds for all positive integers $\color{blue}{n\geq 1}$