Page 401 - Discrete Mathematics and Its Applications

380 5 / Induction and Recursion

30. Use mathematical induction to prove Theorem 1 in Sec- group that can complete a lap by obtaining gas from other
tion 4.2, that is, show if b is an integer, where b> 1, and cars as it travels around the track.
n is a positive integer, then n can be expressed uniquely 41. Show that if n is a positive integer, then
k
in the form n = a k b + a k−1 b k−1 + ··· + a 1 b + a 0 .
⎛ ⎞
n
n
∗ 31. A lattice point in the plane is a point (x, y) where both x
and y are integers. Use mathematical induction to show (2j − 1) ⎝ 1/k ⎠ = n(n + 1)/2.
that at least n + 1 straight lines are needed to ensure j = 1 k = j
that every lattice point (x, y) with x ≥ 0, y ≥ 0, and
x + y ≤ n lies on one of these lines. 42. Use mathematical induction to show that if a, b, and c
are the lengths of the sides of a right triangle, where c is
32. (Requires calculus) Use mathematical induction and the the length of the hypotenuse, then a + b <c for all
n
n
n
product rule to show that if n is a positive integer and integers n with n ≥ 3.
f 1 (x), f 2 (x),...,f n (x), are all differentiable functions,
∗ 43. Use mathematical induction to show that if n is a posi-
then 2 2 2
(f 1 (x)f 2 (x) ··· f n (x)) tive integers, the sequence 2 mod n,2 mod n,2 mod n,
2
f 1 (x)f 2 (x) ··· f n (x) 2 2 2 mod n,... is eventually constant (that is, all terms
f (x) f (x) f (x) after a finite number of terms are all the same).

1
n
2
= + + ··· + . 44. A unit or Egyptian fraction is a fraction of the form
f 1 (x) f 2 (x) f n (x)
1/n, where n is a positive integer. In this exercise, we
33. (Requires material in Section 2.6) Suppose that B = will use strong induction to show that a greedy algorithm
MAM −1 , where A and B are n × n matrices and M is can be used to express every rational number p/q with
k
k
invertible. Show that B = MA M −1 for all positive in- 0 < p/q < 1 as the sum of distinct unit fractions.At each
tegers k. (Consult both the text of Section 2.6 and the step of the algorithm, we find the smallest positive integer
preamble to Exercise 18 of Section 2.6.) n such that 1/n can be added to the sum without exceed-
34. Use mathematical induction to show that if you draw lines ing p/q. For example, to express 5/7 we first start the
in the plane you only need two colors to color the regions sum with 1/2. Because 5/7 − 1/2 = 3/14 we add 1/5to
formed so that no two regions that have an edge in com- the sum because 5 is the smallest positive integer k such
mon have a common color. that 1/k < 3/14. Because 3/14 − 1/5 = 1/70, the algo-
35. Show that n! can be represented as the sum of n of its rithm terminates, showing that 5/7 = 1/2 + 1/5 + 1/70.
distinct positive divisors whenever n ≥ 3. [Hint: Use in- Let T(p) be the statement that this algorithm terminates
ductive loading. First try to prove this result using mathe- for all rational numbers p/q with 0 < p/q < 1. We will
matical induction. By examining where your proof fails, prove that the algorithm always terminates by showing
find a stronger statement that you can easily prove using that T(p) holds for all positive integers p.
mathematical induction.] a) Show that the basis step T(1) holds.
∗
36. Use mathematical induction to prove that if x 1 ,x 2 ,...,x n b) Suppose that T(k) holds for positive integers k with
are positive real numbers with n ≥ 2, then k< p. That is, assume that the algorithm terminates
for all rational numbers k/r, where 1 ≤ k< p. Show
1 1 1
x 1 + x 2 + ··· x n + ≥ that if we start with p/q and the fraction 1/n is se-
x 1 x 2 x n
lected in the first step of the algorithm, then p/q =
1 1 1 1

x 1 + x 2 + ··· x n−1 + x n + p /q + 1/n, where p = np − q and q = nq. After
x 2 x 3 x n x 1
considering the case where p/q = 1/n, use the in-
37. Use mathematical induction to prove that if n people stand ductive hypothesis to show that the greedy algorithm

in a line, where n is a positive integer, and if the first per- terminates when it begins with p /q and complete the
son in the line is a woman and the last person in line is a inductive step.
man, then somewhere in the line there is a woman directly The McCarthy 91 function (defined by John McCarthy, one
in front of a man. of the founders of artificial intelligence) is defined using the
∗ 38. Suppose that for every pair of cities in a country there is a rule

direct one-way road connecting them in one direction or n − 10 if n> 100
M(n) =
the other. Use mathematical induction to show that there M(M(n + 11)) if n ≤ 100
is a city that can be reached from every other city either for all positive integers n.
directly or via exactly one other city.
45. By successively using the defining rule for M(n), find
39. Use mathematical induction to show that when n circles
divide the plane into regions, these regions can be col- a) M(102). b) M(101). c) M(99).
ored with two different colors such that no regions with a d) M(97). e) M(87). f) M(76).
common boundary are colored the same. ∗∗ 46. Show that the function M(n) is a well-defined function
∗ 40. Suppose that among a group of cars on a circular track from the set of positive integers to the set of positive inte-
there is enough fuel for one car to complete a lap. Use gers. [Hint: Prove that M(n) = 91 for all positive integers
mathematical induction to show that there is a car in the n with n ≤ 101.]