Bound by a Riemann sum

Quick description

This method - a combination of the divide and conquer strategy and the base times height bound - is almost embarrassingly obvious: the Riemann integral $\int_a^bf(x)dx$ is defined to be the infimum over all sums of the form $x_{i-1}\leq x\leq x_i\}$ over all dissections $a=x_0<x_1<\dots<x_n=b.$ Therefore, any such sum gives us an upper bound for the integral. Often one can get useful bounds by taking very simple sums with $n$ equal to 1 or 2. (When $n=1$ we are using the base times height technique.)

Prerequisites

First-year calculus

Example 1

The integral test for convergence is a classic example of this method: if $[1,+\infty] \to \R^+$ is a monotone non-increasing function, then $\sum_{n=1}^\infty f(n)$ converges if and only if the integral $\int_1^\infty f(x)\ dx$ is finite. Indeed from taking upper and lower Riemann sums one obtains the bounds

$\sum_{n=2}^\infty f(n) \leq \int_1^\infty f(x)\ dx \leq \sum_{n=1}^\infty f(n).$

Note that this method can fail completely if $f$ is non-monotone, and in particular if it oscillates at a wavelength significantly smaller than $1$ .

Example 2

Suppose you are asked to prove that the integral $\int_{-1}^1(1-x^2)^ndx$ tends to $0$ as $n$ tends to infinity. One can use relatively sophisticated tools such as the monotone convergence theorem to prove this (since the pointwise limit of the functions $f_n(x)=(1-x^2)^n$ is the function that is $0$ when $x\in[-1,1]\setminus\{0\}$ and $1$ when $x=0$ ). However, one can also prove it simply and directly as follows. We use the fact that the functions $(1-x^2)^n$ decrease as $|x|$ increases. Therefore, for any $\delta>0$ we can split the interval $[-1,1]$ into the three parts $[-1,-\delta],$ $[-\delta,\delta]$ and $[\delta,1]$ and thereby obtain the upper bound $2(1-\delta)(1-\delta^2)^n+2\delta,$ which is at most $2(\delta+(1-\delta^2)^n).$ At this point, all we have to do is choose $\delta$ to make this quantity small. We could argue abstractly that for every $\delta>0$ the quantity tends to $2\delta$ as $n\rightarrow\infty,$ which proves the result we wanted, or we could be slightly more ambitious and try to find $\delta$ that minimizes, or at least comes close to minimizing, the expression in question.

Let us briefly see what happens if we go for the second approach. As is often the case, if we want to have a reasonable idea of what the minimum is, we should try to choose $\delta$ so that the two parts of the expression are equal. How do we get $\delta$ to equal $(1-\delta^2)^n$ ? If $\delta=n^{-1/2},$ then $(1-\delta^2)^n\rightarrow e^{-1},$ so we need to take a larger $\delta.$ Bearing in mind that $(1-\delta^2)^n$ is close to $e^{-\delta^2n},$ a pretty good choice is $\delta=n^{-1/2}(\log n)^{1/2},$ in which case $e^{-\delta^2n}=n^{-1}.$ With a little bit of work, one can prove that this choice of $\delta$ leads to an upper bound for the integral of at most $3n^{-1/2}(\log n)^{1/2},$ which tends to $0.$

Example 3

Suppose one wants to show that the contour integral $\int_{C_r} \frac{e^{iz}}{z+i}\ dz$ goes to zero in magnitude as $r \to \infty$ , where $C_r$ is the semicircular contour $0 \leq \theta \leq \pi\}$ . (This is a special case of Jordan's lemma, but pretend for now that one is not aware of this lemma.) A direct application of the base times height bound, using the fact that $e^{iz}$ is bounded in magnitude by $1$ , gives an upper bound of the base $\pi r$ times the height $\frac{1}{r-1}$ (for $r>1$ ); but unfortunately $\pi r \times \frac{1}{r-1}$ does not go to zero as $r \to \infty$ .

But one can do better by noting that the bound $|e^{iz}| \leq 1$ is usually quite inefficient. Indeed, if $z=x+iy$ , then $|e^{iz}| = e^{-y}$ . Thus as soon as $y$ is even moderately large, e.g. $y \geq \log r$ , then $e^{iz}$ is actually quite small, e.g. $|e^{iz}| \leq 1/r$ .

This suggests performing the following Riemann sum: in the region $\hbox{Im}(z) \geq \log r$ (say), use the upper bound $|\frac{e^{iz}}{z+i}| \leq \frac{1/r}{r-1}$ ; in the remaining region $\hbox{Im}(z) < \log r$ , use the cruder bound $|\frac{e^{iz}}{z+i}| \leq \frac{1}{r-1}$ . The length of the curve in the first region can be bounded crudely by the length $\pi r$ of the whole curve; meanwhile, the length of the curve in the second region can be bounded by $C \log r$ for some absolute constant $C$ . This leads to a net upper bound of