Prove this identity with a combinatorial argument

Question

Prove that for all integers $j,k,n, k \ge 0$, we have

$$ \sum\limits_{i=0}^n ({-1})^{n-i} \binom {n}{i} \binom {ki}{j} = \begin{cases} 0, & \text{if } 0 \le j < n; \\ k^n, & \text{if } j = n. \end{cases} $$

The alternating sum suggests use of inclusion-exclusion principle, but I am unable to setup a situation. The sum becomes 0 which is strange for me. How do you incorporate that. Using inclusion -exclusion for counting something like surjective functions always we count something.

I am trying to learn combinatorics, so would prefer a combinatorial argument.

Answer 1

Consider $n$ groups of $k$ objects. The quantity ${n\choose i}{ki\choose j}$ represents the number of ways to choose $i$ of the groups, then select $j$ objects from the chosen groups. By inclusion-exclusion, the left hand side is the number of ways to choose $j$ objects total from a collection of $n$ groups of $k$ objects, such that each group has at least one object selected from it. It is not hard to see the right hand side counts the same thing.

Answer 2

This problem also has an algebraic proof which I submit for enrichment. Suppose we seek to evaluate

$$\sum_{q=0}^n (-1)^{n-q} {n\choose q} {kq\choose j}.$$

We introduce

$${kq\choose j} = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{j+1}} (1+z)^{kq} \; dz.$$

With $j$ non-negative this integral correctly represents the binomial coefficient and vanishes when $j$ is out of range. We then get for the sum

$$\frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{j+1}} \sum_{q=0}^n {n\choose q} (-1)^{n-q} (1+z)^{kq} \; dz \\ = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{j+1}} (-1+(1+z)^k)^n \; dz.$$

This is

$$[z^j] \left({k\choose 1}z + {k\choose 2}z^2 + \cdots + {k\choose k}z^k\right)^n.$$

The first power of $z$ that occurs here is $z^n$ so the value is zero for $j\lt n.$ Moreover the coefficient on $z^n$ can only be achieved in one way, namely by taking the first term of the sum being exponentiated. This has coefficient $k$ so the answer for $j=n$ is $$k^n.$$

Remark. We can use this technique for larger values of $j.$ For example we get for $j=n+2$ the result

$${n\choose 1} k^{n-1} {k\choose 3} + {n\choose 2} k^{n-2} {k\choose 2}^2.$$