The Art and Craft of Problem Solving

322 CHAPTER 9 CALCULUS

Since the sequence is monotonic and bounded, it must converge. Now let us show

that it converges to Va. Since 0 is a much easier number to work with, let us define

the sequence of "error" values En by

En := Xn -Va,

and show that En -+ O. Note that the En are all non-negative. Now we look at the ratio

of En+! to En to see how the error changes, hoping that it decreases dramatically. We

have (aren't you glad you studied factoring in Section 5.2?)

Thus

En+! = Xn+! - Va

= � (xn+�)-Va

2 Xn

x� + a -2xnVa

2xn

(xn -Va)^2

2xn

En^2

2xn

En+! En Xn -Va Xn 1

--=-= <-=-.

En 2xn 2xn 2xn 2

Since this ratio is also positive, we are guaranteed that limn-+oo En = 0, using the

squeeze principle on page 318.

We are done; we have shown that Xn -+ Va. •

The trickiest part in the example above was guessing that the limit was Va. What

if we hadn't been lucky enough to have a nice picture? There is a simple but very

productive tool that often works when a sequence is defined recursively. Let us apply

it to the previous example. If Xn -+ L, then for really large n, both Xn and xn+! approach

L. Thus, as n approaches infinity, the equation Xn+! = (xn + a/xn)/ 2 becomes

L=�(L+I)'

and a tiny bit of algebra yields L = Va. This solve fo r the limit tool does not prove

that the limit exists, but it does show us what the limit must equal if it exists.

Here is a tricky problem that has several solutions. We will present one that em­

ploys big-Oh estimates.

Example 9.2.3 (Putnam 19 90) Is v'2 the limit of a sequence of numbers of the form

ifJi-Tm (n ,m = 0, 1,2, ... )?

Partial Solution: Your intuition should suggest that the answer is yes, because,

for "large enough integers, cube roots get closer to each other, so we can approach any

number." Let's sketch a solution that formalizes this idea.