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.

  • 4
    $\begingroup$ 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. $\endgroup$ – Mike Earnest Dec 25 '18 at 17:18
  • $\begingroup$ 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$. $\endgroup$ – Will Orrick Dec 26 '18 at 1:05

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.




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


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.