My question is:

show $$\sum_{k=0}^{m} \binom{n-k}{m-k}=\binom{n+1}{m}$$ $$n\geq m\geq 1$$ I tried to do this via induction and failed. there has to be another way of doing this.

We could either explain combinatorically that we are counting the same thing in 2 different ways, in this sense, we are counting the number of ways to choose $m$ elements from a set with $n+1$ elements.

Or we could try like me to prove it algebraically, both ways are valid...I'd like some help, or a push in the right direction.


marked as duplicate by Najib Idrissi, Jack D'Aurizio, Johanna, Jonas Meyer, HK Lee Apr 9 '15 at 3:03

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.


Hint: The right side counts the number of ways to pick $m$ elements out of $n+1$.

For the left: partition the $m$-element subsets of $n+1$ based on the highest element that is NOT included in the subset.

  • $\begingroup$ I'm not sure I understood you. You want me to partition the big set (of $n+1$ elements) to different sets of $m$ elements based on the highest element that isn't in the subset? I don't follow. $\endgroup$ – Oria Gruber Jan 19 '14 at 19:51
  • $\begingroup$ @OriaGruber Not at all. I want you to partition the collection of $m$-element subsets of $\{1,2,\ldots,n+1\}$ based on the highest absent element. Then the size of the full collection is the sum of the size of these parts... $\endgroup$ – Nick Peterson Jan 19 '14 at 19:54
  • $\begingroup$ if the highest element that is not used is $n-k$, then all the elements $\{n-k+1,...n+1\}$ are used. That's $k+1$ elements. that means that from the set $\{1,2,...n-k-1\}$ we use only $m-(k+1)$ elements $\endgroup$ – Oria Gruber Jan 19 '14 at 19:57
  • 1
    $\begingroup$ @OriaGruber Right. Now, to fix things a little bit, say that the highest element not used is $n+1-k$. Then $k$ is between $0$ (meaning that we don't use element $n+1$) and $m$ (meaning that we use all $m$ elements greater than $n+1-m$, and no others). For a given value of $k$, we use elements $n+1-k+1,\ldots,n+1$ ($k$ total), don't use element $n+1-k$, and have to use $m-k$ from $\{1,2,\ldots,n-k\}$. So... $\endgroup$ – Nick Peterson Jan 19 '14 at 20:00
  • $\begingroup$ yeah I understand now :) if $n-k$ is the largest value not used, that means $\{n-k+1,...,n+1\}$ are all used and there's no choice involved. However, now we need to choose $m-(k+1)$ elements from $\{1,2,...,n-k-1\}$ and for that I have $\binom{n-k-1}{m-k-1}$ options. since we took arbitrary such highest absent value, the sum of all of those (for all absent values) is the number of ways to choose m out of n+1. $\endgroup$ – Oria Gruber Jan 19 '14 at 20:03

As has already been suggested, this is nothing else than Pascal's rule applied recursively m times:

$${n+1\choose m}=\underbrace{n\choose m}_{k=0}+{n\choose m-1}=\underbrace{{n\choose m}+{n-1\choose m-1}}_{\begin{align}\text{The first terms of our series,}\\\text{for k=0 and k=1}\quad\end{align}}+{n-1\choose m-2}=\ldots=\sum_{k=0}^m{n-k\choose m-k}$$

  • $\begingroup$ @barto: Same here. I suspect the site is currently undergoing some technical difficulties. $\endgroup$ – Lucian Apr 8 '15 at 16:24
  • $\begingroup$ @barto: Better now ? $\endgroup$ – Lucian Apr 8 '15 at 16:42

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