118
Proofs, Induction, and Number Theory
Second Principle of Induction
In addition to the first principle of induction, which we have been using,
1. P(1) is true
2. (4k)[P(k) true S P(k + 1) true]
there is a second principle of induction.
f S P(n) true for all positive integers n
PRinciPLe SECoND PrINCIPlE oF MaThEMaTICal INDuCTIoN
1′. P(1) is true
2′. (4k)[P(r) true for all r,
1 ≤ r ≤ k S P(k + 1) true]
¶ S P(n) true for all positive integers n
dimensions 2
k+1
× 2
k+1
. We need to show that it can be tiled when one square is removed. To relate the k + 1 case to the inductive hypothesis, divide the 2
k+1
× 2
k+1
checkerboard into four quarters. Each quarter will be a 2
k
× 2
k
checkerboard, and
one will have a missing square (Figure 2.3c). By the inductive hypothesis, this
checkerboard can be tiled. Remove a corner from each of the other three checkerboards, as in Figure 2.3d. By the inductive hypothesis, the three boards with the holes
removed can be tiled, and one angle iron can tile the three holes. Hence the original
2
k+1
× 2
k+1
board with its one hole can be tiled.
(d)
(c)
(b)
(a)
Figure 2.3
These two induction principles differ in statements 2 and 2′. In statement 2,
we must be able to prove for an arbitrary positive integer k that P(k + 1) is true
based only on the assumption that P(k) is true. In statement 2′, we can assume
that P(r) is true for all integers r between 1 and an arbitrary positive integer k in
order to prove that P(k + 1) is true. This seems to give us a great deal more “ammunition,” so we might sometimes be able to prove the implication in 2′ when we
cannot prove the implication in 2.
What allows us to deduce (4n)P(n) in either case? We will see that the two induction principles themselves, that is, the two methods of proof, are equivalent. In
other words, if we accept the first principle of induction as valid, then the second
principle of induction is valid, and conversely. In order to prove the equivalence
of the two induction principles, we’ll introduce another principle, which seems so
obvious as to be unarguable.
Proofs, Induction, and Number Theory
Second Principle of Induction
In addition to the first principle of induction, which we have been using,
1. P(1) is true
2. (4k)[P(k) true S P(k + 1) true]
there is a second principle of induction.
f S P(n) true for all positive integers n
PRinciPLe SECoND PrINCIPlE oF MaThEMaTICal INDuCTIoN
1′. P(1) is true
2′. (4k)[P(r) true for all r,
1 ≤ r ≤ k S P(k + 1) true]
¶ S P(n) true for all positive integers n
dimensions 2
k+1
× 2
k+1
. We need to show that it can be tiled when one square is removed. To relate the k + 1 case to the inductive hypothesis, divide the 2
k+1
× 2
k+1
checkerboard into four quarters. Each quarter will be a 2
k
× 2
k
checkerboard, and
one will have a missing square (Figure 2.3c). By the inductive hypothesis, this
checkerboard can be tiled. Remove a corner from each of the other three checkerboards, as in Figure 2.3d. By the inductive hypothesis, the three boards with the holes
removed can be tiled, and one angle iron can tile the three holes. Hence the original
2
k+1
× 2
k+1
board with its one hole can be tiled.
(d)
(c)
(b)
(a)
Figure 2.3
These two induction principles differ in statements 2 and 2′. In statement 2,
we must be able to prove for an arbitrary positive integer k that P(k + 1) is true
based only on the assumption that P(k) is true. In statement 2′, we can assume
that P(r) is true for all integers r between 1 and an arbitrary positive integer k in
order to prove that P(k + 1) is true. This seems to give us a great deal more “ammunition,” so we might sometimes be able to prove the implication in 2′ when we
cannot prove the implication in 2.
What allows us to deduce (4n)P(n) in either case? We will see that the two induction principles themselves, that is, the two methods of proof, are equivalent. In
other words, if we accept the first principle of induction as valid, then the second
principle of induction is valid, and conversely. In order to prove the equivalence
of the two induction principles, we’ll introduce another principle, which seems so
obvious as to be unarguable.