4
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ Are you familiar with generating functions? The RHS is the generating function of $\frac{1}{1 + x}$. That should be a hint. $\endgroup$ – Qiaochu Yuan May 5 '13 at 7:48
5
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I'm after a solution that doesn't require knowledge beyond the basic binomial expansion of (1+x)^-n and manipulation of combinatorial coefficients. There must be a manipulation of (1+x)^-n that results in the above series of binomial coefficients. Any further ideas? $\endgroup$ – TryinHard May 6 '13 at 7:47
  • $\begingroup$ Thank you for the extended explanation. By equating the coefficient of X^n in the expansion of the following, the result indeed follows. \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 $\endgroup$ – TryinHard May 11 '13 at 6:10
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.