$\sum_{k=0}^n \binom{n}{k}\frac{(-1)^k}{k!}(k+m)!=0$.

Question

I am working on showing an integral is zero, and I have simplified to the following for $m<n$. $\sum_{k=0}^n \binom{n}{k}\frac{(-1)^k}{k!}(k+m)!$.

From the few test cases I have done, the sum above always seems to be zero. How can I show it is zero for $m<n$? What will it be when $m=n$?

Answer 1

Hint:

$$\sum_{k=0}^n\binom{n}{k}\frac{(-1)^k(k+m)!}{k!}=m!\sum_{k=0}^n\binom{n}{k}\binom{k+m}{m}(-1)^k$$ $$=m![x^m]\sum_{k=0}^n\binom{n}{k}(1+x)^{k+m}(-1)^k$$

Where $[.]$ denotes the Coefficient operator. Can you proceed hereon?

Answer 2

Here is a combinatorial proof why $$ \sum_{k=0}^n \binom{n}{k}\frac{(-1)^k}{k!}(k+m)!=(-1)^nm!\sum_{k=0}^n(-1)^k\binom{n}{k}\binom{m+n-k}{m}=0 $$ Specifically, we prove $$ \sum_{k=0}^n(-1)^k\binom{n}{k}\binom{m+n-k}{m}=0\tag{$\star$} $$ The above summation is the answer to the following combinatorial question:

How many ways are there to put $m$ identical balls in $n+1$ distinct boxes, numbered $1$ to $n+1$, so that boxes numbered $1$ through $n$ are nonempty?

This can be seen using the principle of inclusion exclusion. The number of ways to put $m$ balls in $n+1$ distinct boxes is $\binom{m+n}m$, which can be seen by stars and bars. For each of boxes $1,\dots,n$, we must then subtract the placements where that box is empty. There are $\binom{n}1$ ways to choose the empty box, then $\binom{m+n-1}m$ ways to place the balls in the remaining boxes. However, we have doubly subtracted the placements with two empty boxes, so these must be added back in. Then the arrangements with three empty boxes must be subtracted out, and so on. Continuing this inclusion-exclusion argument results in the LHS of $(\star)$.

On the other hand, since $m<n$, there is no way for all of those boxes to be filled, so the number of ways is obviously $0$, the RHS of $(\star)$.

In general, this argument implies $$ \sum_{k=0}^n(-1)^k\binom{n}{k}\binom{m+n-k}{m}=\binom{n}{m} $$ because in order to place $m$ balls in $n+1$ boxes so boxes $1$ through $n$ are nonempty, you first place one ball in each of the first $n$ boxes, then place the remaining $m-n$ balls in the $n+1$ boxes in $\binom{m}n$ ways. Therefore, $$ \boxed{\sum_{k=0}^n \binom{n}{k}\frac{(-1)^k}{k!}(k+m)!=(-1)^nm!\binom{n}m.} $$ This lets you handle the $m=n$ case, and more.