What Is Mathematics? An Elementary Approach to Ideas and Methods, 2nd Edition (1996)
SUPPLEMENT TO CHAPTER VIII
§2. ORDERS OF MAGNITUDE
1. The Exponential Function and Powers of x
Frequently in mathematics we encounter sequences an which tend to infinity. Often we need to compare such a sequence with another sequence, bn, also tending to infinity, but perhaps “faster” than an. To make this concept precise, we shall say that bn tends to infinity faster than an, or has a higher order of magnitude than an, if the ratio an/bn (numerator and denominator of which both tend to infinity) tends to zero as n increases. Thus the sequence bn = n2 tends to infinity faster than the sequence an = n, and the latter in turn faster than , for
It is clear that ns tends to infinity faster than nr whenever s > r > 0, since then nr/ns = 1/n(s–r) → 0.
If the ratio an/bn approaches a finite constant c, different from zero, we say that the two sequences an and bn approach infinity at the same rate or have the same order of magnitude. Thus an = n2 and bn = 2n2 + n have the same order of magnitude, since
One might think that with the powers of n as a yardstick one could measure the different degrees of becoming infinite for any sequence an that tends to infinity. To do this one would have to find a suitable power ns with the same order of magnitude as an; i.e. such that an/ns tends to a finite constant different from zero. It is a remarkable fact that this is by no means always possible, since the exponential function an with a > 1 (e.g. en) tends to infinity faster than any power ns, however large we choose s, while log n tends to infinity slower than any power ns, however small the positive exponent s. In other words, we have the relations
(1)
and
(2)
as n → ∞. The exponent s here need not be an integer, but may be any fixed positive number.
To prove (1) we first simplify the statement by taking the sth root of the ratio; if the root tends to zero, the original ratio does also. Hence we need only prove that
as n increases. Let b = a1/s; since a is assumed to be greater than 1, b and also will be greater than 1. We may write
b = 1 + q,
where q is positive. Now by the inequality (6) on page 15,
bn/2 = (1 + q)n ≥ 1 + nq > nq,
so that
an/s = bn > n2q2
and
Since the latter quantity tends to zero as n increases, the proof is complete.
As a matter of fact, the relation
(3)
holds when x becomes infinite in any manner by running through a sequence x1, x2,..., which need not coincide with the sequence 1, 2, 3,... of positive integers. For if n – 1 ≤ x ≤ n, then
This remark may be used to prove (2). Setting x = log n and es = a, so that n = ex and ns = (es)x, the ratio in (2) becomes
which is the special case of (3) for s = 1.
Exercises: 1) Prove that for x → ∞ the function log log x tends to infinity more slowly than log x. 2) The derivative of x/log x is 1/log x – 1/(log x)2. Prove that for large x it is “asymptotically” equivalent to the first term, 1/log x, i.e. that their ratio tends to 1 as x → ∞.
2. Order of Magnitude of log (n!)
In many applications, e.g. in the theory of probability, it is important to know the order of magnitude or “asymptotic behavior” of n! for large values of n. We shall here be content with studying the logarithm of n!, i.e. the expression
Pn = log 2 + log 3 + log 4 +... + log n.
We shall show that the “asymptotic value” of Pn is given by n log n; i.e. that
as n → ∞.
The proof is typical of a much used method of comparing a sum with an integral. In Figure 287 the sum Pn is equal to the sum of the areas of the rectangles whose tops are marked by solid lines, and which together do not exceed the area
Fig. 287. Estimation of log (n!).
under the logarithmic curve from 1 to n + 1 (see p. 450, Exercise 1)). But the sum Pn is likewise equal to the total area of the rectangles whose tops are marked by broken lines and which together exceed the area under the curve from 1 to n, given by
Thus we have
and dividing by n log n,
Obviously the two bounds tend to 1 as n tends to infinity, and our statement is proved.
Exercise: Prove that the two bounds are greater than 1 – 1/n and less than 1 + 1/n respectively.