# 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 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.

• If you replace $m-k$ with $n-m$ on the left, and the $m$ on the right with $n-m$, then this becomes the hockey stick identity. – Mike Earnest Dec 25 '18 at 17:18
• Partition the set of subsets of $\{1,2,\ldots,n+1\}$ of size $m$ into $m+1$ parts $P_i$, $i\in\{0,1,\ldots,m\}$ where $P_i$ is the set of size-$m$ subsets whose least missing element is $i+1$. – Will Orrick Dec 26 '18 at 1:05

## 2 Answers

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.

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