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
Previous Page Next Page