Section 2.2 Induction
127
one computer, there is only one manufacturer. Now we assume P(k); that is, in any collection of k
computers, all the computers were built by the same manufacturer. To prove P(k + 1), we consider
any collection of k + 1 computers. Pull one of these k + 1 computers (call it HAL) out of the collection. By our assumption, the remaining k computers all have the same manufacturer. Let HAL
change places with one of these k computers. In the new group of k computers, all have the same
manufacturer. Thus, HAL’s manufacturer is the same one that produced all the other computers, and
all k + 1 computers have the same manufacturer.
71. An obscure tribe has only three words in its language, moon, noon, and soon. New words are composed by
juxtaposing these words in any order, as in soonnoonmoonnoon. Any such juxtaposition is a legal word.
a. Use the first principle of induction (on the number of subwords in the word) to prove that any word in
this language has an even number of o’s.
b. Use the second principle of induction (on the number of subwords in the word) to prove that any word
in this language has an even number of o’s.
72. A simple closed polygon consists of n points in the plane joined in pairs by n line segments; each point is
the endpoint of exactly 2 line segments. Following are two examples.
(a)
(b)
a. Use the first principle of induction to prove that the sum of the interior angles of an n-sided simple
closed polygon is (n − 2)180° for all n ≥ 3.
b. Use the second principle of induction to prove that the sum of the interior angles of an n-sided simple
closed polygon is (n − 2)180° for all n ≥ 3.
73. The Computer Science club is sponsoring a jigsaw puzzle contest. Jigsaw puzzles are assembled by fitting
2 pieces together to form a small block, adding a single piece to a block to form a bigger block, or fitting
2 blocks together. Each of these moves is considered a step in the solution. Use the second principle of
induction to prove that the number of steps required to assemble an n-piece jigsaw puzzle is n − 1.
74. OurWay Pizza makes only two kinds of pizza, pepperoni and vegetarian. Any pizza of either kind comes
with an even number of breadsticks (not necessarily the same even number for both kinds). Any order of 2
or more pizzas must include at least 1 of each kind. When the delivery driver goes to deliver an order, he
or she puts the completed order together by combining 2 suborders—picking up all the pepperoni pizzas
from 1 window and all the vegetarian pizzas from another window. Prove that for a delivery of n pizzas,
n ≥ 1, there are an even number of breadsticks included.
75. Consider propositional wffs that contain only the connectives `, ~ , and S (no negation) and where wffs
must be parenthesized when joined by a logical connective. Count each statement letter, connective, or
parenthesis as one symbol. For example, ((A) ` (B)) ~ ((C) ` (D)) is such a wff, with 19 symbols. Prove
that any such wff has an odd number of symbols.
76. In any group of k people, k ≥ 1, each person is to shake hands with every other person. Find a formula for
the number of handshakes, and prove the formula using induction.
127
one computer, there is only one manufacturer. Now we assume P(k); that is, in any collection of k
computers, all the computers were built by the same manufacturer. To prove P(k + 1), we consider
any collection of k + 1 computers. Pull one of these k + 1 computers (call it HAL) out of the collection. By our assumption, the remaining k computers all have the same manufacturer. Let HAL
change places with one of these k computers. In the new group of k computers, all have the same
manufacturer. Thus, HAL’s manufacturer is the same one that produced all the other computers, and
all k + 1 computers have the same manufacturer.
71. An obscure tribe has only three words in its language, moon, noon, and soon. New words are composed by
juxtaposing these words in any order, as in soonnoonmoonnoon. Any such juxtaposition is a legal word.
a. Use the first principle of induction (on the number of subwords in the word) to prove that any word in
this language has an even number of o’s.
b. Use the second principle of induction (on the number of subwords in the word) to prove that any word
in this language has an even number of o’s.
72. A simple closed polygon consists of n points in the plane joined in pairs by n line segments; each point is
the endpoint of exactly 2 line segments. Following are two examples.
(a)
(b)
a. Use the first principle of induction to prove that the sum of the interior angles of an n-sided simple
closed polygon is (n − 2)180° for all n ≥ 3.
b. Use the second principle of induction to prove that the sum of the interior angles of an n-sided simple
closed polygon is (n − 2)180° for all n ≥ 3.
73. The Computer Science club is sponsoring a jigsaw puzzle contest. Jigsaw puzzles are assembled by fitting
2 pieces together to form a small block, adding a single piece to a block to form a bigger block, or fitting
2 blocks together. Each of these moves is considered a step in the solution. Use the second principle of
induction to prove that the number of steps required to assemble an n-piece jigsaw puzzle is n − 1.
74. OurWay Pizza makes only two kinds of pizza, pepperoni and vegetarian. Any pizza of either kind comes
with an even number of breadsticks (not necessarily the same even number for both kinds). Any order of 2
or more pizzas must include at least 1 of each kind. When the delivery driver goes to deliver an order, he
or she puts the completed order together by combining 2 suborders—picking up all the pepperoni pizzas
from 1 window and all the vegetarian pizzas from another window. Prove that for a delivery of n pizzas,
n ≥ 1, there are an even number of breadsticks included.
75. Consider propositional wffs that contain only the connectives `, ~ , and S (no negation) and where wffs
must be parenthesized when joined by a logical connective. Count each statement letter, connective, or
parenthesis as one symbol. For example, ((A) ` (B)) ~ ((C) ` (D)) is such a wff, with 19 symbols. Prove
that any such wff has an odd number of symbols.
76. In any group of k people, k ≥ 1, each person is to shake hands with every other person. Find a formula for
the number of handshakes, and prove the formula using induction.