122
Proofs, Induction, and Number Theory
ReMinDeR
Use the second principle
of induction when the
k + 1 case depends on
results farther back than k.
As a general rule, the first principle of mathematical induction applies
when information about “one position back” is enough, that is, when the truth
of P(k) is enough to prove the truth of P(k + 1). The second principle applies
when information about “one position back” isn’t good enough; that is, you
can’t prove that P(k + 1) is true just because you know P(k) is true, but you can
prove P(k + 1) true if you know that P(r) is true for one or more values of r that
are “farther back” than k.
S e c t i o n 2 . 2 review
tecHniQueS
• Use the first principle of induction in proofs.
• Use the second principle of induction in proofs.
MAin iDeAS
• Mathematical induction is a technique to prove
properties of positive integers.
• An inductive proof need not begin with 1.
• Induction can be used to prove statements about
quantities whose values are arbitrary nonnegative
integers.
• The first and second principles of induction each
prove the same conclusion, but one approach may
be easier to use than the other in a given situation.
W
W
For reasons that will be clear momentarily, we’ll also establish two additional
cases, P(9) and P(10), by the equations
9 = 3 + 3 + 3
10 = 5 + 5
Now we assume that P(r) is true, that is, r can be written as a sum of 3s and 5s, for
any r, 8 ≤ r ≤ k, and consider P(k + 1). We may assume that k + 1 is at least 11,
because we have already proved P(r) true for r = 8, 9, and 10. If k + 1 ≥ 11, then
(k + 1) – 3 = k – 2 ≥ 8. Thus k – 2 is a legitimate r value, and by the inductive
hypothesis, P(k – 2) is true. Therefore k – 2 can be written as a sum of 3s and 5s,
and adding an additional 3 gives us k + 1 as a sum of 3s and 5s. This verifies that
P(k + 1) is true and completes the proof.
PrACTiCe 9
a. Why are the additional cases P(9) and P(10) proved separately in Example 24?
b. Why can’t the first principle of induction be used in the proof of Example 24?
■
eXeRciSeS 2.2
1. For all positive integers, let P(n) be the equation
2 + 6 + 10 + c + (4n − 2) = 2n
2
a. Write the equation for the base case P(1) and verify that it is true.
b. Write the inductive hypothesis P(k).
c. Write the equation for P(k + 1).
d. Prove that P(k + 1) is true.
Proofs, Induction, and Number Theory
ReMinDeR
Use the second principle
of induction when the
k + 1 case depends on
results farther back than k.
As a general rule, the first principle of mathematical induction applies
when information about “one position back” is enough, that is, when the truth
of P(k) is enough to prove the truth of P(k + 1). The second principle applies
when information about “one position back” isn’t good enough; that is, you
can’t prove that P(k + 1) is true just because you know P(k) is true, but you can
prove P(k + 1) true if you know that P(r) is true for one or more values of r that
are “farther back” than k.
S e c t i o n 2 . 2 review
tecHniQueS
• Use the first principle of induction in proofs.
• Use the second principle of induction in proofs.
MAin iDeAS
• Mathematical induction is a technique to prove
properties of positive integers.
• An inductive proof need not begin with 1.
• Induction can be used to prove statements about
quantities whose values are arbitrary nonnegative
integers.
• The first and second principles of induction each
prove the same conclusion, but one approach may
be easier to use than the other in a given situation.
W
W
For reasons that will be clear momentarily, we’ll also establish two additional
cases, P(9) and P(10), by the equations
9 = 3 + 3 + 3
10 = 5 + 5
Now we assume that P(r) is true, that is, r can be written as a sum of 3s and 5s, for
any r, 8 ≤ r ≤ k, and consider P(k + 1). We may assume that k + 1 is at least 11,
because we have already proved P(r) true for r = 8, 9, and 10. If k + 1 ≥ 11, then
(k + 1) – 3 = k – 2 ≥ 8. Thus k – 2 is a legitimate r value, and by the inductive
hypothesis, P(k – 2) is true. Therefore k – 2 can be written as a sum of 3s and 5s,
and adding an additional 3 gives us k + 1 as a sum of 3s and 5s. This verifies that
P(k + 1) is true and completes the proof.
PrACTiCe 9
a. Why are the additional cases P(9) and P(10) proved separately in Example 24?
b. Why can’t the first principle of induction be used in the proof of Example 24?
■
eXeRciSeS 2.2
1. For all positive integers, let P(n) be the equation
2 + 6 + 10 + c + (4n − 2) = 2n
2
a. Write the equation for the base case P(1) and verify that it is true.
b. Write the inductive hypothesis P(k).
c. Write the equation for P(k + 1).
d. Prove that P(k + 1) is true.