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


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


Your induction hypothesis is that


and you want to prove that


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.

  • $\begingroup$ i am a little confused now $\endgroup$ – Csci319 Mar 4 '15 at 23:36
  • $\begingroup$ @Csci319: Can you be a little more specific about what’s confusing you? $\endgroup$ – Brian M. Scott Mar 4 '15 at 23:38
  • $\begingroup$ why does it end at 1? $\endgroup$ – Csci319 Mar 4 '15 at 23:39
  • $\begingroup$ So I understand Coefficients of $(x + y)^n$ using the pascal's. I just do not understand how to apply it to this proof $\endgroup$ – Csci319 Mar 4 '15 at 23:42
  • $\begingroup$ @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. $\endgroup$ – 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$.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.