Prove that $\forall n \in \mathbb Z^{+}$ $$2^n=\sum_{i=0}^{n}{n \choose i} $$
It seems like something that should be done by induction, but trying that way I get
Let P(n) be the property that $2^n=\sum_{i=0}^{n}{n \choose i} $. Clearly P(1) is true because $\sum_{i=0}^{1}{1 \choose i}={1 \choose 0} + {1 \choose 1}=1+1=2=2^1 $. Then suppose P(k) is true for some k. That is that $2^k=\sum_{i=0}^{k}{k \choose i} $. We need to show that P(k+1) is true. That is we will show that $2^{k+1}=\sum_{i=0}^{k+1}{k+1 \choose i} $. So, $$\sum_{i=0}^{k+1}{k+1 \choose i}={k+1 \choose k+1}+\sum_{i=0}^{k}{k \choose i} $$ $$= {\frac {(k+1)!}{k!(k+1)!}} + 2^k$$ $$={\frac {1}{k!}}+2^k$$
and I don't know where to go from there.
Hint:
You don't need an inductive proof here: rewrite $2^n=(1+1)^n$ and use the binomial formula.