Prove that $\sum\limits_{i=0}^n(-1)^i\binom{n}{i}\binom{kn-ki}{n-1}=0$

Question

Given $$\sum\limits_{i=0}^n(-1)^i \binom{n}{i}\binom{m-ik+n-1}{n-1}$$ (which can be interpreted as the number of solution sets to the equation $x_1+x_2+\cdots+x_n=m$ where $0≤x_i<k$), prove that $$\sum\limits_{i=0}^n(-1)^i\binom{n}{i}\binom{kn-ki}{n-1}=0$$ for all $k,m,n\in \mathbb{N}.$$

---

Does anyone have any hints on how to do this question? Am I still supposed to/can I even use a combinatorial interpretation? I can see where they got $$\sum\limits_{i=0}^n(-1)^i \binom{n}{i}\binom{m-ik+n-1}{n-1}$$, which is pretty much defining sets for $x_i≥k,$ (i.e., splitting all of the solution sets into two types based on ones with at least one $i$ having greater than $k$, then using the Principle of Inclusion-Exclusion to take the complement (like done here for a specific case in Example 2.1.4. I also tried to plug in numbers to turn this into a specific case, and interpret it in a combinatorial context (i.e., counting the number of ways to distribute $m=8$ balls into $n=3$ bins where each bin can only hold a max of $k<2$ balls. However, I can't see any way to get to the conclusion stated, and am truly stuck. I notice that the expression looks like the identity $$\sum\limits_{i=0}^n\binom ni(-1)^i$$ from the binomial theorem, but couldn't find a way to use it (don't even know if this can be used).

Answer 1

Suppose you have a collection of distinct balls, there being $k$ different colors of balls available, and there being $n$ balls of each of the colors, within each color they are labeled with numbers $1,2,3,\dots,n$

In how many ways can you select $n-1$ balls such that at least one number is absent?

Clearly, all ways of selecting $n-1$ balls would be such that a number were absent and so the count is $\binom{nk}{n-1}$

What if we were to do this by inclusion-exclusion however over the events "Number1 is absent", "Number2 is absent", ...

Suppose $i$ numbers are guaranteed absent. Choose the numbers to be absent in $\binom{n}{i}$ ways. With $i$ numbers absent, there remain $nk-ki$ balls without said numbers. Choose your $n-1$ balls from the remaining in $\binom{nk-ki}{n-1}$ ways.

$~$

We have then $\binom{nk}{k-1} = \sum\limits_{i=1}^n (-1)^{i+1}\binom{n}{i}\binom{nk-ki}{n-1}$ and by rearrangement we get the proposed identity.

Answer 2

Hint:

You are supposed to use the combinatorial interpretation to do this problem. There is an expression you can substitute for $m$ into the first expression, which will turn it into the second expression. This allows you to also interpret the second expression combinatorially. Looking at the combinatorial interpretation, it will be easy to see that there are zero ways to complete the task, thus proving that the second expression is $0$.

Solution:

In the first expression, let $m=(k-1)n+1$. The result is exactly the LHS of the second equation. Therefore, the LHS of the second equation is the number solutions to $x_1+\dots+x_n=(k-1)n+1$ with $0\le x_i<k$. However, there are clearly zero solutions to this system of equations and inequalities, as they imply $$x_1+\dots+x_n\le (k-1)+\dots+(k-1)=n(k-1),$$ contradicting the fact that the sum should equal $n(k-1)+1$. Since $0$ is the RHS of the second equation, we have proved the second equation.