1.1. Approximating a sum by an integral
In certain situations, it is useful to replace a sum by an integral. The
following result shows when and how this can be done.
Proposition 1.1. Let a, b ∈ N with a b and let f : [a, b] → R be a
monotonic function on [a, b]. There exists a real number θ = θ(a, b) such
that −1 ≤ θ ≤ 1 and such that
f(t) dt + θ(f(b) − f(a)).
Proof. Indeed, assume that f is decreasing, in which case, using a geometric
approach, it is easy to see that
f(t) dt −
f(n) = f(a) − f(b),
from which (1.1) follows easily. If on the other hand, f is increasing, the
same type of argument yields (1.1).
One can use this result to estimate log n!. Indeed, setting f(n) = log n
in (1.1), one obtains
log n! =
log i =
log t dt + θ(log n − log 1) = n log n − n + O(log n),
thus providing a fairly good approximation for log n!. A better estimate is
proved in Section 1.9.