Chapter 1
Preliminary Notions
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
(1.1)
an≤b
f(n) =
b
a
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
0
b
a
f(t) dt
an≤b
f(n)
a≤n≤b−1
f(n)
an≤b
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! =
n
i=1
log i =
n
1
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.
1
http://dx.doi.org/10.1090/gsm/134/01
Previous Page Next Page