126
Proofs, Induction, and Number Theory
59. Prove DeMoivre’s Theorem:
(cos θ + i sin θ)
n
= cos nθ + i sin nθ
for all n ≥ 1. Hint: Recall the addition formulas from trigonometry:
cos(α + β) = cos α cos β − sin α sin β
sin(α + β) = sin α cos β + cos α sin β
60. Prove that
sin θ + sin 3θ + c + sin(2n − 1)θ =
sin
2
nθ
sin θ
for all n ≥ 1 and all θ for which sin θ ∙ 0.
61. Use induction to prove that the product of any three consecutive positive integers is divisible by 3.
62. Suppose that exponentiation is defined by the equation
x
j # x = x
j+1
for any j ≥ 1. Use induction to prove that x
n # x
m
= x
n+m
for n ≥ 1, m ≥ 1.
(Hint: Do induction on m for a fixed, arbitrary value of n.)
63. According to Example 20, it is possible to use angle irons to tile a 4 × 4 checkerboard with the upper right
corner removed.Sketch such a tiling.
64. Example 20 does not cover the case of checkerboards that are not sized by powers of 2. Determine whether
it is possible to tile a 3 × 3 checkerboard.
65. Prove that it is possible to use angle irons to tile a 5 × 5 checkerboard with the upper left corner removed.
66. Find a configuration for a 5 × 5 checkerboard with one square removed that is not possible to tile; explain
why this is not possible.
67. Consider n infinitely long straight lines, none of which are parallel and no three of which have a common
point of intersection. Show that for n ≥ 1, the lines divide the plane into (n
2
+ n + 2)∙2 separate regions.
68. A string of 0s and 1s is to be processed and converted to an even-parity string by adding a parity bit to the
end of the string.(For an explanation of the use of parity bits, see Example 30 in Chapter 9.) The parity
bit is initially 0. When a 0 character is processed, the parity bit remains unchanged. When a 1 character
is processed, the parity bit is switched from 0 to 1 or from 1 to 0. Prove that the number of 1s in the final
string, that is, including the parity bit, is always even. (Hint: Consider various cases.)
69. What is wrong with the following “proof” by mathematical induction? We will prove that for any positive
integer n, n is equal to 1 more than n. Assume that P(k) is true.
k = k + 1
Adding 1 to both sides of this equation, we get
k + 1 = k + 2
Thus,
P(k + 1) is true
70. What is wrong with the following “proof” by mathematical induction?
We will prove that all computers are built by the same manufacturer. In particular, we will prove
that in any collection of n computers where n is a positive integer, all the computers are built by the
same manufacturer. We first prove P(1), a trivial process, because in any collection consisting of
Proofs, Induction, and Number Theory
59. Prove DeMoivre’s Theorem:
(cos θ + i sin θ)
n
= cos nθ + i sin nθ
for all n ≥ 1. Hint: Recall the addition formulas from trigonometry:
cos(α + β) = cos α cos β − sin α sin β
sin(α + β) = sin α cos β + cos α sin β
60. Prove that
sin θ + sin 3θ + c + sin(2n − 1)θ =
sin
2
nθ
sin θ
for all n ≥ 1 and all θ for which sin θ ∙ 0.
61. Use induction to prove that the product of any three consecutive positive integers is divisible by 3.
62. Suppose that exponentiation is defined by the equation
x
j # x = x
j+1
for any j ≥ 1. Use induction to prove that x
n # x
m
= x
n+m
for n ≥ 1, m ≥ 1.
(Hint: Do induction on m for a fixed, arbitrary value of n.)
63. According to Example 20, it is possible to use angle irons to tile a 4 × 4 checkerboard with the upper right
corner removed.Sketch such a tiling.
64. Example 20 does not cover the case of checkerboards that are not sized by powers of 2. Determine whether
it is possible to tile a 3 × 3 checkerboard.
65. Prove that it is possible to use angle irons to tile a 5 × 5 checkerboard with the upper left corner removed.
66. Find a configuration for a 5 × 5 checkerboard with one square removed that is not possible to tile; explain
why this is not possible.
67. Consider n infinitely long straight lines, none of which are parallel and no three of which have a common
point of intersection. Show that for n ≥ 1, the lines divide the plane into (n
2
+ n + 2)∙2 separate regions.
68. A string of 0s and 1s is to be processed and converted to an even-parity string by adding a parity bit to the
end of the string.(For an explanation of the use of parity bits, see Example 30 in Chapter 9.) The parity
bit is initially 0. When a 0 character is processed, the parity bit remains unchanged. When a 1 character
is processed, the parity bit is switched from 0 to 1 or from 1 to 0. Prove that the number of 1s in the final
string, that is, including the parity bit, is always even. (Hint: Consider various cases.)
69. What is wrong with the following “proof” by mathematical induction? We will prove that for any positive
integer n, n is equal to 1 more than n. Assume that P(k) is true.
k = k + 1
Adding 1 to both sides of this equation, we get
k + 1 = k + 2
Thus,
P(k + 1) is true
70. What is wrong with the following “proof” by mathematical induction?
We will prove that all computers are built by the same manufacturer. In particular, we will prove
that in any collection of n computers where n is a positive integer, all the computers are built by the
same manufacturer. We first prove P(1), a trivial process, because in any collection consisting of