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
 A: Let 
$$\tag1S=1+2+2^2+\cdots+2^n$$
Multiplying both sides by $2$,
$$\tag22S=2+2^2+2^3+\cdots+2^{n+1}$$
Subtracting $(1)$ from $(2)$,
$$S=2^{n+1}-1$$
This is a specific example of the sum of a geometric series. In general,
$$a+ar+ar^2+\cdots+ar^n=a\left(\frac{r^{n+1}-1}{r-1}\right)$$
A: Mathematical induction will also help you.


*

*(Base step) When $n=0$, $\sum_{i=0}^0 2^i = 2^0 = 1= 2^{0+1}-1$.

*(Induction step) Suppose that there exists $n$ such that $\sum_{i=0}^n 2^i = 2^{n+1}-1$. Then $\sum_{i=0}^{n+1}2^i=\sum_{i=0}^n 2^i + 2^{n+1}= (2^{n+1}-1)+2^{n+1}=2^{n+2}-1.$


Therefore given identity holds for all $n\in \mathbb{N}_0$.

Edit: If you want to apply combinations and Pascal's triangle, observe
\begin{align}
2^0&=\binom{0}{0}\\
2^1&=\binom{1}{0}+\binom{1}{1}\\
2^2&=\binom{2}{0}+\binom{2}{1}+\binom{2}{2}\\
2^3&=\binom{3}{0}+\binom{3}{1}+\binom{3}{2}+\binom{3}{3}\\
\vdots&=\vdots\\
2^n&=\binom{n}{0}+\binom{n}{1}+\binom{n}{2}+\binom{n}{3}+\cdots+\binom{n}{n}
\end{align}
Hockey stick identity says that
$$
\sum_{i=r}^n \binom{i}{r}=\binom{n+1}{r+1}.
$$
and so
\begin{align}
\binom{0}{0}+\binom{1}{0}+\cdots+\binom{n}{0}&=\binom{n+1}{1}\\
\binom{1}{1}+\binom{2}{1}+\cdots+\binom{n}{1}&=\binom{n+1}{2}\\
\binom{2}{2}+\binom{3}{2}+\cdots+\binom{n}{2}&=\binom{n+1}{3}\\
\vdots&=\vdots\\
\binom{n}{n}&=\binom{n+1}{n+1}
\end{align}
Add all terms, then we get
\begin{align}
\sum_{i=0}^n 2^i &= \sum_{i=1}^{n+1} \binom{n+1}{i}\\
&=\sum_{i=0}^{n+1}\binom{n+1}{i}-1\\
&=2^{n+1}-1.
\end{align}
A: 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. 
A: \begin{eqnarray}
2^{n+1} &=& 2^n+2^n \\
&=&2^n + 2^{n-1} + 2^{n-1} \\
&\vdots& \\
&=&  2^n + 2^{n-1} +2^{n-1} + \cdots + 2 +2 \\
&=&  2^n + 2^{n-1} +2^{n-1} + \cdots + 2 +1 + 1
\end{eqnarray}
A: Since you asked about Pascal's triangle:
Imagine filling in rows $0$ through $n$ of Pascal's triangle.  Now change the first position of row $0$ from $1$ to $1+1$.
Distribute the two ones to the following row, which should now read $1+1, 1+1$.  Distribute again to get $1+1,2+2,1+1$.  And so on.
When we get to row $n$, we will populate row $n+1$ as usual, and the sum of those numbers will equal the sum of the numbers we started with.
Since the sum of the elements in the $i$-th row of Pascal's triangle is $2^i$, we have shown that $1+ \sum_{i=0}^n 2^i = 2^{n+1}$.
