The Art and Craft of Problem Solving

9.2 CONVERGENCE AND CONTINUITY 319

This forces Xn -t O. Conversely, if the tenus of a sequence are greater in ab­

solute value than the corresponding tenus of a sequence that diverges (has

infinite limit), then the sequence in question also diverges.

6. Use Big-Oh and Little-oh Analysis. Most convergence investigations require
   estimates and comparisons. The big-and little-oh notations give us a system­
   atic way to describe growth rates of functions as the variable tends towards
   infinity or zero.
   We say that f(x) = O(g(x)) ("f is big-Oh g") if there exists a constant C such
   that I f(n) 1 ::; qg(n) 1 for all sufficiently large n. We say that f(x) = o(g(x))
   if limx--->oof(x)/g(x) = O. For example, f(x) = O(x^3 ) means that, for large
   enough x, we can bound f(x) by a cubic. On the other hand, f(x) = o (x^3 )
   means that f(x) grows fundamentally slower than a cubic.
   We can also use this notation to describe behavior near zero. If we say f (x) =
   O(g(x )) "as x -t 0," this means that f(x) is bounded by a constant multiple of
   g(x) for sufficiently small, but nonzero values of x. Likewise, we can define
   f (x) = o (g(x)) as x -t O.
   This notation is useful for two reasons: it allows us to focus on the parts of a
   function "that matter." For example, when x is small, it may be very helpful
   to know that f(x) = x + O( v'x) as x -t 0, especially if we are comparing it,
   say, with another function that is x + O ( V'x) as x -t O. Also, we can do simple
   algebra with the "oh" functions. For example, If f(x) = O(xl), then xf(x) =
   O (x^3 ), etc.

The next few examples illustrate some of these ideas. In the first example, our
goals are modest-just to find some decent bounds for an infinite sequence. However,
the process is instructive.

Example 9.2.1 Let an = (I + 1/2 )(1 + 1/4 )··· (1 + 1/ 2 n). Find upper and lower

bounds a, b such that a::; nlim an ::; b.
--->oo

Solution: Define the product

S(x,n) = (1 +x)( 1 +xl) ... (1 +�),

where 0 < x < 1. What we are interested in is the limiting value of S (x,n) as n -t 00,
which we will denote by S(x).
By mUltiplying out but ignoring repeated tenus, it is clear that

(4)

since all powers of x will appear in the product (with coefficients of at least I).

To get an inequality going the other direction, we need a more subtle analysis. We
claim that for any integer m, we have