TAOCP 6.4 Exercise 52
From equation (42), $Q_o(M,N)$ is given by the finite sum Q_o(M,N)=\sum_{k=0}^{N} \binom{N}{k}\frac{k!
Exercise 52. [HM20] [HM20] Prove that Qo(M, N) = fo? e ‘(1+ t/M)" dt.
Verified: yes
Solve time: 1m03s
Solution
From equation (42), $Q_o(M,N)$ is given by the finite sum
$$ Q_o(M,N)=\sum_{k=0}^{N} \binom{N}{k}\frac{k!}{M^k}. $$
Consider the integral
$$ I=\int_{0}^{\infty} e^{-t}\left(1+\frac{t}{M}\right)^N dt. $$
Expand the power using the binomial theorem,
$$ \left(1+\frac{t}{M}\right)^N=\sum_{k=0}^{N} \binom{N}{k}\frac{t^k}{M^k}. $$
Substituting this into $I$ yields
$$ I=\int_{0}^{\infty} e^{-t}\sum_{k=0}^{N} \binom{N}{k}\frac{t^k}{M^k} dt. $$
Since the sum is finite, interchange of summation and integration is valid,
$$ I=\sum_{k=0}^{N} \binom{N}{k}\frac{1}{M^k}\int_{0}^{\infty} e^{-t} t^k dt. $$
For each integer $k\ge 0$, the gamma-function identity gives
$$ \int_{0}^{\infty} e^{-t} t^k dt = k!. $$
Substitution produces
$$ I=\sum_{k=0}^{N} \binom{N}{k}\frac{k!}{M^k}. $$
This expression matches the definition of $Q_o(M,N)$ from equation (42), hence
$$ Q_o(M,N)=\int_{0}^{\infty} e^{-t}\left(1+\frac{t}{M}\right)^N dt. $$
This completes the proof. ∎