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


2 Answers 2


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, 2015 at 23:36
  • $\begingroup$ @Csci319: Can you be a little more specific about what’s confusing you? $\endgroup$ Mar 4, 2015 at 23:38
  • $\begingroup$ why does it end at 1? $\endgroup$
    – Csci319
    Mar 4, 2015 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, 2015 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$ Mar 4, 2015 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, 2015 at 23:27
  • $\begingroup$ check it one more time, there's something just a bit off. $\endgroup$
    – jchun
    Mar 4, 2015 at 23:29
  • $\begingroup$ I do not see what is wrong $\endgroup$
    – Csci319
    Mar 4, 2015 at 23:36

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .