ORDERS OF MAGNITUDE - SUPPLEMENT TO CHAPTER VIII - What Is Mathematics? An Elementary Approach to Ideas and Methods, 2nd Edition (1996)

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 image, for

image

It is clear that ns tends to infinity faster than nr whenever s > r > 0, since then nr/ns = 1/n(sr) → 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

image

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)    image

and

(2)    image

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

image

as n increases. Let b = a1/s; since a is assumed to be greater than 1, b and also image will be greater than 1. We may write

bimage = 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

image

Since the latter quantity tends to zero as n increases, the proof is complete.

As a matter of fact, the relation

(3)    image

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 ≤ xn, then

image

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

image

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

image

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

image

Fig. 287. Estimation of log (n!).

image

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

image

Thus we have

image

and dividing by n log n,

image

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.