gaby131o

2022-09-23

Algebraic Proof that $\sum _{i=0}^{n}\left(\genfrac{}{}{0}{}{n}{i}\right)={2}^{n}$

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}.$

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.

Do you have a similar question?