Sum of product of binomial coefficients: $\sum_{k=0}^{n}(-1)^k\binom{n}{k}\binom{n + k}{k} = (-1)^n$

Based on the binomial expansion of $(1+x)^n$, show that:

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

This is a question from a very old high school exam paper I came across. It looks like it involes the product of two binomial expansions but I cannot figure this out. Any help much appreciated.

Solution 1:

If you write the equation to prove as $\sum_k(-1)^{n-k}\binom nk\binom{n+k}n=1$, you can interpret the left hand side as the result of applying the $n$-th finite difference operation $\Delta^n$ to the sequence $k\mapsto\binom kn$, and taking the term of the resulting sequence at $k=n$. Then $\Delta(k\mapsto\binom km)=k\mapsto\binom k{m-1}$ implies that the left hand side becomes $\Delta^n\left(k\mapsto\binom kn\right)(n)=\binom n{n-n}=\binom n0=1$ as desired.

Another approach is to recognise negation of the upper index in the second binomial coefficient: $$ (-1)^k\binom{n+k}k=\binom{k-(n+k)-1}k=\binom{-n-1}k, $$ after which the identity becomes in instance of the Vandermonde identity $$ \sum_{k=0}^n(-1)^k\binom nk\binom{n + k}k= \sum_k\binom n{n-k}\binom{-n-1}k=\binom{-1}n=(-1)^n. $$

${}$

Added after request in comment. Neither of these arguments requires much beyond basic knowledge about binomial coefficients. The difference operator $\Delta$ is defined by $\Delta(f)(k)=f(k+1)-f(k)$, so with $f:k\mapsto\binom km$ one gets $$ \Delta(f)(k)=\binom{k+1}m-\binom km=\binom k{m-1} $$

just from Pascal's recurrence. And the formula $$ \Delta^n(f)(n)=\sum_i(-1)^{n-i}\binom nif(n+i) $$ either follows easily by induction from the definition of $\Delta$, or if you prefer by using the operators identity $I$ and shift $S$ on functions, defined by $I(f)=f$ and $S(f)(i)=f(i+1)$, writing $\Delta=S-I$, and using the binomial formula for $(S-I)^n$ (possible since $S$ and $I$ commute).

In the second variant, you probably already know the formula $\binom{-n}k= (-1)^k\binom{n+k-1}k$ for binomial coefficients with negative upper index, or else the equality between the outer expressions in $$ (1+X)^{-n} = \sum_{k\in\mathbf N} \binom{-n}kX^k = \sum_{k\in\mathbf N}(-1)^k\binom{n+k-1}kX^k $$ (if not, see this answer deriving the first formula). Then $\sum_k(-1)^k\binom{n+k}kX^k=(1+X)^{-n-1}$, and the instance of the Vandermonde identity is proved by comparing coefficients in $$ \sum_n\left(\sum_{k=0}^n(-1)^k\tbinom{n + k}k\tbinom nk\right)X^n =(1+X)^{-n-1}(1+X)^n=(1+X)^{-1}=\sum_n(-1)^nX^n $$ which might be the proof using only manipulation of $(1+X)^{n-1}$ you asked for.

Solution 2:

Suppose we seek to evaluate $$\sum_{k=0}^n (-1)^k {n\choose k} {n+k\choose k}.$$

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

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

It follows that the closed form of the sum is given by $$(-1)^n [z^n] (1+z)^n = (-1)^n.$$

A trace as to when this method appeared on MSE and by whom starts at this MSE link.