Section 2.2 Induction
121
Most problems do not work equally well with either form of induction; the
fence post and the programming language problem were somewhat artificial.
Generally, the second principle of induction is called for when the problem
“splits” most naturally in the middle instead of growing from the end.
P with k + 1 factors. P can be written as (S )T, a product of two factors S and T,
where S has r 1 factors and T has r 2 factors. Then 1 ≤ r 1 ≤ k and 1 ≤ r 2 ≤ k, with
r 1 + r 2 = k + 1. By the inductive hypothesis, S and T each have an even number
of parentheses, and therefore so does (S )T = P.
eXAMPLe 23
Prove that for every integer n ≥ 2, n is a prime number or a product of prime numbers.
We will postpone the decision of whether to use the first or the second principle of induction; the basis step is the same in each case and need not start with
1. Obviously here we should start with 2. P(2) is the statement that 2 is a prime
number or a product of primes. Because 2 is a prime number, P(2) is true. Jumping
ahead, for either principle we will be considering the number k + 1. If k + 1 is
prime, we are done. If k + 1 is not prime, then it is a composite number and can be
written as k + 1 = ab. Here k + 1 has been split into two factors. Maybe neither
of these factors has the value k, so an assumption only about P(k) isn’t enough.
Hence, we’ll use the second principle of induction.
So let’s start again. We assume that for all r, 2 ≤ r ≤ k, P(r) is true—r is
prime or the product of primes. Now consider the number k + 1. If k + 1 is
prime, we are done. If k + 1 is not prime, then it is a composite number and
can be written as k + 1 = ab, where 1 < a < k + l and 1 < b < k + l. (This
is a nontrivial factorization, so neither factor can be 1 or k + 1.) Therefore
2 ≤ a ≤ k and 2 ≤ b ≤ k. The inductive hypothesis applies to both a and b, so a
and b are either prime or the product of primes. Thus, k + 1 = ab is the product
of prime numbers. This verifies P(k + 1) and completes the proof by the second
principle of induction.
The proof in Example 23 is an existence proof rather than a constructive
proof. Knowing that every nonprime number has a factorization as a product
of primes does not make it easy to find such a factorization. (We will see in
Section 2.4 that there is, except for the order of the factors, only one such
factorization.) Some encryption systems for passing information in a secure
fashion on the Web depend on the difficulty of factoring large numbers into
their prime factors (see the discussion on public-key encryption in Section 5.6).
eXAMPLe 24
Prove that any amount of postage greater than or equal to 8 cents can be built using
only 3-cent and 5-cent stamps.
Here we let P(n) be the statement that only 3-cent and 5-cent stamps are needed to build n cents worth of postage, and prove that P(n) is true for all n ≥ 8. The
basis step is to establish P(8), which is done by the equation
8 = 3 + 5
121
Most problems do not work equally well with either form of induction; the
fence post and the programming language problem were somewhat artificial.
Generally, the second principle of induction is called for when the problem
“splits” most naturally in the middle instead of growing from the end.
P with k + 1 factors. P can be written as (S )T, a product of two factors S and T,
where S has r 1 factors and T has r 2 factors. Then 1 ≤ r 1 ≤ k and 1 ≤ r 2 ≤ k, with
r 1 + r 2 = k + 1. By the inductive hypothesis, S and T each have an even number
of parentheses, and therefore so does (S )T = P.
eXAMPLe 23
Prove that for every integer n ≥ 2, n is a prime number or a product of prime numbers.
We will postpone the decision of whether to use the first or the second principle of induction; the basis step is the same in each case and need not start with
1. Obviously here we should start with 2. P(2) is the statement that 2 is a prime
number or a product of primes. Because 2 is a prime number, P(2) is true. Jumping
ahead, for either principle we will be considering the number k + 1. If k + 1 is
prime, we are done. If k + 1 is not prime, then it is a composite number and can be
written as k + 1 = ab. Here k + 1 has been split into two factors. Maybe neither
of these factors has the value k, so an assumption only about P(k) isn’t enough.
Hence, we’ll use the second principle of induction.
So let’s start again. We assume that for all r, 2 ≤ r ≤ k, P(r) is true—r is
prime or the product of primes. Now consider the number k + 1. If k + 1 is
prime, we are done. If k + 1 is not prime, then it is a composite number and
can be written as k + 1 = ab, where 1 < a < k + l and 1 < b < k + l. (This
is a nontrivial factorization, so neither factor can be 1 or k + 1.) Therefore
2 ≤ a ≤ k and 2 ≤ b ≤ k. The inductive hypothesis applies to both a and b, so a
and b are either prime or the product of primes. Thus, k + 1 = ab is the product
of prime numbers. This verifies P(k + 1) and completes the proof by the second
principle of induction.
The proof in Example 23 is an existence proof rather than a constructive
proof. Knowing that every nonprime number has a factorization as a product
of primes does not make it easy to find such a factorization. (We will see in
Section 2.4 that there is, except for the order of the factors, only one such
factorization.) Some encryption systems for passing information in a secure
fashion on the Web depend on the difficulty of factoring large numbers into
their prime factors (see the discussion on public-key encryption in Section 5.6).
eXAMPLe 24
Prove that any amount of postage greater than or equal to 8 cents can be built using
only 3-cent and 5-cent stamps.
Here we let P(n) be the statement that only 3-cent and 5-cent stamps are needed to build n cents worth of postage, and prove that P(n) is true for all n ≥ 8. The
basis step is to establish P(8), which is done by the equation
8 = 3 + 5