TAOCP 1.2.11.3 Exercise 19

Section 1.2.11.3: Some Asymptotic Calculations

Exercise 19. [HM30] (Watson's lemma.) Show that if the integral

$$ C_n = \int_0^\infty e^{-nx} f(x),dx $$

exists for all large $n$, and if $f(x)=O(x^\alpha)$ for $0 \le x \le r$, where $r>0$ and $\alpha>-1$, then

$$ C_n = O(n^{-1-\alpha}). $$

Verified: yes
Solve time: 6m56s

---

The reviewer is correct: the original proof fails because it implicitly assumes absolute convergence of a Laplace integral from mere convergence. The tail estimate must be redone from scratch.

Corrected solution

Let

$$ C_n=\int_0^\infty e^{-nx}f(x),dx, $$

and assume:

1. $C_n$ exists for all sufficiently large $n$;
2. there are constants $K>0$, $r>0$, and $\alpha>-1$ such that

$$ |f(x)|\le Kx^\alpha \qquad (0\le x\le r). $$

We must prove that

$$ C_n=O(n^{-1-\alpha}). $$

Fix $N$ such that $C_N$ exists. Then $C_n$ exists for every $n\ge N$.

Split the integral at $r$:

$$ C_n = \int_0^r e^{-nx}f(x),dx + \int_r^\infty e^{-nx}f(x),dx =:A_n+B_n . $$

We estimate $A_n$ and $B_n$ separately.

Estimate of $A_n$

Using $|f(x)|\le Kx^\alpha$ on $[0,r]$,

$$ |A_n| \le K\int_0^r e^{-nx}x^\alpha,dx. $$

Substitute $u=nx$. Then $x=u/n$ and $dx=du/n$, giving

$$ |A_n| \le K n^{-1-\alpha} \int_0^{nr} e^{-u}u^\alpha,du. $$

Since $\alpha>-1$,

$$ \int_0^{nr} e^{-u}u^\alpha,du \le \int_0^\infty e^{-u}u^\alpha,du = \Gamma(\alpha+1). $$

Hence

$$ |A_n| \le K\Gamma(\alpha+1),n^{-1-\alpha}, $$

so

$$ A_n=O(n^{-1-\alpha}). $$

Estimate of $B_n$

The previous proof incorrectly tried to deduce absolute convergence. Instead, use only the existence of $C_N$.

Define

$$ D:=\int_r^\infty e^{-Nx}f(x),dx . $$

This improper integral exists because $C_N$ exists and

$$ \int_0^r e^{-Nx}f(x),dx $$

is an ordinary finite integral.

For $n\ge N$, write

$$ B_n = \int_r^\infty e^{-(n-N)x}\bigl(e^{-Nx}f(x)\bigr),dx. $$

Let

$$ g(x)=e^{-Nx}f(x). $$

Then $\int_r^\infty g(x),dx$ converges.

Set

$$ G(t)=\int_r^t g(x),dx. $$

Since the improper integral of $g$ converges, $G(t)$ has a finite limit as $t\to\infty$. Therefore $G$ is bounded: there exists $M>0$ such that

$$ |G(t)|\le M \qquad (t\ge r). $$

Now integrate by parts on $[r,T]$:

$$ \int_r^T e^{-(n-N)x}g(x),dx = e^{-(n-N)T}G(T) - e^{-(n-N)r}G(r) + (n-N)\int_r^T e^{-(n-N)x}G(x),dx . $$

Since $G(r)=0$,

$$ \int_r^T e^{-(n-N)x}g(x),dx = e^{-(n-N)T}G(T) + (n-N)\int_r^T e^{-(n-N)x}G(x),dx . $$

Let $T\to\infty$. Because $G(T)$ is bounded and $e^{-(n-N)T}\to0$,

$$ B_n = (n-N)\int_r^\infty e^{-(n-N)x}G(x),dx . $$

Hence

$$ |B_n| \le M(n-N)\int_r^\infty e^{-(n-N)x},dx. $$

Evaluating the integral,

$$ (n-N)\int_r^\infty e^{-(n-N)x},dx = e^{-(n-N)r}, $$

so

$$ |B_n| \le M e^{-(n-N)r}. $$

Therefore

$$ B_n=O!\left(e^{-(n-N)r}\right). $$

Since every exponential decay dominates every negative power, there exists a constant $M_1$ such that

$$ e^{-(n-N)r} \le M_1 n^{-1-\alpha} \qquad (n\ge N). $$

Thus

$$ B_n=O(n^{-1-\alpha}). $$

Conclusion

Combining the estimates,

$$ C_n=A_n+B_n, $$

with

$$ A_n=O(n^{-1-\alpha}), \qquad B_n=O(n^{-1-\alpha}). $$

Therefore

$$ \boxed{,C_n=O(n^{-1-\alpha}),}. $$

This proves the result. ∎