Proving identity for binomial coefficient using generating funtion

Question

I am trying to show that $$\sum_{k=0}^n (-1)^k \binom{n}{k} \binom{nx-kx}{n+1} = n x^{n-1} \binom{x}{2}.$$ By using $(1+x)^n(1+x)^n = (1+x)^{2n}$ and $(1+x)^n(1-x)^n = (1-x^2)^n$ and generating functions, I already showed that $$\sum_{k=0}^n \binom{n}{k}^2 = \binom{2n}{n}\quad\text{and}\quad \sum_{k=0}^n (-1)^k \binom{n}{k}^2 = \begin{cases} (-1)^m \binom{2m}{m},&\text{for } n=2m, \\ 0,&\text{else}. \end{cases}$$ So I think there has to be a similiar method to show the first identity, but I am failing at finding it because of having the index in the upper part of $\binom{nx-kx}{n+1}$. Does someone have an idea, how to get rid of it?

Answer 1

We use the coefficient of operator $[z^n]$ to denote the coefficient of a series. This way we can write for instance \begin{align*} [z^q](1+z)^n=\binom{n}{q}\tag{1} \end{align*}

We obtain \begin{align*} \color{blue}{\sum_{k=0}^n}&\color{blue}{ (-1)^k \binom{n}{k} \binom{nx-kx}{n+1}}\\ &=\sum_{k=0}^n(-1)^{n-k}\binom{n}{k}\binom{kx}{n+1}\tag{2}\\ &=\sum_{k=0}^{n}(-1)^{n-k}\binom{n}{k}[z^{n+1}](1+z)^{kx}\tag{3}\\ &=[z^{n+1}]\left(\left(1+z\right)^x-1\right)^n\tag{4}\\ &=[z^{n+1}]\left(\sum_{j=1}^x\binom{x}{j}z^j\right)^n\tag{5}\\ &=[z]\left(\sum_{j=0}^{x-1}\binom{x}{j+1}z^j\right)^n\tag{6}\\ &\,\,\color{blue}{=nx^{n-1}\binom{x}{2}}\tag{7} \end{align*} and the claim follows.

Comment:

• In (2) we change the order of summation $k\to n-k$.

• In (3) we apply the coefficient of operator according to (1).

• In (4) we use the linearity of the coefficient of operator and apply the binomial theorem.

• In (5) we apply the binomial theorem again.

• In (6) we shift the index to start with $j=0$ and factor out $z^n$ applying the rule $[z^p]z^qA(z)=[z^{p-q}]A(z)$.

• In (7) we note that in order to select the coefficient of $z$ in (6) we have to take $j=1$ once and $j=0$ for the other $(n-1)$ factors. This we do $n$ times.

Answer 2

Here is a simple combinatorial proof.

Imagine an $n\times x$ grid of objects. Both sides of the equation are answers to the question "How many ways are there to select $n+1$ objects from this grid so that every each has at least one selected object?"

On the one hand, $\sum_{k=0}^n (-1)^k \binom{n}{k} \binom{nx-kx}{n+1}$ answers this question using the principle of inclusion-exclusion. Take all $\binom{nx}{n+1}$ ways to select $n+1$ objects from the grid, then for each row, subtract away the $\binom{nx-x}{n+1}$ selections which miss that row. Then add back, for each pair of rows, the $\binom{nx-2x}{n+1}$ selections which miss both those rows, and so on.

On the other hand, if every row is covered, then there must exist exactly one row with two objects selected, while each other row has exactly one object selected. There are $n$ ways to choose the row with two objects selected, $\binom x2$ ways to choose the two objects from that row, then $x^{n-1}$ ways to select the objects from the remaining rows.