TAOCP 1.2.11.3 Exercise 17
Define S(n)=\sum_{k\ge0}\frac{(n+k-1)!
Section 1.2.11.3: Some Asymptotic Calculations
Exercise 17. [HM29] (K. W. Miller.) Symmetry demands that we consider also a fourth series, which is to $P(n)$ as $R(n)$ is to $Q(n)$:
$$ S(n) = 1 + \frac{n}{n+1} + \frac{n}{n+2}\frac{n+1}{n+2} + \cdots = \sum_{k \ge 0} \frac{(n+k-1)!}{(n-1)!(n+k)^k}. $$
What is the asymptotic behavior of this function?
Verified: yes
Solve time: 1m56s
Setup
Define
$$ S(n)=\sum_{k\ge0}\frac{(n+k-1)!}{(n-1)!(n+k)^k}. $$
The problem asks for an asymptotic expansion of $S(n)$ analogous to the expansions (24), (25), and (26).
Using
$$ \frac{(n+k-1)!}{(n-1)!} =\frac{(n+k)!}{(n-1)!(n+k)}, $$
we rewrite the summand as
$$ \frac{(n+k)!}{(n-1)!(n+k)^{k+1}}. $$
Let
$$ m=n+k. $$
Then $k=m-n$, and
$$ S(n) =\frac1{(n-1)!}\sum_{m=n}^{\infty}\frac{m!}{m^{m-n+1}} =\frac1{(n-1)!}\sum_{m=n}^{\infty}m^{,n-1}\frac{m!}{m^m}. $$
Since
$$ Q(m)=\frac{m!e^m}{m^m}, $$
by the definition used throughout this section,
$$ \frac{m!}{m^m}=Q(m)e^{-m}. $$
Hence
$$ S(n) =\frac1{(n-1)!}\sum_{m=n}^{\infty}m^{,n-1}Q(m)e^{-m}. \tag{1} $$
Equation (25) gives
$$ Q(m) =\sqrt{\frac{\pi m}{2}} -\frac13 +\frac1{12}\sqrt{\frac{\pi}{2m}} -\frac4{135m} +O(m^{-3/2}). \tag{2} $$
Substituting (2) into (1) reduces the problem to estimating sums of the form
$$ \sum_{m=n}^{\infty}m^{,n+\alpha}e^{-m}. $$
Solution
Let
$$ T_\alpha(n)=\sum_{m=n}^{\infty}m^{,n+\alpha}e^{-m}. $$
The summand is concentrated near $m=n$. Applying Euler's summation formula exactly as in the derivation of (22), but for the upper tail, gives
$$ T_\alpha(n) = \Gamma!\left(n+\alpha+1,n\right) +\frac12 n^{,n+\alpha}e^{-n} +O!\left(n^{,n+\alpha-1}e^{-n}\right). \tag{3} $$
Now use Theorem A. Since
$$ \Gamma(a,n) = \Gamma(a)-\gamma(a,n), $$
equation (19) with $x=n+\alpha$ and $y=-\alpha$ yields
$$ \frac{\Gamma(n+\alpha+1,n)} {\Gamma(n+\alpha+1)} = \frac12 +\frac{\alpha+\frac23}{\sqrt{2\pi}},n^{-1/2} +O(n^{-3/2}). \tag{4} $$
Therefore
$$ \Gamma(n+\alpha+1,n) = \Gamma(n+\alpha+1) \left( \frac12 +\frac{\alpha+\frac23}{\sqrt{2\pi}},n^{-1/2} +O(n^{-3/2}) \right). \tag{5} $$
Using
$$ \frac{\Gamma(n+\alpha+1)}{(n-1)!} = n^{\alpha+1} \left( 1+\frac{\alpha(\alpha+1)}{2n} +O(n^{-2}) \right), \tag{6} $$
and
$$ \frac{n^{,n+\alpha}e^{-n}}{(n-1)!} = \frac1{\sqrt{2\pi}},n^{\alpha+1/2} +O(n^{\alpha-1/2}), \tag{7} $$
equations (3), (5), (6), and (7) imply
$$ \frac{T_\alpha(n)}{(n-1)!} = \frac12 n^{\alpha+1} +\frac{\alpha+\frac76}{\sqrt{2\pi}},n^{\alpha+1/2} +O(n^\alpha). \tag{8} $$
Apply (8) successively to the terms of (2).
For $\alpha=-\frac12$,
$$ \frac1{(n-1)!} \sum_{m=n}^{\infty} m^{,n-\frac12}e^{-m} = \frac12 n^{1/2} +\frac2{3\sqrt{2\pi}} +O(n^{-1/2}). \tag{9} $$
For $\alpha=-1$,
$$ \frac1{(n-1)!} \sum_{m=n}^{\infty} m^{,n-1}e^{-m} = \frac12 +\frac1{6\sqrt{2\pi}},n^{-1/2} +O(n^{-1}). \tag{10} $$
For $\alpha=-\frac32$,
$$ \frac1{(n-1)!} \sum_{m=n}^{\infty} m^{,n-\frac32}e^{-m} = \frac12 n^{-1/2} +O(n^{-1}). \tag{11} $$
Substituting (9), (10), and (11) into (1) and (2) gives
$$ \begin{aligned} S(n) &= \sqrt{\frac{\pi}{2}} \left( \frac12 n^{1/2} +\frac2{3\sqrt{2\pi}} \right) -\frac13\left(\frac12\right) +\frac1{12}\sqrt{\frac{\pi}{2}} \left(\frac12 n^{-1/2}\right) +O(n^{-1})\ &= \sqrt{\frac{\pi n}{8}} +\frac13 -\frac16 +\frac1{24}\sqrt{\frac{\pi}{2n}} +O(n^{-1}). \end{aligned} $$
The constant terms combine to
$$ \frac13-\frac16=\frac16. $$
Hence
$$ S(n) = \sqrt{\frac{\pi n}{8}} +\frac16 +\frac1{24}\sqrt{\frac{\pi}{2n}} +O(n^{-1}). \tag{12} $$
Thus the asymptotic behavior of $S(n)$ is
$$ \boxed{ S(n) = \sqrt{\frac{\pi n}{8}} +\frac16 +\frac1{24}\sqrt{\frac{\pi}{2n}} +O(n^{-1}) }. $$
Verification
The dominant contribution to $S(n)$ comes from the leading term of $Q(m)$ in (25),
$$ Q(m)\sim \sqrt{\frac{\pi m}{2}}. $$
Substituting this approximation into (1) gives
$$ S(n) \sim \sqrt{\frac{\pi}{2}} \frac1{(n-1)!} \sum_{m=n}^{\infty}m^{,n-\frac12}e^{-m}. $$
Equation (9) yields
$$ S(n)\sim \sqrt{\frac{\pi}{2}}\cdot\frac12 n^{1/2} = \sqrt{\frac{\pi n}{8}}, $$
which agrees with the leading term of (12).
The coefficient of $n^{1/2}$ is exactly one-half of the corresponding coefficient in (24), (25), and (26). This is consistent with the fact that $S(n)$ is represented by an upper-tail incomplete gamma function, whose leading asymptotic proportion is $1/2$ by Theorem A.
Notes
Keeping additional terms from (25) and carrying the expansion of (8) to one higher order produces a complete asymptotic series for $S(n)$ analogous to (24), (25), and (26). The leading behavior already exhibits the expected symmetry: the growth rate is proportional to $\sqrt{n}$, and the factor $1/2$ arises from the same incomplete-gamma transition described by Theorem A.