Page 357 - Discrete Mathematics and Its Applications

336 5 / Induction and Recursion

Webeginwithoneofthemostprominentusesofstronginduction,thepartofthefundamental
theorem of arithmetic that tells us that every positive integer can be written as the product of
primes.
EXAMPLE 2 Show that if n is an integer greater than 1, then n can be written as the product of primes.

Solution: Let P (n) be the proposition that n can be written as the product of primes.
BASIS STEP: P(2) is true, because 2 can be written as the product of one prime, itself. (Note
that P(2) is the first case we need to establish.)

INDUCTIVE STEP: The inductive hypothesis is the assumption that P(j) is true for all
integers j with 2 ≤ j ≤ k, that is, the assumption that j can be written as the product of primes
whenever j is a positive integer at least 2 and not exceeding k. To complete the inductive step,
it must be shown that P(k + 1) is true under this assumption, that is, that k + 1 is the product
of primes.
There are two cases to consider, namely, when k + 1 is prime and when k + 1 is composite.
If k + 1 is prime, we immediately see that P(k + 1) is true. Otherwise, k + 1 is composite and
can be written as the product of two positive integers a and b with 2 ≤ a ≤ b< k + 1. Because
both a and b are integers at least 2 and not exceeding k, we can use the inductive hypothesis to
write both a and b as the product of primes. Thus, if k + 1 is composite, it can be written as the
product of primes, namely, those primes in the factorization of a and those in the factorization
of b. ▲

Remark: Because 1 can be thought of as the empty product of no primes, we could have started
the proof in Example 2 with P(1) as the basis step. We chose not to do so because many people
find this confusing.

Example 2 completes the proof of the fundamental theorem of arithmetic, which asserts that
every nonnegative integer can be written uniquely as the product of primes in nondecreasing
order. We showed in Section 4.3 that an integer has at most one such factorization into primes.
Example 2 shows there is at least one such factorization.
Next, we show how strong induction can be used to prove that a player has a winning
strategy in a game.

EXAMPLE 3 Consider a game in which two players take turns removing any positive number of matches they
want from one of two piles of matches. The player who removes the last match wins the game.
Show that if the two piles contain the same number of matches initially, the second player can
always guarantee a win.

Solution: Let n be the number of matches in each pile. We will use strong induction to prove
P (n), the statement that the second player can win when there are initially n matches in each
pile.
BASIS STEP: When n = 1, the first player has only one choice, removing one match from one
of the piles, leaving a single pile with a single match, which the second player can remove to
win the game.
INDUCTIVE STEP: The inductive hypothesis is the statement that P(j) is true for all j with
1 ≤ j ≤ k, that is, the assumption that the second player can always win whenever there are j
matches, where 1 ≤ j ≤ k in each of the two piles at the start of the game. We need to show that
P(k + 1) is true, that is, that the second player can win when there are initially k + 1 matches in
each pile, under the assumption that P(j) is true for j = 1, 2,...,k. So suppose that there are
k + 1 matches in each of the two piles at the start of the game and suppose that the first player
removes r matches (1 ≤ r ≤ k) from one of the piles, leaving k + 1 − r matches in this pile.
By removing the same number of matches from the other pile, the second player creates the