TAOCP 1.2.6 Exercise 16

Exercise 16. [M15] Given that $n$ and $k$ are positive integers, prove the symmetrical identity

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

Verified: yes
Solve time: 34s

Solution

We begin with the left-hand side of the identity and apply the definition (3) of binomial coefficients for general integers $r$:

$$ \binom{-n}{k-1} = \frac{(-n)(-n-1)\cdots(-n-(k-2))}{(k-1)!}. $$

Expanding the numerator, we have

$$ (-n)(-n-1)\cdots(-n-(k-2)) = (-1)^{k-1} n(n+1)\cdots(n+k-2), $$

because each factor contributes a factor of $-1$, and there are $k-1$ factors. Hence

$$ \binom{-n}{k-1} = (-1)^{k-1} \frac{n(n+1)\cdots(n+k-2)}{(k-1)!}. $$

Multiplying both sides by $(-1)^n$, we obtain

$$ (-1)^n \binom{-n}{k-1} = (-1)^n \cdot (-1)^{k-1} \frac{n(n+1)\cdots(n+k-2)}{(k-1)!} = (-1)^{n+k-1} \frac{n(n+1)\cdots(n+k-2)}{(k-1)!}. \tag{1} $$

Now consider the right-hand side of the identity:

$$ \binom{-k}{n-1} = \frac{(-k)(-k-1)\cdots(-k-(n-2))}{(n-1)!}. $$

Expanding similarly, we have

$$ (-k)(-k-1)\cdots(-k-(n-2)) = (-1)^{n-1} k(k+1)\cdots(k+n-2), $$

so that

$$ \binom{-k}{n-1} = (-1)^{n-1} \frac{k(k+1)\cdots(k+n-2)}{(n-1)!}. $$

Multiplying by $(-1)^k$ yields

$$ (-1)^k \binom{-k}{n-1} = (-1)^k \cdot (-1)^{n-1} \frac{k(k+1)\cdots(k+n-2)}{(n-1)!} = (-1)^{n+k-1} \frac{k(k+1)\cdots(k+n-2)}{(n-1)!}. \tag{2} $$

Comparing equations (1) and (2), it remains to verify that

$$ \frac{n(n+1)\cdots(n+k-2)}{(k-1)!} = \frac{k(k+1)\cdots(k+n-2)}{(n-1)!}. $$

Observe that both sides are products of $n+k-2$ consecutive integers, grouped differently. More precisely, by equation (5) or the factorial representation, we have

$$ \frac{n(n+1)\cdots(n+k-2)}{(k-1)!} = \frac{(n+k-2)!}{(n-1)!(k-1)!}, $$

and

$$ \frac{k(k+1)\cdots(k+n-2)}{(n-1)!} = \frac{(n+k-2)!}{(k-1)!(n-1)!}. $$

Since multiplication is commutative, these expressions are identical. Therefore,

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

This completes the proof.

∎