120
Proofs, Induction, and Number Theory
Example 21 allowed for either form of inductive proof because we could
either reduce the fence at one end or split it at an arbitrary point. The problem of
Example 19 is similar.
Let P(n) be the statement that a fence with n fence posts has n – 1 sections, and
prove P(n) true for all n ≥ 1.
We’ll start with the first principle of induction. For the basis step, P(1) says that
a fence with only 1 fence post has 0 sections, which is clearly true (Figure 2.4b).
Assume that P(k) is true:
a fence with k fence posts has k – 1 sections
and try to prove P(k + 1):
(?) a fence with k + 1 fence posts has k sections
Given a fence with k + 1 fence posts, how can we relate that to a fence with
k fence posts so that we can make use of the inductive hypothesis? We can chop
off the last post and the last section (Figure 2.4c). The remaining fence has k fence
posts and, by the inductive hypothesis, k – 1 sections. Therefore the original fence
had k sections.
Now we’ll prove the same result using the second principle of induction. The
basis step is the same as before. For the inductive hypothesis, we assume
for all r, 1 ≤ r ≤ k, a fence with r fence posts has r – 1 sections
and try to prove P(k + 1):
(?) a fence with k + 1 fence posts has k sections
For a fence with k + 1 fence posts, split the fence into two parts by removing
one section (Figure 2.4d). The 2 parts of the fence have r 1 and r 2 fence posts, where
1 ≤ r 1 ≤ k, 1 ≤ r 2 ≤ k, and r 1 + r 2 = k + 1. By the inductive hypothesis, the 2
parts have, respectively, r 1 – 1 and r 2 – 1 sections, so the original fence has
(r 1 − 1) + (r 2 − 1) + 1 sections
(The extra 1 is for the one that we removed.) Simple arithmetic then yields
r 1 + r 2 − 1 = (k + 1) − 1 = k sections
This proves that a fence with k + 1 fence posts has k sections, which verifies
P(k + 1) and completes the proof using the second principle of induction.
eXAMPLe 22
We again want to show that any product of factors can be written in this programming language with an even number of parentheses, this time using the second principle of induction. The base case is the same as in Example 19: A single factor has
0 parentheses, an even number. Assume that any product of r factors, 1 ≤ r ≤ k,
can be written with an even number of parentheses. Then consider a product
Proofs, Induction, and Number Theory
Example 21 allowed for either form of inductive proof because we could
either reduce the fence at one end or split it at an arbitrary point. The problem of
Example 19 is similar.
Let P(n) be the statement that a fence with n fence posts has n – 1 sections, and
prove P(n) true for all n ≥ 1.
We’ll start with the first principle of induction. For the basis step, P(1) says that
a fence with only 1 fence post has 0 sections, which is clearly true (Figure 2.4b).
Assume that P(k) is true:
a fence with k fence posts has k – 1 sections
and try to prove P(k + 1):
(?) a fence with k + 1 fence posts has k sections
Given a fence with k + 1 fence posts, how can we relate that to a fence with
k fence posts so that we can make use of the inductive hypothesis? We can chop
off the last post and the last section (Figure 2.4c). The remaining fence has k fence
posts and, by the inductive hypothesis, k – 1 sections. Therefore the original fence
had k sections.
Now we’ll prove the same result using the second principle of induction. The
basis step is the same as before. For the inductive hypothesis, we assume
for all r, 1 ≤ r ≤ k, a fence with r fence posts has r – 1 sections
and try to prove P(k + 1):
(?) a fence with k + 1 fence posts has k sections
For a fence with k + 1 fence posts, split the fence into two parts by removing
one section (Figure 2.4d). The 2 parts of the fence have r 1 and r 2 fence posts, where
1 ≤ r 1 ≤ k, 1 ≤ r 2 ≤ k, and r 1 + r 2 = k + 1. By the inductive hypothesis, the 2
parts have, respectively, r 1 – 1 and r 2 – 1 sections, so the original fence has
(r 1 − 1) + (r 2 − 1) + 1 sections
(The extra 1 is for the one that we removed.) Simple arithmetic then yields
r 1 + r 2 − 1 = (k + 1) − 1 = k sections
This proves that a fence with k + 1 fence posts has k sections, which verifies
P(k + 1) and completes the proof using the second principle of induction.
eXAMPLe 22
We again want to show that any product of factors can be written in this programming language with an even number of parentheses, this time using the second principle of induction. The base case is the same as in Example 19: A single factor has
0 parentheses, an even number. Assume that any product of r factors, 1 ≤ r ≤ k,
can be written with an even number of parentheses. Then consider a product