Find a Closed form for the Combinatorial Sum $\sum_{k=0}^m\binom{n-k}{m-k} $ and Provide a Combinatorial Proof of the Result

Question

Question Find a closed form for the combinatorial sum $\sum_{k=0}^m\binom{n-k}{m-k} $ and provide a combinatorial proof of the resulting identity.

My attempt

I was able to find a closed form using the method of "snake-oil" but unable to provide a combinatorial proof. We claim that $$ \sum_{k=0}^m\binom{n-k}{m-k}=\binom{n+1}{m}\tag{0}. $$ Indeed note that (formally) $$ \begin{align} \sum_{m=0}^\infty\left(\sum_{k=0}^m\binom{n-k}{m-k}\right)z^m&=\sum_{k=0}^\infty\left(\sum_{m=k}^\infty\binom{n-k}{m-k}\right)z^m\tag{1}\\ &=\sum_{k=0}^\infty z^k\left(\sum_{u=0}^\infty\binom{n-k}{u}z^u\right)\\ &=\sum_{k=0}^\infty z^k(1+z)^{n-k}\tag{2}\\ &=(1+z)^n\sum_{k=0}^\infty\left(\frac{z}{1+z}\right)^k\\ &=(1+z)^n\frac{1}{1-\frac{z}{1+z}}=(1+z)^{n+1}.\tag{3} \end{align} $$ Taking the coefficient of $z^m$ from $(1+z)^{n+1}$ yields the result. In the above computation we interchanged summation in $(1)$, used the binomial thoerem in $(2)$ and used the formula for a geometric series in $(3)$.

My problem

The simplicity of the identity in $(0)$ (supposing I have not made any mistakes) suggests a combinatorial proof. Unfortunately, I have not been able to make much progress here. I don't know how to classify the $m$ element subsets of $[n+1]$ to obtain $(0)$.

Any help is appreciated.

Answer 1

In how many ways can you choose the m-element subsets of {1,...,n}? In ${n \choose m}$ ways. But you may also write this as (the number of ways to choose m-element subsets that contain n )+ (the ones that don’t contain n but contain (n-1) +(the number of subsets that contain neither n, nor n-1, but contain n-2) +...(keep going)+(the number of subsets that contain neither n, nor n-1,nor...,nor m+1) and this gives you ${n-1 \choose m} + {n-2 \choose m}+...+{m \choose m}$

This is the same identity as the one you need to prove once you note that ${n-k \choose m-k}={n-k \choose n-m}$ and change the order of sumation from m to 0 instead of 0 to m.

Answer 2

Lemma:

$$\binom{n}{k}=\binom{n}{n-k}$$

$$\binom{n}{k}=\frac{n!}{(n-k)!k!}=\binom{n}{n-k}=\frac{n!}{k!(n-k)!}$$ Proof:

$$\binom{n-k}{m-k}=\binom{n-k}{(n-k)-(m-k)}=\binom{n-k}{n-m}$$ Therefore, $$\sum_{k=0}^{m}\binom{n-k}{m-k}=\sum_{k=0}^{m}\binom{n-k}{n-m}$$ Notice that $$\sum_{k=0}^{m}\binom{n-k}{n-m}=\sum_{k=n-m}^{n}\binom{k}{n-m}$$ Using Hockey Stick identity $$\sum_{i=r}^{n}\binom{i}{r}=\binom{n+1}{r+1}$$ We have $$\sum_{k=0}^{m}\binom{n-k}{m-k}=\sum_{k=0}^{m}\binom{n-k}{n-m}=\sum_{k=n-m}^{n}\binom{k}{n-m}=\binom{n+1}{n+1-m}=\binom{n+1}{m}$$