TAOCP 1.2.11.3 Exercise 11

The generalized sums are defined for integer \(n\ge 1\) and real \(x\) by \[ Q_x(n) = \sum_{k=0}^{n-1} \frac{(n-1)_k}{n^k}\,x^k, \qquad R_x(n) = \sum_{k=0}^{\infty} \frac{n!

taocpmathematicsalgorithmsvolume-1hm-hard

Section 1.2.11.3: Some Asymptotic Calculations

Exercise 11. ▶ [HM35] Let us generalize the functions $Q(n)$ and $R(n)$ by introducing a parameter $x$:

$$ Q_x(n)=1+\frac{n-1}{n}x+\frac{n-1}{n}\frac{n-2}{n}x^2+\cdots, $$

$$ R_x(n)=1+\frac{n}{n+1}x+\frac{n}{n+1}\frac{n}{n+2}x^2+\cdots. $$

Explore this situation and find asymptotic formulas when $x\ne 1$.

Verified: no
Solve time: 19m20s

Setup

The generalized sums are defined for integer (n\ge 1) and real (x) by

[ Q_x(n) = \sum_{k=0}^{n-1} \frac{(n-1)k}{n^k},x^k, \qquad R_x(n) = \sum{k=0}^{\infty} \frac{n!}{(n+k)!},n^k x^k, ]

where ((n-1)_k = (n-1)(n-2)\cdots(n-k)) (with the empty product equal to (1)). Both sums reduce to the original (Q(n)) and (R(n)) when (x=1).

Using standard identities for the incomplete gamma functions

[ \gamma(a,z) = \int_0^z t^{a-1}e^{-t},dt,\qquad \Gamma(a,z) = \int_z^\infty t^{a-1}e^{-t},dt, ]

and the relation (\gamma(a,z)+\Gamma(a,z)=\Gamma(a)), we obtain exact representations

[ Q_x(n) = \frac{x^{n-1}e^{n/x}}{n^{n-1}},\Gamma!\left(n,\frac{n}{x}\right), \tag{1} ] [ R_x(n) = \frac{n,e^{nx}}{(nx)^n},\gamma(n,nx). \tag{2} ]

The goal is to find asymptotic expansions of (Q_x(n)) and (R_x(n)) as (n\to\infty) for fixed (x\neq 1) (we assume (x>0); the case (x<0) leads to oscillatory asymptotics and is not treated here).

Solution

1. Asymptotics of the incomplete gamma functions

For large (n) and fixed (p>0), (p\neq 1), the normalized incomplete gamma functions have the following asymptotic expansions (obtained by Laplace’s method on the integral representations, cf. Exercises 9 and 10):

Let (A(p)=p-1-\ln p;(>0) for (p\neq1)).

  • (p>1): [ \frac{\Gamma(n,np)}{\Gamma(n)} = \frac{e^{-nA(p)}}{\sqrt{2\pi n},(p-1)} \left[1-\frac{p}{n(p-1)^2}+O!\left(\frac{1}{n^2}\right)\right],\qquad \frac{\gamma(n,np)}{\Gamma(n)} = 1-\frac{\Gamma(n,np)}{\Gamma(n)}. ]

  • (p<1): [ \frac{\gamma(n,np)}{\Gamma(n)} = \frac{e^{-nA(p)}}{\sqrt{2\pi n},(1-p)} \left[1-\frac{p}{n(1-p)^2}+O!\left(\frac{1}{n^2}\right)\right],\qquad \frac{\Gamma(n,np)}{\Gamma(n)} = 1-\frac{\gamma(n,np)}{\Gamma(n)}. ]

2. Stirling’s formula for (\Gamma(n))

[ \Gamma(n) = (n-1)! = \sqrt{2\pi},n^{n-1/2}e^{-n} \left(1+\frac{1}{12n}+\frac{1}{288n^2}+O!\left(\frac{1}{n^3}\right)\right). \tag{3} ]

3. Prefactors (D) and (C)

From (1) and (2) we write

[ Q_x(n) = D\cdot\frac{\Gamma(n,n/x)}{\Gamma(n)},\qquad R_x(n) = C\cdot\frac{\gamma(n,nx)}{\Gamma(n)}, ]

where

[ D = \frac{x^{n-1}e^{n/x}}{n^{n-1}},\Gamma(n),\qquad C = \frac{n,e^{nx}}{(nx)^n},\Gamma(n). ]

Using (3),

[ D = \sqrt{2\pi n};x^{n-1}e^{n(1/x-1)} \left(1+\frac{1}{12n}+\frac{1}{288n^2}+\cdots\right), \tag{4} ] [ C = \sqrt{2\pi n};\frac{e^{n(x-1)}}{x^n} \left(1+\frac{1}{12n}+\frac{1}{288n^2}+\cdots\right). \tag{5} ]

4. Case (x>1)

Here (p=x>1) for (R_x) and (p=1/x<1) for (Q_x).

  • (R_x(n)): (\displaystyle\frac{\gamma(n,nx)}{\Gamma(n)} = 1-\frac{e^{-nA(x)}}{\sqrt{2\pi n},(x-1)} \left[1-\frac{x}{n(x-1)^2}+\cdots\right]).

    Because (C\cdot\frac{e^{-nA(x)}}{\sqrt{2\pi n},(x-1)}=\frac{1}{x-1}),

    [ R_x(n) = C - \frac{1}{x-1} \left(1+\frac{1}{12n}+\cdots\right) \left(1-\frac{x}{n(x-1)^2}+\cdots\right). ]

    Hence

    [ \boxed{ R_x(n) \sim \sqrt{2\pi n},\frac{e^{n(x-1)}}{x^n} \left(1+\frac{1}{12n}+\frac{1}{288n^2}+\cdots\right)

    • \frac{1}{x-1} \left[1+\frac{1}{n}\left(\frac{1}{12}-\frac{x}{(x-1)^2}\right)+O!\left(\frac{1}{n^2}\right)\right]. } ]

  • (Q_x(n)): (\displaystyle\frac{\Gamma(n,n/x)}{\Gamma(n)} = 1-\frac{x,e^{-nA(1/x)}}{\sqrt{2\pi n},(x-1)} \left[1-\frac{x}{n(x-1)^2}+\cdots\right]).

    Since (D\cdot\frac{x,e^{-nA(1/x)}}{\sqrt{2\pi n},(x-1)}=\frac{1}{x-1}),

    [ Q_x(n) = D - \frac{1}{x-1} \left(1+\frac{1}{12n}+\cdots\right) \left(1-\frac{x}{n(x-1)^2}+\cdots\right). ]

    Therefore

    [ \boxed{ Q_x(n) \sim \sqrt{2\pi n};x^{n-1}e^{n(1/x-1)} \left(1+\frac{1}{12n}+\frac{1}{288n^2}+\cdots\right)

    • \frac{1}{x-1} \left[1+\frac{1}{n}\left(\frac{1}{12}-\frac{x}{(x-1)^2}\right)+O!\left(\frac{1}{n^2}\right)\right]. } ]

5. Case (x<1)

Now (p=x<1) for (R_x) and (p=1/x>1) for (Q_x).

  • (R_x(n)): (\displaystyle\frac{\gamma(n,nx)}{\Gamma(n)} = \frac{e^{-nA(x)}}{\sqrt{2\pi n},(1-x)} \left[1-\frac{x}{n(1-x)^2}+\cdots\right]).

    Multiplying by (C) and using (e^{n(x-1)}e^{-nA(x)}=x^n),

    [ R_x(n) = \frac{1}{1-x} \left(1+\frac{1}{12n}+\cdots\right) \left(1-\frac{x}{n(1-x)^2}+\cdots\right). ]

    Hence

    [ \boxed{ R_x(n) \sim \frac{1}{1-x} \left[1+\frac{1}{n}\left(\frac{1}{12}-\frac{x}{(1-x)^2}\right)+O!\left(\frac{1}{n^2}\right)\right]. } ]

  • (Q_x(n)): (\displaystyle\frac{\Gamma(n,n/x)}{\Gamma(n)} = \frac{x,e^{-nA(1/x)}}{\sqrt{2\pi n},(1-x)} \left[1-\frac{x}{n(1-x)^2}+\cdots\right]).

    Multiplying by (D) and using (x^{n-1}e^{n(1/x-1)}e^{-nA(1/x)}x = 1),

    [ Q_x(n) = \frac{1}{1-x} \left(1+\frac{1}{12n}+\cdots\right) \left(1-\frac{x}{n(1-x)^2}+\cdots\right). ]

    Thus

    [ \boxed{ Q_x(n) \sim \frac{1}{1-x} \left[1+\frac{1}{n}\left(\frac{1}{12}-\frac{x}{(1-x)^2}\right)+O!\left(\frac{1}{n^2}\right)\right]. } ]

Verification

  1. Limit (x<1): Both (Q_x(n)) and (R_x(n)) tend to (\frac{1}{1-x}).
    This matches the termwise limits of the defining series:
    (\frac{(n-1)k}{n^k}\to 1) and (\frac{n!,n^k}{(n+k)!}\to 1) as (n\to\infty), so both sums approach (\sum{k\ge0}x^k=\frac{1}{1-x}).

  2. Leading terms for (x>1): The exponentially growing factors are
    (\sqrt{2\pi n},x^{n-1}e^{n(1/x-1)}) for (Q_x) and (\sqrt{2\pi n},e^{n(x-1)}/x^n) for (R_x).
    Their exponents are (n(\ln x+1/x-1)) and (n(x-1-\ln x)) respectively, both positive for (x>1).
    The constant correction (-1/(x-1)) is easily checked against exact formulas for small (n) (e.g. (n=3,x=2) gives (Q\approx3.22), asymptotic (3.87-1=2.87); (R\approx10.51), asymptotic (10.90-1=9.90) , reasonable agreement for such small (n)).

  3. Consistency of the (1/n) coefficients: The correction coefficient (\frac{1}{12}-\frac{x}{(x-1)^2}) (for (x>1)) and (\frac{1}{12}-\frac{x}{(1-x)^2}) (for (x<1)) are exactly what one obtains by multiplying the Stirling series with the next term in the incomplete gamma expansion. They are the same for (Q_x) and (R_x) in each regime, as required by the structure of the calculation.

  4. Standard reference: The asymptotic formulas for the incomplete gamma functions used here are classical (DLMF 8.11) and were also derived in the text’s Theorem A (for the central regime) and in Exercises 9-10 (for the large‑deviation regime (p\neq1)).

This completes the derivation. ∎