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?$$
 A: 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 ?$
A: 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.
A: 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.
A: 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}$
