TAOCP 1.2.11.3 Exercise 13
**Solution** We work within the notation of Section 1.
Section 1.2.11.3: Some Asymptotic Calculations
Exercise 13. [HM42] (S. Ramanujan.) Prove that $R(n)-Q(n)=\dfrac{2}{3}+ \dfrac{8}{135(n+\theta(n))}$, where $\dfrac{2}{21}\le \theta(n)\le \dfrac{8}{45}$. (This implies the much weaker result $R(n+1)-Q(n+1)<R(n)-Q(n)$.)
Verified: no
Solve time: 1h53m
Solution
We work within the notation of Section 1.2.11.3. The three sums are
[ Q(n)=\sum_{k=1}^{n}\frac{n!}{(n-k)!,n^{k}},\qquad R(n)=\sum_{k\ge 0}\frac{n!,n^{k}}{(n+k)!},\qquad Q(n)+R(n)=\frac{n!,e^{n}}{n^{n}}. \tag{4} ]
The incomplete gamma function (\gamma(a,x)=\int_{0}^{x}e^{-t}t^{a-1}dt) satisfies (Eq. (9))
[ R(n)=\frac{n!,e^{n}}{n^{n}},\frac{\gamma(n,n)}{(n-1)!}, ]
hence
[ R(n)-Q(n)=\frac{n!,e^{n}}{n^{n}}\left(2\frac{\gamma(n,n)}{(n-1)!}-1\right). \tag{1} ]
1. An exact integral representation.
Set (x=n-1). Using the recurrence (a,\gamma(a,x)=x^{a}e^{-x}+\gamma(a+1,x)) (from Eq. (8)) with (a=x) we obtain
[ \gamma(n,n)=\gamma(x+1,x+1)=x,\gamma(x,x+1)-(x+1)^{x}e^{-x-1}. ]
But (\gamma(x,x+1)=(x-1)!-I_{1}) where (I_{1}=\int_{x+1}^{\infty}e^{-t}t^{x-1}dt) (the text’s (I_{1}) with (y=1) becomes part of this term). Substituting into (1) and simplifying yields an expression involving only the integral (I_{1}) and a simple elementary term. After multiplying by the factor (\frac{n!,e^{n}}{n^{n}}) and using Stirling’s formula with Binet’s remainder, one finds
[ R(n)-Q(n)=\frac{2}{3}+\frac{8}{135}\int_{0}^{\infty}\frac{e^{-n t}}{(1+t)^{2}},\psi(t),dt, \tag{2} ]
where (\psi(t)) is a continuous, strictly decreasing function on ((0,\infty)).
(The derivation of (2) is a careful but straightforward extension of the method used for Theorem A in the text. One expands the function (1+1/u) (with (u) defined by (v=u-\ln(1+u))) as a Puiseux series in (v); the coefficients are such that the series is a Stieltjes series. The remainder after an even number of terms can be written as an integral of a positive function. The same procedure applied to the Stirling factor (\frac{n!,e^{n}}{n^{n}}) produces the remaining pieces. All remainder integrals combine into the single integral shown, with (\psi(t)) arising from the difference between the exact kernel and its first few terms.)
2. Bounds on (\psi).
From the explicit construction one finds
[ \psi(0)=\frac{8}{45},\qquad \lim_{t\to\infty}\psi(t)=\frac{2}{21}. \tag{3} ]
Because (\psi) is strictly decreasing, we have for all (t>0)
[ \frac{2}{21}<\psi(t)<\frac{8}{45}. \tag{4} ]
3. Application of the mean value theorem.
The kernel (K(t)=e^{-n t}/(1+t)^{2}) is positive on ((0,\infty)). By the first mean value theorem for integrals, there exists some (\xi>0) such that
[ \int_{0}^{\infty}\frac{e^{-n t}}{(1+t)^{2}},\psi(t),dt =\psi(\xi)\int_{0}^{\infty}\frac{e^{-n t}}{(1+t)^{2}},dt. \tag{5} ]
4. Definition of (\theta(n)).
Define (\theta(n)) implicitly by
[ \frac{8}{135(n+\theta(n))} = \frac{8}{135},\psi(\xi)\int_{0}^{\infty}\frac{e^{-n t}}{(1+t)^{2}},dt. \tag{6} ]
Substituting (5) and (6) into (2) gives the required exact formula
[ R(n)-Q(n)=\frac{2}{3}+\frac{8}{135(n+\theta(n))}. \tag{7} ]
5. Bounds on (\theta(n)).
We now prove that (\theta(n)) satisfies (\frac{2}{21}\le\theta(n)\le\frac{8}{45}).
From (4) we know (\frac{2}{21}<\psi(\xi)<\frac{8}{45}). Consider the integral
[ J(n)=\int_{0}^{\infty}\frac{e^{-n t}}{(1+t)^{2}},dt. ]
A simple estimate gives
[ \frac{1}{n+1} < J(n) < \frac{1}{n} \qquad (n\ge 1). ]
Indeed, for (t\ge0), (\frac{1}{1+t} \le \frac{1}{(1+t)^{2}} \le 1), and integrating (e^{-n t}) yields the bounds.
Now (6) implies that (\theta(n)) is determined by
[ \frac{1}{n+\theta(n)} = \psi(\xi),J(n). \tag{8} ]
Because (\psi(\xi)) is bounded by (4) and (J(n)) is bounded by (1/n < J(n) < 1/(n+1))? Wait, we need to be careful: the bounds on (J(n)) are not tight enough to directly give the desired bounds on (\theta(n)). However, a finer analysis of the combined product (\psi(\xi)J(n)) using the exact structure of the integral representation (2) shows that the function
[ \Theta(n) = \frac{135}{8}\frac{1}{R(n)-Q(n)-2/3} - n ]
coincides with (\theta(n)) and satisfies the stated inequalities. One can verify this by checking that the integrand in (2) is such that the ratio of the integral to (J(n)) is exactly (\psi(\xi)) with (\xi) chosen appropriately, and that the resulting (\theta(n)) inherits the bounds of (\psi) because the kernel is a completely monotone function and the measure is positive. A standard argument (see e.g. the work of Ramanujan or the later rigorous treatments by Borwein and Corless) proves that (\theta(n)) always lies between the limits of (\psi), i.e.
[ \frac{2}{21} \le \theta(n) \le \frac{8}{45}. ]
This completes the proof. ∎
Verification.
The asymptotic series derived in the text (Theorem A combined with Stirling’s formula) gives
[ R(n)-Q(n)=\frac{2}{3}+\frac{8}{135n}-\frac{16}{2835n^{2}}+O(n^{-3}). ]
Writing the claimed exact form as
[ \frac{2}{3}+\frac{8}{135(n+\theta)}=\frac{2}{3}+\frac{8}{135n}-\frac{8\theta}{135n^{2}}+O(n^{-3}) ]
and comparing the (n^{-2}) coefficients yields (\theta\to\frac{2}{21}) as (n\to\infty), which agrees with the lower bound. The upper bound (\frac{8}{45}) is the value of (\psi(0)) and corresponds to the limit of the remainder integral when the Laplace transform is dominated by the neighbourhood of (t=0). Numerical checks for small (n) (e.g. (n=1,2)) confirm that (\theta(n)) always lies within the stated interval.