Discrete Mathematics for Computer Science

Strong Form of Mathematical Induction 67

for some prime numbers P1, P2 ...- Pk. The pi's are not required to be distinct, and

k simply denotes the number of factors needed to express p. For example, 4 = 2.2 is a

factorization of 4 into two primes. If k = 1, then n is a prime, and n = n is a factorization

into primes. We just define the term factorization into primes to include the one-prime

case.

The proof that every integer n > 1 can be factored into primes goes as follows: If n is

prime, then n = n is a factorization of n into primes. Otherwise, if n is not a prime, then n

can be factored as n = k -m for some integers m and k where n > m, k > 1. Since k and

m are both less than n, we can conclude that m and k can be factored. We would now use

the factorizations of m and k to form a factorization of n.

This is not an application of an inductive hypothesis as induction has been presented

so far. The problem is that the Principle of Mathematical Induction only uses the result for

n - 1 to prove the result for n = (n - 1 + 1). Here, the result for n has to be proved from

the same result for two smaller numbers k and m, neither of which (it turns out) is n - 1.

In fact, k, m < n/2.

The Strong Form of Mathematical Induction has a somewhat different form of in-

ductive hypothesis: It assumes the result for all natural numbers k where no _< k < n-

with no E N just as before-and then proves the result for n. This was what we needed

for factoring-whatever k, m are, we get to apply the inductive hypothesis to both of

them.

We now give a formal statement of this new form of induction and then complete the

proof that every integer can be written as a product of primes.

Strong Form of Mathematical Induction

Let T C N and no E N. Suppose that for all natural numbers n > no, if no, no +

1 .... n - l E T, then n E T. Then, every natural number n > no is in T.

If no is equal to zero, then the Strong Form of Mathematical Induction proves that

T-=N.

The Strong Form of Mathematical Induction is also sometimes called Complete In-
duction or Course of Values Induction. It is the inductive hypothesis which is "stronger"
not the principle itself. Indeed, any theorem provable with the strong form of induction is
also provable with the first form, but such proofs may require some awkward complica-
tions.
To use the strong form of induction, one must prove the if-then statement that

if no, no + 1 ..... n -ET, 1 c then n E T

Virtually always, the proof is broken into cases. For some values of n, including no, the
result is proven directly; this set of cases is sometimes called the base step. For the other
values of n, the result is proved using the assumption that no, no + 1 .... n - 1 E T. This
is called the inductive step, and that assumption is called the inductive hypothesis.