## Strong Mathematical Induction

Also known as course-of-values induction, strong induction adds to mathematical induction by showing that additional assertions hold if mathematical induction holds.

**3.5 Strong Mathematical Induction**

There is a second form of the principle of mathematical induction which is useful in some cases. To apply the first form of induction, we assume *P*(*k*) for an arbitrary natural number *k *and show that *P*(*k *+ 1) follows from that assumption. In the second form of induction, the assumption is that *P*(*x*) holds for all *x *between 0 and *k *inclusive, and we show that *P*(*k *+ 1) follows from this. This gives us a lot more to work with when deducing *P*(*k *+ 1). We will need this second, stronger form of induction in the next two sections. A proof will be given in the next chapter.

**Theorem 3.9. ***Let P be a one-place predicate whose domain of discourse includes the natural numbers. Suppose that P*(0) *is true and that*

(*P*(0) ∧ *P*(1) ∧ · · · ∧*P*(*k*)) *→ **P*(*k *+ 1)

*is true for each natural number k *≥ 0*. Then P*(*n*) *is true for every natural number n.*

For example, we can use this theorem to prove that every integer greater than one can be written as a product of prime numbers (where a number that is itself prime is considered to be a product of one prime number). The proof illustrates an important point about applications of this theorem: When proving *P*(*k *+ 1), you don't necessarily have to *use *the assumptions that *P*(0), *P*(1), …, and *P*(*k*) are true. If *P*(*k *+ 1) is proved by *any *means – possibly including the assumptions – then the statement (*P*(0) ∧ *P*(1) ∧ *· · · *∧ *P*(*k*)) *→ **P*(*k *+ 1) has been shown to be true. It follows from this observation that several numbers, not just zero, can be 'base cases' in the sense that *P*(*x *+ 1) can be proved independently of *P*(0) through *P*(*x*). In this sense, 0, 1, and every prime number are base cases in the following theorem.

**Theorem 3.10. ***Every natural number greater than one can be written as a product of prime numbers.*

*Proof. *Let *P*(*n*) be the statement "if *n *> 1, then *n *can be written as a product of prime numbers". We will prove that *P*(*n*) is true for all *n *by applying the second form of the principle of induction.

Note that *P*(0) and *P*(1) are both automatically true, since *n *= 0 and *n *= 1 do not satisfy the condition that *n *> 1, and *P*(2) is true since 2 is the product of the single prime number 2. Suppose that *k *is an arbitrary natural number with *k *> 1, and suppose that *P*(0), *P*(1), …, *P*(*k*) are already known to be true; we want to show that *P*(*k *+ 1) is true. In the case where *k *+ 1 is a prime number, then *k *+ 1 is a product of one prime number, so *P*(*k *+ 1) is true.

Consider the case where *k *+ 1 is not prime. Then, according to the definition of prime number, it is possible to write *k *+ 1 = *ab *where *a *and *b *are numbers in the range from 2 to *k *inclusive. Since *P*(0) through *P*(*k*) are known to be true, *a *and *b *can each be written as a product of prime numbers. Since *k *+ 1 = *ab*, *k *+ 1 can also be written as a product of prime numbers. We have shown that *P*(*k *+ 1) follows from *P*(0) ∧ *P*(1) ∧* · · · *∧ *P*(*k*), and this completes the induction.

##### 3.7.3 Course of Values Induction

A second variation allows for the expansion of the induction hypothesis. The course-of-values principle includes the previous generalization. It is also some- times called *strong induction*.

**Theorem 3.7.9: ****The Course-of-Values Principle of Mathematical Induction. ***If p*(*n*) *is a proposition over *{*k*_{0}*, k*_{0} + 1*, k*_{0} + 2*, . . .*}*, **where k*_{0 }*is any **integer, then p*(*n*) *is a tautology if*

*p*(*k*_{0})*is true, and**for all n*≥*k*_{0}*, p*(*k*_{0})*, p*(*k*_{0}+ 1)*, ..., p*(*n*) ⇒*p*(*n*+ 1)*.*

A prime number is defined as a positive integer that has exactly two positive divisors, 1 and itself. There are an infinite number of primes. The list of primes starts with 2*, *3*, *5*, *7*, *11*, . . . *. The proposition over {2, 3, 4, ...} that we will prove here is *p*(*n*): *n *can be written as the product of one or more primes. In most texts, the assertion that *p*(*n*) is a tautology would appear as

**Theorem 3.7.10: Existence ****of Prime Factorizations. ***Every positive integer greater than or equal to 2 has a prime decomposition.*

*Proof. *If you were to encounter this theorem outside the context of a discussion of mathematical induction, it might not be obvious that the proof can be done by induction. Recognizing when an induction proof is appropriate is mostly a matter of experience. Now on to the proof!

Basis: Since 2 is a prime, it is already decomposed into primes (one of them).

Induction: Suppose that for some *n *≥ 2 all of the integers 2 *, *3*, ..., n *have a prime decomposition. Notice the course-of-value hypothesis. Consider *n *+ 1. Either *n *+ 1 is prime or it isn't. If *n *+ 1 is prime, it is already decomposed into primes. If not, then *n *+ 1 has a divisor, *d*, other than 1 and *n *+ 1.

Hence, *n *+ 1 = *cd *where both *c *and *d *are between 2 and *n*. By the induction hypothesis, *c *and *d *have prime decompositions, *c*_{1}*c*_{2}*· · · **c** _{s}* and

*d*

_{1}

*d*

_{2}

*· · ·*

*d*

*, respectively. Therefore,*

_{t }*n*+ 1 has the prime decomposition

*c*

_{1}*c*

_{2}

*· · ·*

*c*

_{s}*d*

_{1}

*d*

_{2}

*· · ·*

*d*

*.*

_{t}

**P****eano Postulates ****and Induction. **Mathematical induction originated in the late nineteenth century. Two mathematicians who were prominent in its development were Richard Dedekind and Giuseppe Peano. Dedekind developed a set of axioms that describe the positive integers. Peano refined these axioms and gave a logical interpretation to them. The axioms are usually called the Peano Postulates.

**Axiom 3.7.11: Peano Postulates. ***The system of positive integers consists of a nonempty set, *ℙ*; a least element of *ℙ*, denoted 1; and a "successor function", s, with the properties*

*If k*∈ ℙ*, then there is an element of*ℙ*c**al**led the successor of k, denoted**s*(*k*)*.**No two elements of*ℙ*have the same successor.**No element of*ℙ*has*1*as its successor.**If S*⊆ ℙ*,*1 ∈*S**, and k*∈*S*⇒*s*(*k*) ∈*S**, then S*= ℙ*.*

Notes:

- You might recognize
*s*(*k*) as simply being*k*+ 1. - Axiom 4 is the one that makes mathematical induction possible. In an induction proof, we simply apply that axiom to the truth set of a proposition.

Source: Al Doerr and Ken Levasseur, http://faculty.uml.edu/klevasseur/ads-latex/ads.pdf

This work is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 3.0 License.