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

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}
