# Algebraic Proof that ∑_(i=0)^n (n i)=2^n

Algebraic Proof that $\sum _{i=0}^{n}\left(\genfrac{}{}{0}{}{n}{i}\right)={2}^{n}$
You can still ask an expert for help

• Questions are typically answered in as fast as 30 minutes

Solve your problem for the price of one coffee

• Math expert for every subject
• Pay only if we can solve it

gerasseltd9
Let $g\left(n\right)=\sum _{i=0}^{n}\left(\genfrac{}{}{0}{}{n}{i}\right)$. Then
$g\left(n+1\right)-g\left(n\right)=\sum _{i=0}^{n+1}\left(\genfrac{}{}{0}{}{n+1}{i}\right)-\sum _{i=0}^{n}\left(\genfrac{}{}{0}{}{n}{i}\right)=\sum _{i=0}^{n+1}\left(\left(\genfrac{}{}{0}{}{n+1}{i}\right)-\left(\genfrac{}{}{0}{}{n}{i}\right)\right)=\sum _{i=0}^{n+1}\left(\genfrac{}{}{0}{}{n}{i-1}\right)$
$=\sum _{i=0}^{n}\left(\genfrac{}{}{0}{}{n}{i}\right)=g\left(n\right).$
Here, we use the fact that $\left(\genfrac{}{}{0}{}{n}{n+1}\right)=\left(\genfrac{}{}{0}{}{n}{-1}\right)=0$, as well as the binomial recurrence $\left(\genfrac{}{}{0}{}{n+1}{i}\right)=\left(\genfrac{}{}{0}{}{n}{i}\right)+\left(\genfrac{}{}{0}{}{n}{i-1}\right)$.
Thus we have $g\left(n+1\right)=2g\left(n\right)$, with $g\left(0\right)=1$. Since $g\left(n\right)$ doubles each time $n$ is incremented by $1$, we must have
$g\left(n\right)=\sum _{i=0}^{n}\left(\genfrac{}{}{0}{}{n}{i}\right)={2}^{n}.$
###### Did you like this example?
Liam Potter
Simply use the binomial formula.
$\left(a+b{\right)}^{n}=\sum _{k=0}^{n}\left(\genfrac{}{}{0}{}{n}{k}\right){a}^{k}{b}^{n-k}$
With $a=b=1$ you have your result.