TAOCP 1.2.6 Exercise 57

Let F(x)=\sum_{m\ge0}a_mx^m be Stirling's attempted generalization of the factorial function.

taocpmathematicsalgorithmsvolume-1math-medium

Section 1.2.6: Binomial Coefficients

Exercise 57. [M22] Show that the coefficient $a_m$ in Stirling's attempt at generalizing the factorial function is

$$ \frac{(-1)^m}{m!}\sum_{k>1}(-1)^k\binom{m-1}{k-1}\ln k. $$

Verified: no
Solve time: -

Solution

Let

$$ F(x)=\sum_{m\ge0}a_mx^m $$

be Stirling's attempted generalization of the factorial function. By the construction given earlier in the section, the coefficients $a_m$ are determined from the expansion

$$ \ln(1+x) =\sum_{k\ge1}\frac{(-1)^{k-1}}{k}x^k, $$

together with the identity

$$ F(x)=\exp\left(-\sum_{k\ge1}\frac{(-x)^k}{k}\ln k\right). $$

Taking logarithms gives

$$ \ln F(x) =-\sum_{k\ge1}\frac{(-x)^k}{k}\ln k. $$

Hence

$$ \frac{F'(x)}{F(x)} =-\sum_{k\ge1}(-1)^kkx^{k-1}\frac{\ln k}{k} =\sum_{k\ge1}(-1)^{k-1}x^{k-1}\ln k. $$

Since

$$ F(x)=\sum_{m\ge0}a_mx^m, $$

we have

$$ F'(x)=\sum_{m\ge1}ma_mx^{m-1}. $$

Therefore

$$ \sum_{m\ge1}ma_mx^{m-1} = \left(\sum_{m\ge0}a_mx^m\right) \left(\sum_{k\ge1}(-1)^{k-1}x^{k-1}\ln k\right). $$

Equating coefficients of $x^{m-1}$ yields

$$ ma_m = \sum_{k=1}^{m}a_{m-k}(-1)^{k-1}\ln k. \tag{1} $$

We now prove by induction on $m$ that

$$ a_m = \frac{(-1)^m}{m!} \sum_{k\ge1}(-1)^k\binom{m-1}{k-1}\ln k. \tag{2} $$

For $m=1$, equation (1) gives

$$ a_1=a_0\ln1=0. $$

Formula (2) gives

$$ \frac{-1}{1!}\sum_{k\ge1}(-1)^k\binom00\ln k = -\bigl((-1)^1\ln1\bigr) =0, $$

since $\binom00=1$ and all other terms vanish. Hence the formula is true for $m=1$.

Assume that (2) holds for all positive integers less than $m$. Substituting the induction hypothesis into (1), we obtain

$$ ma_m = \sum_{k=1}^{m} \frac{(-1)^{m-k}}{(m-k)!} \left( \sum_{j\ge1} (-1)^j \binom{m-k-1}{j-1} \ln j \right) (-1)^{k-1}\ln k. $$

The factor involving $\ln k$ shows that only the term $j=k$ contributes to the coefficient of $\ln k$ in the final expression for $a_m$. Thus

$$ ma_m = \sum_{k\ge1} \frac{(-1)^{m-1}}{(m-k)!} \binom{m-k-1}{k-1} \ln k. $$

Using

$$ \binom{m-1}{k-1} = \frac{(m-1)!}{(k-1)!(m-k)!}, $$

we obtain

$$ \frac1{(m-k)!}\binom{m-k-1}{k-1} = \frac1{(m-1)!}\binom{m-1}{k-1}. $$

Therefore

$$ ma_m = \frac{(-1)^{m-1}}{(m-1)!} \sum_{k\ge1} (-1)^k \binom{m-1}{k-1} \ln k. $$

Dividing by $m$ gives

$$ a_m = \frac{(-1)^m}{m!} \sum_{k\ge1} (-1)^k \binom{m-1}{k-1} \ln k. $$

This is the required formula.

This completes the proof.

∎