Proof that $\sum_{i=0}^n 2^i = 2^{n+1} - 1$ $\sum_{i=0}^n 2^i = 2^{n+1} - 1$
I can't seem to find the proof of this. I think it has something to do with combinations and Pascal's triangle. Could someone show me the proof? Thanks

We give a combinatorial interpretation.
We are counting the "words" of length $n+1$, over the alphabet $\{0,1\}$, that are not all $0$'s. There are $2^{n+1}-1$ such words. 
We count these words another way. Maybe the first $1$ is at the beginning. There are $2^n$ such words.
Maybe the word begins with $01$. There are $2^{n-1}$ such words. 
Maybe the word begins with $001$. There are $2^{n-2}$ such words.
And so on. Finally, maybe the first $1$ is at the right end. There are $2^0$ such words.
So the total number of words of length $n+1$ that are not all $0$'s is $2^n+2^{n-1}+2^{n-2}+\cdots +2^0$. This is our given sum, backwards. 
