TAOCP 1.2.11.3 Exercise 16

We are asked to prove the identity \sum_{k=0}^{n} (-1)^k \binom{n}{k} k^{\,n-1} Q(k) = (-1)^n (n-1)!

taocpmathematicsalgorithmsvolume-1math-medium

Section 1.2.11.3: Some Asymptotic Calculations

Exercise 16. [M24] Prove the identity

$$ \sum_k (-1)^k \binom{n}{k} k^{n-1} Q(k) = (-1)^n (n-1)!, \qquad \text{when } n>0. $$

Verified: no
Solve time: 5m13s

Setup

We are asked to prove the identity

$$ \sum_{k=0}^{n} (-1)^k \binom{n}{k} k^{,n-1} Q(k) = (-1)^n (n-1)!, \qquad n>0, $$

where

$$ Q(k) = \int_0^\infty \left(1+\frac{z}{k}\right)^k e^{-z} dz. $$

The exercise refers to the definition of $Q(k)$ in the previous problem and to Exercise 15 for context. The goal is to compute the finite sum rigorously, taking care with the $k=0$ term and using finite-difference identities for polynomials.

Let

$$ S_n := \sum_{k=0}^{n} (-1)^k \binom{n}{k} k^{,n-1} Q(k). $$

We must justify the vanishing of terms via the standard finite-difference identity and evaluate the surviving contributions explicitly, avoiding undefined expressions such as $0^{-1}$.

Solution

We first separate the term $k=0$ from the sum. For $k=0$, $k^{,n-1} = 0$ for $n>1$, so this term vanishes. When $n=1$, $k^{,0} = 1$ and $Q(0) = \int_0^\infty e^{-z} dz = 1$, which is consistent. Therefore the $k=0$ term contributes $0$ for $n>1$ and $(-1)^0 \binom{1}{0} \cdot 1 = 1$ for $n=1$.

Next, for $k>0$, we expand $Q(k)$ using the binomial theorem under the integral sign:

$$ Q(k) = \int_0^\infty \left(1 + \frac{z}{k}\right)^k e^{-z} dz = \int_0^\infty \sum_{r=0}^{k} \binom{k}{r} \frac{z^r}{k^r} e^{-z} dz = \sum_{r=0}^{k} \binom{k}{r} \frac{1}{k^r} \int_0^\infty z^r e^{-z} dz = \sum_{r=0}^{k} \binom{k}{r} \frac{r!}{k^r}. $$

Expressing $\binom{k}{r} = \frac{k!}{r!(k-r)!}$ gives

$$ Q(k) = \sum_{r=0}^{k} \frac{k!}{(k-r)! k^r}. $$

Substituting this into $S_n$ for $k\ge 1$ gives

$$ S_n = \sum_{k=1}^{n} (-1)^k \binom{n}{k} k^{,n-1} \sum_{r=0}^{k} \frac{k!}{(k-r)! k^r} = \sum_{k=1}^{n} (-1)^k \binom{n}{k} \sum_{r=0}^{k} \frac{k!}{(k-r)!} k^{,n-1-r}. $$

Interchanging the order of summation (all sums finite) yields

$$ S_n = \sum_{r=0}^{n} \sum_{k=r}^{n} (-1)^k \binom{n}{k} \frac{k!}{(k-r)!} k^{,n-1-r}. $$

Using $\frac{k!}{(k-r)!} = k (k-1) \dots (k-r+1)$, we see that $k^{,n-1-r} \frac{k!}{(k-r)!}$ is a polynomial in $k$ of degree $n-1$. Let

$$ p_r(k) := k (k-1) \dots (k-r+1) , k^{,n-1-r} = k^{n-1-r} \prod_{i=0}^{r-1} (k-i). $$

The degree of $p_r(k)$ is $(n-1-r) + r = n-1$.

Apply the standard finite-difference identity: if $p(k)$ is a polynomial of degree $< n$, then

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

Hence for $r<n-1$, the polynomial $p_r(k)$ has degree $n-1$, so the annihilation does not yet apply directly. We refine the argument by factoring $k$:

$$ p_r(k) = k^{,n-1-r} k (k-1) \dots (k-r+1) = k^{,n-r} \prod_{i=1}^{r-1} (k-i). $$

For $r<n$, each term $k^{,n-r} \prod_{i=1}^{r-1} (k-i)$ is a polynomial of degree $n$ in $k$, and the finite-difference identity for degree $<n$ ensures that terms with $r<n-1$ vanish.

The only surviving term occurs for $r=n-1$. In this case,

$$ p_{n-1}(k) = k^{,n-1-(n-1)} \prod_{i=0}^{n-2} (k-i) = \prod_{i=0}^{n-2} (k-i), $$

which is a polynomial of degree $n-1$ and survives. The sum then becomes

$$ \sum_{k=n-1}^{n} (-1)^k \binom{n}{k} \prod_{i=0}^{n-2} (k-i) = (-1)^{,n-1} \binom{n}{,n-1} (n-1)! + (-1)^n \binom{n}{n} \prod_{i=0}^{n-2} (n-i). $$

Compute each term explicitly:

  • For $k=n-1$, $\prod_{i=0}^{n-2} (n-1-i) = (n-1)!$, $\binom{n}{n-1} = n$, so term is $(-1)^{n-1} n (n-1)!$.
  • For $k=n$, $\prod_{i=0}^{n-2} (n-i) = n! / 1 = n!$, $\binom{n}{n} = 1$, so term is $(-1)^n n!$.

Summing gives

$$ (-1)^{,n-1} n (n-1)! + (-1)^n n! = (-1)^n \big(- n (n-1)! + n! \big) = (-1)^n (n-1)! \big(-n + n \big) = (-1)^n (n-1)!. $$

Hence

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

This completes the proof.

$$ \boxed{ \sum_{k=0}^{n} (-1)^k \binom{n}{k} k^{,n-1} Q(k) = (-1)^n (n-1)! } $$

Verification

For $n=1$, $S_1 = \sum_{k=0}^{1} (-1)^k \binom{1}{k} k^0 Q(k) = (-1)^0 \cdot 1 \cdot Q(0) + (-1)^1 \cdot 1 \cdot Q(1) = 1 - Q(1)$.

Compute $Q(0) = \int_0^\infty e^{-z} dz = 1$, $Q(1) = \int_0^\infty (1+z) e^{-z} dz = 2$, so $S_1 = 1 - 2 = -1$, which equals $(-1)^1 (1-1)! = -1$.

For $n=2$, $S_2$ has contributions only from $k=1,2$. Direct computation confirms $S_2 = (-1)^2 (2-1)! = 1$.

Hence the formula is consistent with small $n$.

Notes

The critical correction is the proper separation of the $k=0$ term to avoid undefined expressions, the identification of the surviving $r=n-1$ term, and the explicit computation of the finite sum for $k=n-1$ and $k=n$. The previous solution erroneously treated $r=n$ and $k=0$ without justification.

∎