Prove that $\binom nk=\sum_{j=0}^{\lfloor\frac k2\rfloor}(-1)^j\binom nj\binom{n+k-2j-1}{n-1}$

Question

Prove combinatorially (using inclusion-exclusion) that$ \binom nk=\sum_{j=0}^{\lfloor\frac k2\rfloor}(-1)^j\binom nj\binom{n+k-2j-1}{n-1}$ Hi, everyone. I'm at a loss here. I've been trying to figure out what is being counted here for literally 4 hours. I've learned some things in the meantime, but the minus 2j term confuses me.

I see that we are starting with the j=o set and filtering out some union of other sets. I have been looking for a way to embed subsets from the LHS into subsets count in the first term on the RHS. But no luck. Are we trimming elements from the sides of the n-1 element subsets of the n+k -1 element set that our k element subsets of an n element set are being somehow mapped into? I only ask what is being counted or a hint in that direction. I'm more than willing to complete the details of the proof. I like this stuff, but this one beats ne. Thanks in advance for any help.

Answer 1

It may help to write out a few terms of the sum

$$\sum_{j=0}^{\lfloor k/2\rfloor}(-1)^j\binom{n}j\binom{n+k-2j-1}{n-1}\;,$$

to get

$$\binom{n}0\binom{n+k-1}{n-1}-\binom{n}1\binom{n+k-3}{n-1}+\binom{n}2\binom{n+k-5}{n-1}-+\ldots\;.$$

The binomial coefficient $\binom{n+k-1}{n-1}$ is recognizable as the number of ways to distribute $k$ indistinguishable stones amongst $n$ distinguishable boxes. Extending that idea to the other terms, we see that $\binom{n+k-3}{n-1}$ is the number of ways to distribute $k-2$ indistinguishable stones amongst $n$ distinguishable boxes, and in general $\binom{n+k-2j-1}{n-1}$ is the number of ways to distribute $k-2j$ indistinguishable stones amongst $n$ distinguishable boxes.

If this isn’t quite enough of a push, I’ve gone further in the spoiler-protected block below.

Let’s start with the first term: $\binom{n}0\binom{n+k-1}{n-1}=\binom{n+k-1}{n-1}$ is the number of ways to distribute the $k$ stones amongst the $n$ boxes. The ways that have at most one stone in each box correspond exactly to the $k$-element subsets of the $n$ boxes, so to get $\binom{n}k$ we need to subtract the distributions that have more than one stone in some box. If we put two stones into one of the boxes, we have $k-2$ stones left to distribute, and we can still distribute them amongst all $n$ boxes. The distribution can be done in $\binom{n+(k-2)-1}{n-1}=\binom{n+k-3}{n-1}$ ways, and there are $\binom{n}1$ ways to choose the overfilled box, so to a first approximation there are $\binom{n}1\binom{n+k-3}{n-1}$ distributions to be thrown away, leaving us with $\binom{n}0\binom{n+k-1}{n-1}-\binom{n}1\binom{n+k-3}{n-1}$ distributions. Unfortunately, any distribution that has two or more stones in each of two boxes has now been subtracted twice, once for each of the boxes, so we have to add those distributions back in. I’ll leave the rest to you.

Answer 2

By way of enrichment permit me to present an algebraic proof.

Suppose we seek to verify that $${n\choose k} = \sum_{j=0}^{\lfloor k/2\rfloor} (-1)^j {n\choose j} {n+k-2j-1\choose n-1}.$$ where $0\le k\le n.$

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

Observe carefully that this integral is zero when $2j\ge k+1$ so it controls the range and we may extend the sum from $\lfloor k/2\rfloor$ to $n.$

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