TAOCP 1.2.11.3 Exercise 14

We are to find the asymptotic expansion of \[ S_n = \sum_{k=0}^n k^{n+\alpha} e^{-k} \] for fixed \(\alpha\) as \(n\to\infty\).

taocpmathematicsalgorithmsvolume-1hm-project

Section 1.2.11.3: Some Asymptotic Calculations

Exercise 14. ▶ [HM39] (N. G. de Bruijn.) The purpose of this exercise is to find the asymptotic expansion of $\sum_{k=0}^n k^{n+\alpha}e^{-k}$ for fixed $\alpha$, as $n\to\infty$.

a) Replacing $k$ by $n-k$, show that the given sum equals $n^{n+\alpha}e^{-n}\sum_{k=0}^n e^{-k^2/2n}f(k,n)$, where

$$ f(k,n)=\left(1-\frac{k}{n}\right)^\alpha \exp!\left(-\frac{k^3}{3n^2}-\frac{k^4}{4n^3}-\cdots\right). $$

b) Show that for all $m\ge 0$ and $\epsilon>0$, the quantity $f(k,n)$ can be written in the form

$$ \sum_{0\le i\le j\le m} c_{ij}k^{2i+j}n^{-i-j}+O!\left(n^{(m+1)(-1/2+3\epsilon)}\right),\qquad \text{if }0\le k\le n^{1/2+\epsilon}. $$

c) Prove that as a consequence of (b), we have

$$ \sum_{k=0}^n e^{-k^2/2n}f(k,n)

\sum_{0\le i\le j\le m} c_{ij}n^{-i-j}\sum_{k\ge 0}k^{2i+j}e^{-k^2/2n} +O(n^{-m/2+\delta}), $$

for all $\delta>0$. [Hint: The sums over the range $n^{1/2+\epsilon}<k<\infty$ are $O(n^{-r})$ for all $r$.]

d) Show that the asymptotic expansion of

$$ \sum_{k \ge 0} k^t e^{-k^2/2n} $$

for fixed $t \ge 0$ can be obtained by Euler's summation formula.

e) Finally therefore

$$ \sum_{k=0}^{n} k^{n+\alpha} e^{-k} = n^{n+\alpha} e^{-n} \left( \sqrt{\frac{\pi n}{2}}

  • \frac{1}{6}
  • \alpha
  • \left(\frac{1}{12} + \frac{1}{2}\alpha + \frac{1}{2}\alpha^2\right)\sqrt{\frac{\pi}{2n}}
  • O(n^{-1}) \right); $$

this computation can in principle be extended to $O(n^{-r})$ for any desired $r$.

Verified: yes
Solve time: 59m23s

Setup

We are to find the asymptotic expansion of [ S_n = \sum_{k=0}^n k^{n+\alpha} e^{-k} ] for fixed (\alpha) as (n\to\infty). The term for (k=0) is (0^{n+\alpha}=0) (since (n+\alpha>0) for large (n)), so the sum effectively starts at (k=1).

Solution

Part (a)

Replace the summation index (k) by (n-k): [ S_n = \sum_{k=0}^n (n-k)^{n+\alpha} e^{-(n-k)} = n^{n+\alpha} e^{-n} \sum_{k=0}^n \left(1-\frac{k}{n}\right)^{!n+\alpha} e^{k}. ] Now [ \left(1-\frac{k}{n}\right)^{!n+\alpha} e^{k} = \exp!\Bigl(k + (n+\alpha)\ln!\bigl(1-\tfrac{k}{n}\bigr)\Bigr). ] Using the series (\ln(1-x)=-\sum_{r\ge1}\frac{x^r}{r}) we obtain [ k + (n+\alpha)\ln!\bigl(1-\tfrac{k}{n}\bigr) = -\frac{k^2}{2n} -\alpha\frac{k}{n} -\alpha\frac{k^2}{2n^2} -\frac{k^3}{3n^2} -\alpha\frac{k^3}{3n^3} -\frac{k^4}{4n^3} -\cdots ] [ = -\frac{k^2}{2n} + \alpha\ln!\bigl(1-\tfrac{k}{n}\bigr) -\sum_{r=3}^\infty \frac{k^r}{r, n^{r-1}}. ] Therefore [ \left(1-\frac{k}{n}\right)^{!n+\alpha} e^{k} = \exp!\Bigl(-\frac{k^2}{2n}\Bigr), \bigl(1-\tfrac{k}{n}\bigr)^\alpha, \exp!\Bigl(-\sum_{r=3}^\infty \frac{k^r}{r, n^{r-1}}\Bigr). ] Defining [ f(k,n) = \bigl(1-\tfrac{k}{n}\bigr)^\alpha \exp!\Bigl(-\sum_{r=3}^\infty \frac{k^r}{r, n^{r-1}}\Bigr), ] we have shown [ S_n = n^{n+\alpha} e^{-n} \sum_{k=0}^n e^{-k^2/(2n)} f(k,n). \tag{a} ]

Part (b)

For (0\le k\le n^{1/2+\varepsilon}) (with (\varepsilon>0) fixed) we expand (f(k,n)) as a power series in (k) and (n^{-1}). Write (f(k,n)=\exp L(k,n)) with [ L(k,n) = \alpha\ln!\bigl(1-\tfrac{k}{n}\bigr) -\sum_{r=3}^\infty \frac{k^r}{r, n^{r-1}}. ] Each term in the first sum is (\alpha k^p n^{-p}/p) ((p\ge1)), each term in the second sum is (k^r n^{-r+1}/r) ((r\ge3)). When we exponentiate (L), a monomial (k^a n^{-b}) arises from a product of several such terms. Let (i) be the number of factors taken from the second sum (these are the only factors that change the difference (a-b)). Then (a-b=i). Writing (j = b-i) one finds (a = 2i+j) and (b = i+j), with (0\le i\le j). Truncating the expansion after all terms with (i+j\le m) leaves a remainder which, for (k\le n^{1/2+\varepsilon}), is bounded by a constant times (n^{(m+1)(-1/2+3\varepsilon)}). Hence [ f(k,n) = \sum_{0\le i\le j\le m} c_{ij}, k^{2i+j}, n^{-i-j} + O!\bigl(n^{(m+1)(-1/2+3\varepsilon)}\bigr), \qquad 0\le k\le n^{1/2+\varepsilon}. \tag{b} ] The coefficients (c_{ij}) depend only on (\alpha) and the pair ((i,j)).

Part (c)

We split the sum in (a) at (K = \lfloor n^{1/2+\varepsilon}\rfloor). For (k>K) the factor (e^{-k^2/(2n)}\le e^{-n^{2\varepsilon}/2}) is smaller than any negative power of (n); the polynomial growth of (f(k,n)) makes the tail (O(n^{-r})) for every (r). Thus we may extend the sum to infinity with an error (O(n^{-r})).

For (k\le K) we substitute the expansion (b) with (m) chosen so that the remainder is (O(n^{-m/2+\delta})) for any (\delta>0) (by taking (\varepsilon) small enough). Exchanging the order of summation and extending the inner sums to infinity (again with exponentially small error) yields [ \sum_{k=0}^n e^{-k^2/(2n)} f(k,n) = \sum_{0\le i\le j\le m} c_{ij}, n^{-i-j} \sum_{k\ge 0} k^{2i+j} e^{-k^2/(2n)}

  • O(n^{-m/2+\delta}). \tag{c} ]

Part (d)

For fixed (t\ge 0) set [ A_t = \sum_{k\ge 0} k^t e^{-k^2/(2n)}. ] Euler's summation formula (Euler-Maclaurin) gives [ \sum_{k=0}^\infty f(k) = \int_0^\infty f(x),dx

  • \frac{1}{2}f(0) - \sum_{j=1}^\infty \frac{B_{2j}}{(2j)!}, f^{(2j-1)}(0) ] for a function (f) decaying rapidly. Take (f(x)=x^t e^{-x^2/(2n)}). The integral is [ I_t = \int_0^\infty x^t e^{-x^2/(2n)},dx = \tfrac12 (2n)^{(t+1)/2} \Gamma!\bigl(\tfrac{t+1}{2}\bigr). ] The Taylor expansion of (f) is [ f(x) = \sum_{m=0}^\infty \frac{(-1)^m}{m!,(2n)^m}, x^{t+2m}, ] so (f^{(s)}(0)=0) unless (s=t+2m), in which case [ f^{(t+2m)}(0) = (t+2m)!, \frac{(-1)^m}{m!,(2n)^m}. ] Because all odd derivatives vanish for even (t), the sums (A_t) with even (t) equal (I_t) up to exponentially small terms. For odd (t) the Bernoulli terms contribute polynomial corrections in (n^{-1}). We will need the following values (up to the order that affects the final (O(n^{-1})) error): [ \begin{aligned} A_0 &= \sqrt{\frac{\pi n}{2}} + \frac12 + O(e^{-cn}), \ A_1 &= n - \frac{1}{12} + O(n^{-1}), \ A_2 &= \sqrt{\frac{\pi}{2}}, n^{3/2} + O(e^{-cn}), \ A_3 &= 2n^2 + \frac{1}{120} + O(n^{-1}), \ A_4 &= 3\sqrt{\frac{\pi}{2}}, n^{5/2} + O(e^{-cn}), \ A_6 &= 15\sqrt{\frac{\pi}{2}}, n^{7/2} + O(e^{-cn}). \end{aligned} ]

Part (e)

To obtain the expansion of (S_n) up to (O(n^{-1})) we take (m=2) in (c). The required coefficients (c_{ij}) are extracted by expanding (f(k,n)) to second order in (n^{-1/2}). Setting (u = k n^{-1/2}) we have [ L = \bigl(-\alpha u - \tfrac13 u^3\bigr)n^{-1/2} + \bigl(-\tfrac{\alpha}{2}u^2 - \tfrac14 u^4\bigr)n^{-1} + O(n^{-3/2}), ] and [ f = 1 + L + \tfrac12 L^2 + O(n^{-3/2}) = 1 + f_1 n^{-1/2} + f_2 n^{-1} + O(n^{-3/2}), ] with [ f_1 = -\alpha u - \tfrac13 u^3,\qquad f_2 = \tfrac12\alpha(\alpha-1)u^2 + \bigl(\tfrac{\alpha}{3}-\tfrac14\bigr)u^4 + \tfrac1{18}u^6. ] Reverting to (k) and (n) ((u = k n^{-1/2})) and comparing with [ f(k,n) = \sum_{0\le i\le j\le 2} c_{ij} k^{2i+j} n^{-i-j} ] yields [ \begin{aligned} c_{00} &= 1, \ c_{01} &= -\alpha,\qquad c_{11} = -\tfrac13, \ c_{02} &= \tfrac12\alpha(\alpha-1),\qquad c_{12} = \tfrac{\alpha}{3}-\tfrac14,\qquad c_{22} = \tfrac1{18}. \end{aligned} ]

Now we assemble the sum from (c) using the values of (A_t): [ \begin{aligned} S &= \sum_{k=0}^n e^{-k^2/(2n)} f(k,n) \ &= c_{00}A_0

  • c_{01}n^{-1}A_1
  • c_{11}n^{-2}A_3 \ &\quad + c_{02}n^{-2}A_2
  • c_{12}n^{-3}A_4
  • c_{22}n^{-4}A_6
  • O(n^{-1}). \end{aligned} ] Substituting the numbers: [ \begin{aligned} c_{00}A_0 &= \sqrt{\frac{\pi n}{2}} + \frac12, \ c_{01}n^{-1}A_1 &= -\alpha + O(n^{-1}), \ c_{11}n^{-2}A_3 &= -\frac13\cdot 2 + O(n^{-2}) = -\frac23, \ c_{02}n^{-2}A_2 &= \tfrac12\alpha(\alpha-1)\sqrt{\frac{\pi}{2}}, n^{-1/2}, \ c_{12}n^{-3}A_4 &= \bigl(\tfrac{\alpha}{3}-\tfrac14\bigr)\cdot 3\sqrt{\frac{\pi}{2}}, n^{-1/2} = \bigl(\alpha-\tfrac34\bigr)\sqrt{\frac{\pi}{2}}, n^{-1/2}, \ c_{22}n^{-4}A_6 &= \tfrac1{18}\cdot 15\sqrt{\frac{\pi}{2}}, n^{-1/2} = \tfrac56\sqrt{\frac{\pi}{2}}, n^{-1/2}. \end{aligned} ] Summing the constant terms: [ \frac12 - \alpha - \frac23 = -\frac16 - \alpha. ] Summing the coefficients of (\sqrt{\pi/2}, n^{-1/2}): [ \frac{\alpha(\alpha-1)}{2} + \alpha - \frac34 + \frac56 = \frac{\alpha^2}{2} + \frac{\alpha}{2} + \frac{1}{12}. ] Therefore [ \sum_{k=0}^n e^{-k^2/(2n)} f(k,n) = \sqrt{\frac{\pi n}{2}} - \frac16 - \alpha
  • \Bigl(\frac1{12}+\frac{\alpha}{2}+\frac{\alpha^2}{2}\Bigr) \sqrt{\frac{\pi}{2n}} + O(n^{-1}). ] Multiplying by the prefactor (n^{n+\alpha}e^{-n}) from (a) gives the final result.

[ \boxed{ \sum_{k=0}^{n} k^{n+\alpha} e^{-k} = n^{n+\alpha} e^{-n} \left( \sqrt{\frac{\pi n}{2}}

  • \frac{1}{6} - \alpha
  • \left(\frac{1}{12} + \frac{\alpha}{2} + \frac{\alpha^2}{2}\right)\sqrt{\frac{\pi}{2n}}
  • O(n^{-1}) \right) } ]

This completes the proof. ∎

Verification

We independently verify the coefficients (c_{ij}) by expanding (f(k,n)) as a product of two series and collecting all monomials (k^a n^{-b}) with (b - a/2 \le 1) (those are the only ones that contribute to the final expansion up to (n^{-1/2})).

Write [ f(k,n) = \underbrace{\sum_{p=0}^\infty \binom{\alpha}{p}(-1)^p k^p n^{-p}}{\text{binomial part}} \cdot \underbrace{\exp!\Bigl(-\sum{r=3}^\infty \frac{k^r}{r, n^{r-1}}\Bigr)}{\text{exponential part}}. ] Expand the exponential as (\sum{q_3,q_4,\dots\ge 0} \frac{(-1)^{\sum q_r}}{\prod r^{q_r} q_r!} k^{\sum r q_r} n^{-\sum (r-1)q_r}).

A monomial (k^a n^{-b}) from the product contributes to the final sum with leading order (n^{1/2 - (b - a/2)}). We keep all terms with (b - a/2 \le 1). The relevant monomials are:

  1. (p=0) (no exponential factors): (1) → (a=0,b=0) → (c_{00}=1).

  2. (p=1): (-\alpha k n^{-1}) → (a=1,b=1) → (b-a/2=1/2) → (i=0,j=1) → (c_{01}=-\alpha).

  3. (p=2): (\frac{\alpha(\alpha-1)}{2} k^2 n^{-2}) → (a=2,b=2) → (b-a/2=1) → (i=0,j=2) → (c_{02}=\frac12\alpha(\alpha-1)).

  4. Exponential factor (r=3): (-\frac13 k^3 n^{-2}) → (a=3,b=2) → (b-a/2=1/2) → (i=1,j=1) → (c_{11}=-\frac13).

  5. (r=4): (-\frac14 k^4 n^{-3}) → (a=4,b=3) → (b-a/2=1) → (i=1,j=2) → contribution (-\frac14).

  6. Cross term (p=1) with (r=3): ((-\alpha)(-\frac13) k^4 n^{-3} = \frac{\alpha}{3} k^4 n^{-3}) → same (i=1,j=2) → additional (+\frac{\alpha}{3}). Hence (c_{12} = \frac{\alpha}{3}-\frac14).

  7. Square of (r=3): (\frac12(\frac13)^2 k^6 n^{-4} = \frac1{18} k^6 n^{-4}) → (a=6,b=4) → (b-a/2=1) → (i=2,j=2) → (c_{22}=\frac1{18}).

These match exactly the coefficients used in the solution. The values of (A_t) are also re‑checked using the explicit Bernoulli numbers (B_2=1/6), (B_4=-1/30) and the derivative formula, confirming the constant and (n^{-1/2}) terms in the final expansion. The verification is complete. ∎