Page 365 - Discrete Mathematics and Its Applications

344 5 / Induction and Recursion

n
∗ 30. Find the flaw with the following “proof” that a = 1 for the set of positive integers of the form as + bt, where s
all nonnegative integers n, whenever a is a nonzero real and t are integers.
number. a) Show that S is nonempty.
0
0
Basis Step: a = 1 is true by the definition of a . b) Use the well-ordering property to show that S has a
smallest element c.
j
Inductive Step: Assume that a = 1 for all nonnegative c) Show that if d is a common divisor of a and b, then d
integers j with j ≤ k. Then note that is a divisor of c.
d) Show that c | a and c | b.[Hint: First, assume that
k
k
a · a 1 · 1
k+1
a = = = 1. c | a. Then a = qc + r, where 0 <r <c. Show that
a k−1 1
r ∈ S, contradicting the choice of c.]
∗ 31. Show that strong induction is a valid method of proof by e) Conclude from (c) and (d) that the greatest common
showing that it follows from the well-ordering property. divisor of a and b exists. Finish the proof by showing
32. Find the flaw with the following “proof” that every that this greatest common divisor is unique.
postage of three cents or more can be formed using just 37. Let a be an integer and d be a positive integer. Show
three-cent and four-cent stamps. that the integers q and r with a = dq + r and 0 ≤ r< d,
which were shown to exist in Example 5, are unique.
Basis Step: We can form postage of three cents with a
single three-cent stamp and we can form postage of four 38. Use mathematical induction to show that a rectangu-
cents using a single four-cent stamp. lar checkerboard with an even number of cells and two
squares missing, one white and one black, can be covered
Inductive Step: Assume that we can form postage by dominoes.
of j cents for all nonnegative integers j with j ≤ k us- ∗∗ 39. Can you use the well-ordering property to prove the state-
ing just three-cent and four-cent stamps. We can then ment: “Every positive integer can be described using no
form postage of k + 1 cents by replacing one three-cent more than fifteen English words”? Assume the words
stamp with a four-cent stamp or by replacing two four- come from a particular dictionary of English. [Hint: Sup-
cent stamps by three three-cent stamps. pose that there are positive integers that cannot be de-
33. Show that we can prove that P(n, k) is true for all pairs scribed using no more than fifteen English words. By
of positive integers n and k if we show well ordering, the smallest positive integer that cannot
be described using no more than fifteen English words
a) P(1, 1) is true and P(n, k) →[P(n + 1,k) ∧
P(n, k + 1)] is true for all positive integers n and k. would then exist.]
b) P(1,k) is true for all positive integers k, and 40. Use the well-ordering principle to show that if x and y
P(n, k) → P(n + 1,k) is true for all positive inte- are real numbers with x< y, then there is a rational
gers n and k. number r with x< r < y.[Hint: Use the Archimedean
c) P(n, 1) is true for all positive integers n, and property, given in Appendix 1, to find a positive
P(n, k) → P(n, k + 1) is true for all positive inte- integer A with A> 1/(y − x). Then show that there is
gers n and k. a rational number r with denominator A between x and
n
34. Prove that j(j + 1)(j + 2) ··· (j + k − 1) = y by looking at the numbers x + j/A, where j is a
j=1
n(n + 1)(n + 2) ··· (n + k)/(k + 1) for all positive inte- positive integer.]
gers k and n.[Hint: Use a technique from Exercise 33.] ∗ 41. Show that the well-ordering property can be proved when
∗ 35. Showthatifa 1 ,a 2 ,...,a n arendistinctrealnumbers,ex- the principle of mathematical induction is taken as an ax-
actly n − 1 multiplications are used to compute the prod- iom.
uct of these n numbers no matter how parentheses are ∗ 42. Show that the principle of mathematical induction and
inserted into their product. [Hint: Use strong induction strong induction are equivalent; that is, each can be shown
and consider the last multiplication.] to be valid from the other.
∗ 36. The well-ordering property can be used to show that there ∗ 43. Show that we can prove the well-ordering property when
is a unique greatest common divisor of two positive in- we take strong induction as an axiom instead of taking
tegers. Let a and b be positive integers, and let S be the well-ordering property as an axiom.

5.3 Recursive Definitions and Structural Induction

Introduction

Sometimes it is difficult to define an object explicitly. However, it may be easy to define this
object in terms of itself. This process is called recursion. For instance, the picture shown in
Figure 1 is produced recursively. First, an original picture is given.Then a process of successively
superimposing centered smaller pictures on top of the previous pictures is carried out.