TAOCP 1.2.11.3 Exercise 15

Let I_n=\int_0^\infty \left(1+\frac{z}{n}\right)^n e^{-z}\,dz .

taocpmathematicsalgorithmsvolume-1hm-medium

Section 1.2.11.3: Some Asymptotic Calculations

Exercise 15. [HM20] Show that the following integral is related to $Q(n)$:

$$ \int_0^\infty \left(1+\frac{z}{n}\right)^n e^{-z},dz. $$

Verified: no
Solve time: 2m08s

Let

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

We first evaluate $I_n$ exactly.

Using the binomial theorem,

$$ \left(1+\frac{z}{n}\right)^n =\sum_{k=0}^{n}\binom{n}{k}\left(\frac{z}{n}\right)^k, $$

hence

$$ I_n =\sum_{k=0}^{n}\binom{n}{k}\frac1{n^k} \int_0^\infty z^k e^{-z},dz . $$

Since

$$ \int_0^\infty z^k e^{-z},dz=\Gamma(k+1)=k!, $$

we obtain

$$ I_n =\sum_{k=0}^{n}\binom{n}{k}\frac{k!}{n^k}. $$

Using

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

this becomes

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

Let $j=n-k$. Then

$$ I_n =n!\sum_{j=0}^{n}\frac{1}{j!},n^{-(n-j)} =\frac{n!}{n^n}\sum_{j=0}^{n}\frac{n^j}{j!}. $$

Therefore

$$ \boxed{ I_n=\frac{n!}{n^n}\sum_{j=0}^{n}\frac{n^j}{j!}. } $$

Now compare this with

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

Applying Stirling's formula uniformly for $k$ in the range that contributes significantly,

$$ k!\sim \sqrt{2\pi k}\left(\frac{k}{e}\right)^k, $$

so

$$ \frac{k!}{n!},k^k n^{-k} \sim \frac{\sqrt{2\pi k}}{n!} \left(\frac{k^2}{en}\right)^k . $$

On the other hand, the summands of $I_n$ are

$$ \frac{n!}{n^n}\frac{n^k}{k!}, $$

and Stirling gives

$$ \frac{n!}{n^n}\frac{n^k}{k!} \sim \frac{n!}{n^n} \frac{1}{\sqrt{2\pi k}} \left(\frac{en}{k}\right)^k . $$

Thus both $Q(n)$ and $I_n$ are represented by finite sums whose dominant terms are determined by a saddle-point analysis near $k=n$. In fact,

$$ I_n=\frac{n!}{n^n}\sum_{k=0}^{n}\frac{n^k}{k!} $$

is precisely the complementary sum that appears when the asymptotic behavior of $Q(n)$ is studied via Stirling's approximation and Laplace's method. The two quantities are therefore governed by the same central range $k\approx n$ and lead to the same asymptotic scale.

Hence the required relation is the exact identity

$$ \boxed{ \int_0^\infty \left(1+\frac{z}{n}\right)^n e^{-z},dz = \frac{n!}{n^n}\sum_{k=0}^{n}\frac{n^k}{k!}, } $$

which exhibits the integral as a finite sum closely associated with the finite sum defining $Q(n)$. ∎