# Induction proof using Pascal's Identity: $\binom{n}{0}+\binom{n}{i}+…+\binom{n}{n}=2^n$

Prove by induction that for all $n ≥ 0$:

$\binom{n}{0}+\binom{n}{i}+....+\binom{n}{n}=2^n$

We should use pascal's identity

Base case: $n=0$

LHS: $\binom{0}{0}=1$

RHS: $2^0=1$

Inductive step: Here is where I am get held up. I know Pascal's Identity $\displaystyle\binom{n+1}{k+1}=\binom nk+\binom n{k+1}$ and I am looking to prove $n+1$

so do I want to prove : $\binom{k}{0}+\binom{k}{1}+....+\binom{k}{k}+\binom{n+1}{k+1}=2^{k+1}$?

$$\binom{n}0+\binom{n}1+\ldots+\binom{n}n=2^n\;,$$

and you want to prove that

$$\binom{n+1}0+\binom{n+1}1+\ldots+\binom{n+1}{n+1}=2^{n+1}\;.$$

Pascal’s identity allows you to write

\begin{align*}\binom{n+1}1&+\binom{n+1}2+\ldots+\binom{n+1}n\\ &=\left(\binom{n}0+\binom{n}1\right)+\left(\binom{n}1+\binom{n}2\right)+\ldots+\left(\binom{n}{n-1}+\binom{n}n\right)\\ &=\binom{n}0+2\binom{n}1+2\binom{n}2+\ldots+2\binom{n}{n-1}+\binom{n}n\;, \end{align*}

and $\dbinom{n+1}0=\dbinom{n+1}{n+1}=1$, so

\begin{align*}\binom{n+1}0&+\binom{n+1}1+\ldots+\binom{n+1}{n+1}\\ &=1+\binom{n}0+2\binom{n}1+2\binom{n}2+\ldots+2\binom{n}{n-1}+\binom{n}n+1\\ &=2\binom{n}0+2\binom{n}1+2\binom{n}2+\ldots+2\binom{n}{n-1}+2\binom{n}n\;. \end{align*}

And at that point you’re almost done.

• i am a little confused now – Csci319 Mar 4 '15 at 23:36
• @Csci319: Can you be a little more specific about what’s confusing you? – Brian M. Scott Mar 4 '15 at 23:38
• why does it end at 1? – Csci319 Mar 4 '15 at 23:39
• So I understand Coefficients of $(x + y)^n$ using the pascal's. I just do not understand how to apply it to this proof – Csci319 Mar 4 '15 at 23:42
• @Csci319: I left off the $\binom{n+1}0$ and $\binom{n+1}{n+1}$ because when you apply Pascal’s identity to them, you get $\binom{n}{-1}$ and $\binom{n}{n+1}$ (among other things), and I wasn’t sure whether you knew that those are defined to be $0$. If you do know that, I can simplify the calculation a little. However, I added them back in for the final calculation, so nothing was lost. \\ This argument has nothing to do with the use of binomial coefficients in the binomial theorem; all you need is Pascal’s identity. – Brian M. Scott Mar 4 '15 at 23:48

Well, you need to prove the case where $n = k + 1$. According to what you already have, your assumption is in terms of $k$.

• I changed my assumption – Csci319 Mar 4 '15 at 23:27
• check it one more time, there's something just a bit off. – jchun Mar 4 '15 at 23:29
• I do not see what is wrong – Csci319 Mar 4 '15 at 23:36