The Art and Craft of Problem Solving

3.2 THE EXTREME PRINCIPLE 79

Now assume the inductive hypothesis that all sequences of length n will eventually

become unchanging. Consider an (n + 1 )-e1ement sequence

U\, U 2 , ... ,Un, Un+l·

We will perform the erase-and-replace operation repeatedly on this sequence, with the
understanding that we perform only operations that produce change, and at each stage,
we will arrange the terms in increasing order. We make some simple observations:

(^1). The least element in the sequence at any possible stage is at least equal to the
greatest common divisor of all of the original elements.

2. The greatest element in the sequence at any possible stage is at most equal to

the least common mUltiple of all of the original elements.

3. The least element at any given stage is always less than or equal to the least

element at the previous stage.

4. Since we arrange the terms in increasing order, observations (1) and (2) imply

that there are only finitely many sequences possible.

As we perform erase-and-replace operations to the sequence, let £j be the least
element of the sequence at stage i. There are two possible scenarios.

• Eventually we will no longer be able to change the sequence, in which case the
  least-element sequence £ 1 , £ 2 , £ 3 , ... terminates.

• At some point, say stage k, we will return to a sequence that previously oc­

curred (because of observation (4) above). Then the least-element sequence

£ I, £ 2 , £ 3 , ... may be infinite, but £k = £k + 1 = £k+ 2 = .. " due to observation (3)

above.

Consequently, for each initial sequence U\,U 2 , ... ,Un,Un+l, depending on how it

evolves, there will be a stage k and a number £ := £k that is the smallest least element

that ever occurs at any stage.

This number £ must divide all the other elements of the sequence at stage k and

all later stages, for otherwise, we could erase-and-replace £ with another element to
produce a smaller least element, which contradicts the minimality of £. Therefore,

once we reach stage k, the least element £ is out of the picture-the only possibility

for erasing-and-replac ing to produce change is to use the remaining n elements. But

the inductive hypothesis says that eventually, these n elements will no longer change.

Thus, eventually, our original (n + 1 )-element sequence will no longer change. _

In more complicated problems, it is not always obvious what entities should be
monotonized, and the Well -Ordering Principle is not always true for infinite sets. In
situations involving infinite sets, sometimes extremal arguments work, but you need to
be careful.

Example 3.2.5 Let f(x) be a polynomial with real coefficients of degree n such that

f(x) 20 for all x E�. Define g(x) := f(x) + f'(x) + !,,(x)··· + f(n) (x). Show that

g(x) 2 0 for all x E�.