TAOCP 1.2.6 Exercise 48

Exercise 48. [M25] Show that

$$ \sum_{k \ge 0}\binom{n}{k}\frac{(-1)^k}{k+x} = \frac{n!}{x(x+1)\cdots(x+n)} = \frac{1}{x\binom{n+x}{n}}, $$

if the denominators are not zero.

Verified: no
Solve time: -

Solution

We are asked to evaluate

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

Consider the function

$$ f(x) = \int_0^1 t^{x-1} (1-t)^n , dt, $$

which is well defined for $x \notin {0,-1,-2,\dots,-n}$. Expanding $(1-t)^n$ by the binomial theorem, Eq. (13), we have

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

Substituting this expansion into the integral yields

$$ f(x) = \int_0^1 t^{x-1} \sum_{k=0}^n \binom{n}{k} (-1)^k t^k , dt = \sum_{k=0}^n \binom{n}{k} (-1)^k \int_0^1 t^{x+k-1} , dt, $$

where we have interchanged summation and integration, which is valid because the sum has finitely many terms. Each integral evaluates to

$$ \int_0^1 t^{x+k-1} , dt = \frac{1}{x+k}, $$

since $x+k \neq 0$. Therefore,

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

On the other hand, $f(x)$ is a standard Beta function:

$$ f(x) = \int_0^1 t^{x-1} (1-t)^n , dt = \mathrm{B}(x,n+1) = \frac{\Gamma(x)\Gamma(n+1)}{\Gamma(x+n+1)}. $$

Using the relation $\Gamma(x+1) = x\Gamma(x)$ repeatedly, we obtain

$$ \frac{\Gamma(x)\Gamma(n+1)}{\Gamma(x+n+1)} = \frac{n!}{x(x+1)\cdots(x+n)}. $$

Finally, using the factorial representation of the binomial coefficient, Eq. (5), we have

$$ x(x+1)\cdots(x+n) = x \frac{(x+n)!}{x!} = x , n! \binom{x+n}{n}, $$

so that

$$ \frac{n!}{x(x+1)\cdots(x+n)} = \frac{1}{x \binom{n+x}{n}}. $$

Hence we have established that

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

This completes the proof.

∎