# Show $\sum_{k=0}^{m} \binom{n-k}{m-k}=\binom{n+1}{m}$ [duplicate]

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 LeeApr 9 '15 at 3:03

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.

• 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. – Oria Gruber Jan 19 '14 at 19:51
• @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... – Nick Peterson Jan 19 '14 at 19:54
• 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 – Oria Gruber Jan 19 '14 at 19:57
• @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... – Nick Peterson Jan 19 '14 at 20:00
• 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. – 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}

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