Page 381 - Discrete Mathematics and Its Applications

360 5 / Induction and Recursion

∗∗ 53. Prove that A(m, n + 1) > A(m, n) whenever m and n are ⎧ if k = 0
⎪n
nonnegative integers. ⎪ log(log (k−1) n) if log (k−1) n is defined
⎪
⎨
∗ 54. Prove that A(m + 1,n) ≥ A(m, n) whenever m and n are log (k) n =
⎪ and positive
nonnegative integers. ⎪
⎪
undefined otherwise.
⎩
55. Prove that A(i, j) ≥ j whenever i and j are nonnegative
∗
integers. The iterated logarithm is the function log n whose value at n
56. Use mathematical induction to prove that a function F is the smallest nonnegative integer k such that log (k) n ≤ 1.
defined by specifying F(0) and a rule for obtaining 60. Find these values.
F(n + 1) from F(n) is well defined. a) log (2) 16 b) log (3) 256
57. Use strong induction to prove that a function F defined by (3) 65536 (4) 2 65536
c) log 2 d) log 2
specifying F(0) and a rule for obtaining F(n + 1) from
∗
61. Find the value of log n for these values of n.
the values F(k) for k = 0, 1, 2,...,n is well defined.
a) 2 b) 4 c) 8 d) 16
58. Show that each of these proposed recursive definitions of 2048
a function on the set of positive integers does not produce e) 256 f) 65536 g) 2
∗
a well-defined function. 62. Find the largest integer n such that log n = 5. Determine
the number of decimal digits in this number.
a) F(n) = 1 + F( n/2 ) for n ≥ 1 and F(1) = 1.
b) F(n) = 1 + F(n − 3) for n ≥ 2, F(1) = 2, and Exercises 63–65 deal with values of iterated functions. Sup-
F(2) = 3. pose that f (n) is a function from the set of real numbers, or
c) F(n) = 1 + F(n/2) for n ≥ 2, F(1) = 1, and positive real numbers, or some other set of real numbers, to
F(2) = 2. the set of real numbers such that f (n) is monotonically in-
d) F(n) = 1 + F(n/2) if n is even and n ≥ 2, F(n) = creasing [that is, f (n) < f (m) when n<m) and f (n)<n
1 − F(n − 1) if n is odd, and F(1) = 1. for all n in the domain of f .] The function f (k) (n) is defined
e) F(n) = 1 + F(n/2) if n is even and n ≥ 2, F(n) = recursively by
F(3n − 1) if n is odd and n ≥ 3, and F(1) = 1.
n if k = 0
59. Show that each of these proposed recursive definitions of f (k) (n) = (k−1)
a function on the set of positive integers does not produce f(f (n)) if k> 0.
a well-defined function.
Furthermore, let c be a positive real number. The iterated
a) F(n) = 1 + F( (n + 1)/2 ) for n ≥ 1 and ∗
function f is the number of iterations of f required to reduce
c
F(1) = 1. its argument to c or less, so f (n) is the smallest nonnegative
∗
b) F(n) = 1 + F(n − 2) for n ≥ 2 and F(1) = 0. integer k such that f (n) ≤ c. c
k
c) F(n) = 1 + F(n/3) for n ≥ 3,F(1) = 1, F(2) = 2,
63. Let f (n) = n − a, where a is a positive integer. Find a
and F(3) = 3.
∗
formula for f (k) (n). What is the value of f (n) when n
d) F(n) = 1 + F(n/2) if n is even and n ≥ 2, F(n) = 0
1 + F(n − 2) if n is odd, and F(1) = 1. is a positive integer?
e) F(n) = 1 + F(F(n − 1)) if n ≥ 2 and F(1) = 2. 64. Let f (n) = n/2. Find a formula for f (k) (n). What is the
value of f (n) when n is a positive integer?
∗
Exercises 60–62 deal with iterations of the logarithm function. 1
√ (k)
Let log n denote the logarithm of n to the base 2, as usual. The 65. Let f (n) = n. Find a formula for f (n). What is the
function log (k) n is defined recursively by value of f (n) when n is a positive integer?
∗
2
5.4 Recursive Algorithms
Introduction
Sometimes we can reduce the solution to a problem with a particular set of input values to the
solution of the same problem with smaller input values. For instance, the problem of finding
the greatest common divisor of two positive integers a and b, where b> a, can be reduced
to finding the greatest common divisor of a pair of smaller integers, namely, b mod a and
a, because gcd(b mod a, a) = gcd(a, b). When such a reduction can be done, the solution to
Here’s a famous
the original problem can be found with a sequence of reductions, until the problem has been
humorous quote: “To
understand recursion, you reduced to some initial case for which the solution is known. For instance, for finding the greatest
must first understand common divisor, the reduction continues until the smaller of the two numbers is zero, because
recursion.” gcd(a, 0) = a when a> 0.
We will see that algorithms that successively reduce a problem to the same problem with
smaller input are used to solve a wide variety of problems.