"Prove ${{n+1}\choose{m+1}} = \sum_{k=m}^{n}{k \choose m}$ by repeatedly using the Pascal Identity ${{n+1} \choose {m+1}}={{n} \> \choose {m+1}} + {n \choose m}$"

I don't know how to start this problem. I know the version of Pascal's Identity has a 1 added to the identity. Am I just supposed to plug ${k \choose m}$ in the identity and repeat using the result?


You can use repeatedly the Pascal identity, having in mind that $n=(n-1)+1$. We have:

\begin{align*} \binom{n+1}{m+1}&=\binom{n}{m}+\binom{n}{m+1}=\binom{n}{m}+\binom{[n-1]+1}{m}\\ &=\binom{n}{m}+\binom{n-1}{m}+\binom{n-1}{m+1}=\binom{n}{m}+\binom{n-1}{m}+\binom{[n-2]+1}{m+1}\\ &\\ &=\vdots\\ &\\ &=\binom{n}{m}+\binom{n-1}{m}+\binom{n-2}{m}+\cdots+\binom{m+2}{m}+\binom{m+1}{m}+\underbrace{\binom{m+1}{m+1}}_{=1}\\ &=\binom{n}{m}+\binom{n-1}{m}+\binom{n-2}{m}+\cdots+\binom{m+2}{m}+\binom{m+1}{m}+\underbrace{\binom{m}{m}}_{=1}\\ &=\sum_{k=m}^n \binom{k}{m} \end{align*}

  • $\begingroup$ Thank you! I wasn't expecting a full answer but I appreciate it. I am a bit confused as to why $n = (n - 1) + 1$ though. $\endgroup$ – Qwurticus Nov 9 '16 at 23:41
  • $\begingroup$ Do you really have no idea why $n=(n-1)+1$? $\endgroup$ – Darío G Nov 9 '16 at 23:42

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.