Now you are in the subtree of Test Flight Problem Set project.

# Problem #7

Question: prove that for any natural number $n$,
$$2 + 2^2 + 2^3 + ... + 2^n = 2^{n+1} - 2$$

Claim: $(\forall n \in {N})(2 + 2^2 + 2^3 + ... + 2^n = 2^{n+1} - 2)$

Proof: let's prove it by induction.

Initial step: $n=1$, $A(1)=2^1=2^2-2 = 2$. The claim is true for initial step, because both sides equal $2$.

Induction step: suppose $A(n)$ and deduce $A(n) \Rightarrow A(n+1)$. Let's add $2^{n+1}$ to the both sides of identity and we will get:
\begin{align} 2 + 2^2 + 2^3 + ... + 2^n + 2^{n+1} & = 2^{n+1} - 2 + 2^{n+1} \\ & = 2 \cdot 2^{n+1} - 2 \\ & = 2^{n+2} - 2 \end{align}
which is the identity with $n+1$ in place of $n$. By the principle of mathematical induction, the identity holds for all $n$. $\blacksquare$