5.

3 Recursive Definitions and Structural Induction 357

EXAMPLE 13 Suppose that am,n is defined recursively for (m, n) ∈ N × N by a0,0 = 0 and

am−1,n + 1 if n = 0 and m > 0
am,n =
am,n−1 + n if n > 0.

Show that am,n = m + n(n + 1)/2 for all (m, n) ∈ N × N, that is, for all pairs of nonnegative
integers.

Solution: We can prove that am,n = m + n(n + 1)/2 using a generalized version of mathematical
induction. The basis step requires that we show that this formula is valid when (m, n) = (0, 0).
The induction step requires that we show that if the formula holds for all pairs smaller than
(m, n) in the lexicographic ordering of N × N, then it also holds for (m, n).
BASIS STEP: Let (m, n) = (0, 0). Then by the basis case of the recursive definition of am,n
we have a0,0 = 0. Furthermore, when m = n = 0, m + n(n + 1)/2 = 0 + (0 · 1)/2 = 0. This
completes the basis step.
INDUCTIVE STEP: Suppose that am ,n = m + n (n + 1)/2 whenever (m, n ) is less
than (m, n) in the lexicographic ordering of N × N. By the recursive definition, if n = 0,
then am,n = am−1,n + 1. Because (m − 1, n) is smaller than (m, n), the inductive hypoth-
esis tells us that am−1,n = m − 1 + n(n + 1)/2, so that am,n = m − 1 + n(n + 1)/2 + 1 =
m + n(n + 1)/2, giving us the desired equality. Now suppose that n > 0, so am,n = am,n−1 + n.
Because (m, n − 1) is smaller than (m, n), the inductive hypothesis tells us that am,n−1 =
m + (n − 1)n/2, so am,n = m + (n − 1)n/2 + n = m + (n2 − n + 2n)/2 = m + n(n + 1)/2.

▲
This finishes the inductive step.

As mentioned, we will justify this proof technique in Section 9.6.

Exercises

1. Find f (1), f (2), f (3), and f (4) if f (n) is defined recur- 5. Determine whether each of these proposed definitions is
sively by f (0) = 1 and for n = 0, 1, 2, . . . a valid recursive definition of a function f from the set
a) f (n + 1) = f (n) + 2. of nonnegative integers to the set of integers. If f is well
b) f (n + 1) = 3f (n). defined, find a formula for f (n) when n is a nonnegative
c) f (n + 1) = 2f (n) . integer and prove that your formula is valid.
d) f (n + 1) = f (n)2 + f (n) + 1. a) f (0) = 0, f (n) = 2f (n − 2) for n ≥ 1
2. Find f (1), f (2), f (3), f (4), and f (5) if f (n) is defined b) f (0) = 1, f (n) = f (n − 1) − 1 for n ≥ 1
recursively by f (0) = 3 and for n = 0, 1, 2, . . . c) f (0) = 2, f (1) = 3, f (n) = f (n − 1) − 1 for
a) f (n + 1) = −2f (n). n ≥ 2
b) f (n + 1) = 3f (n) + 7. d) f (0) = 1, f (1) = 2, f (n) = 2f (n − 2) for n ≥ 2
c) f (n + 1) = f (n)2 − 2f (n) − 2. e) f (0) = 1, f (n) = 3f (n − 1) if n is odd and n ≥ 1
d) f (n + 1) = 3f (n)/3 . and f (n) = 9f (n − 2) if n is even and n ≥ 2
3. Find f (2), f (3), f (4), and f (5) if f is defined recur- 6. Determine whether each of these proposed definitions is
sively by f (0) = −1, f (1) = 2, and for n = 1, 2, . . . a valid recursive definition of a function f from the set
a) f (n + 1) = f (n) + 3f (n − 1). of nonnegative integers to the set of integers. If f is well
b) f (n + 1) = f (n)2 f (n − 1). defined, find a formula for f (n) when n is a nonnegative
c) f (n + 1) = 3f (n)2 − 4f (n − 1)2 . integer and prove that your formula is valid.
d) f (n + 1) = f (n − 1)/f (n). a) f (0) = 1, f (n) = −f (n − 1) for n ≥ 1
4. Find f (2), f (3), f (4), and f (5) if f is defined recur- b) f (0) = 1, f (1) = 0, f (2) = 2, f (n) = 2f (n − 3)
sively by f (0) = f (1) = 1 and for n = 1, 2, . . . for n ≥ 3
a) f (n + 1) = f (n) − f (n − 1). c) f (0) = 0, f (1) = 1, f (n) = 2f (n + 1) for n ≥ 2
b) f (n + 1) = f (n)f (n − 1). d) f (0) = 0, f (1) = 1, f (n) = 2f (n − 1) for n ≥ 1
c) f (n + 1) = f (n)2 + f (n − 1)3 . e) f (0) = 2, f (n) = f (n − 1) if n is odd and n ≥ 1 and
d) f (n + 1) = f (n)/f (n − 1). f (n) = 2f (n − 2) if n ≥ 2
 358 5 / Induction and Recursion

7. Give a recursive definition of the sequence {an }, n = 23. Give a recursive definition of the set of positive integers
1, 2, 3, . . . if that are multiples of 5.
a) an = 6n. b) an = 2n + 1. 24. Give a recursive definition of
c) an = 10n . d) an = 5. a) the set of odd positive integers.
8. Give a recursive definition of the sequence {an }, n = b) the set of positive integer powers of 3.
1, 2, 3, . . . if c) the set of polynomials with integer coefficients.
a) an = 4n − 2. b) an = 1 + (−1)n . 25. Give a recursive definition of
c) an = n(n + 1). d) an = n2 .
a) the set of even integers.
9. Let F be the function such that F (n) is the sum of the first b) the set of positive integers congruent to 2 modulo 3.
n positive integers. Give a recursive definition of F (n).
c) the set of positive integers not divisible by 5.
10. Give a recursive definition of Sm (n), the sum of the inte-
26. Let S be the subset of the set of ordered pairs of integers
ger m and the nonnegative integer n.
defined recursively by
11. Give a recursive definition of Pm (n), the product of the
integer m and the nonnegative integer n. Basis step: (0, 0) ∈ S.
In Exercises 12–19 fn is the nth Fibonacci number. Recursive step: If (a, b) ∈ S, then (a + 2, b + 3) ∈ S
12. Prove that f 12 + f 22 + · · · + f n2 = fn fn+1 when n is a and (a + 3, b + 2) ∈ S.
positive integer. a) List the elements of S produced by the first five ap-
13. Prove that f1 + f3 + · · · + f2n−1 = f2n when n is a pos- plications of the recursive definition.
itive integer. b) Use strong induction on the number of applications
∗ 14. Show that fn+1 fn−1 − f n2 = (−1)n when n is a positive of the recursive step of the definition to show that
integer. 5 | a + b when (a, b) ∈ S.
∗ 15. Show that f0 f1 + f1 f2 + · · · + f2n−1 f2n = f 2 when n c) Use structural induction to show that 5 | a + b when
2n
is a positive integer. (a, b) ∈ S.
∗ 16. Show that f0 − f1 + f2 − · · · − f2n−1 + f2n = 27. Let S be the subset of the set of ordered pairs of integers
f2n−1 − 1 when n is a positive integer. defined recursively by
17. Determine the number of divisions used by the Euclidean Basis step: (0, 0) ∈ S.
algorithm to find the greatest common divisor of the Fi-
bonacci numbers fn and fn+1 , where n is a nonnegative Recursive step: If (a, b) ∈ S, then (a, b + 1) ∈ S,
integer.Verify your answer using mathematical induction. (a + 1, b + 1) ∈ S, and (a + 2, b + 1) ∈ S.
18. Let a) List the elements of S produced by the first four ap-
 plications of the recursive definition.
1 1
A= . b) Use strong induction on the number of applications of
1 0
the recursive step of the definition to show that a ≤ 2b
Show that whenever (a, b) ∈ S.

fn+1 fn c) Use structural induction to show that a ≤ 2b when-
An = ever (a, b) ∈ S.
fn fn−1
28. Give a recursive definition of each of these sets of ordered
when n is a positive integer.
pairs of positive integers. [Hint: Plot the points in the set
19. By taking determinants of both sides of the equation in in the plane and look for lines containing points in the
Exercise 18, prove the identity given in  Exercise
 14. (Re- set.]
a b 
call that the determinant of the matrix   is ad − bc.) a) S = {(a, b) | a ∈ Z+ , b ∈ Z+ , and a + b is odd}
c d
∗ 20. b) S = {(a, b) | a ∈ Z+ , b ∈ Z+ , and a | b}
Give a recursive definition of the functions max and
c) S = {(a, b) | a ∈ Z+ , b ∈ Z+ , and 3 | a + b}
min so that max(a1 , a2 , . . . , an ) and min(a1 , a2 , . . . , an )
are the maximum and minimum of the n numbers 29. Give a recursive definition of each of these sets of or-
a1 , a2 , . . . , an , respectively. dered pairs of positive integers. Use structural induction
∗ 21. to prove that the recursive definition you found is correct.
Let a1 , a2 , . . . , an , and b1 , b2 , . . . , bn be real numbers.
[Hint: To find a recursive definition, plot the points in the
Use the recursive definitions that you gave in Exercise 20
set in the plane and look for patterns.]
to prove these.
a) S = {(a, b) | a ∈ Z+ , b ∈ Z+ , and a + b is even}
a) max(−a1 , −a2 , . . . , −an ) = − min(a1 , a2 , . . . , an )
b) max(a1 + b1 , a2 + b2 , . . . , an + bn ) b) S = {(a, b) | a ∈ Z+ , b ∈ Z+ , and a or b is odd}
≤ max(a1 , a2 , . . . , an ) + max(b1 , b2 , . . . , bn ) c) S = {(a, b) | a ∈ Z+ , b ∈ Z+ , a + b is odd, and 3 | b}
c) min(a1 + b1 , a2 + b2 , . . . , an + bn ) 30. Prove that in a bit string, the string 01 occurs at most one
≥ min(a1 , a2 , . . . , an ) + min(b1 , b2 , . . . , bn ) more time than the string 10.
22. Show that the set S defined by 1 ∈ S and s + t ∈ S when- 31. Define well-formed formulae of sets, variables represent-
ever s ∈ S and t ∈ S is the set of positive integers. ing sets, and operators from { , ∪, ∩, −}.
 5.3 Recursive Definitions and Structural Induction 359

32. a) Give a recursive definition of the function ones(s), 45. Use generalized induction as was done in Example 13 to
which counts the number of ones in a bit string s. show that if am,n is defined recursively by a0,0 = 0 and
b) Use structural induction to prove that ones(st) = 
a + 1 if n = 0 and m > 0
ones(s) + ones(t). am,n = m−1,n
am,n−1 + 1 if n > 0,
33. a) Give a recursive definition of the function m(s), which
equals the smallest digit in a nonempty string of dec- then am,n = m + n for all (m, n) ∈ N × N.
imal digits. 46. Use generalized induction as was done in Example 13 to
b) Use structural induction to prove that m(st) = show that if am,n is defined recursively by a1,1 = 5 and
min(m(s), m(t)). 
a + 2 if n = 1 and m > 1
The reversal of a string is the string consisting of the symbols am,n = m−1,n
of the string in reverse order. The reversal of the string w is am,n−1 + 2 if n > 1,
denoted by wR . then am,n = 2(m + n) + 1 for all (m, n) ∈ Z+ × Z+ .
34. Find the reversal of the following bit strings. ∗ 47. A partition of a positive integer n is a way to write n
a) 0101 b) 1 1011 c) 1000 1001 0111 as a sum of positive integers where the order of terms in
35. Give a recursive definition of the reversal of a string. the sum does not matter. For instance, 7 = 3 + 2 + 1 + 1
[Hint: First define the reversal of the empty string. Then is a partition of 7. Let Pm equal the number of different
write a string w of length n + 1 as xy, where x is a string partitions of m, and let Pm,n be the number of different
of length n, and express the reversal of w in terms of x R ways to express m as the sum of positive integers not
and y.] exceeding n.
∗ 36. Use structural induction to prove that (w1 w2 )R = wR wR . a) Show that Pm,m = Pm .
2 1
37. Give a recursive definition of wi , where w is a string and b) Show that the following recursive definition for Pm,n
i is a nonnegative integer. (Here wi represents the con- is correct: ⎧
catenation of i copies of the string w.) ⎪
⎪ 1 if m = 1
⎪
⎪
∗ 38. Give a recursive definition of the set of bit strings that are ⎪
⎨1 if n = 1
palindromes. Pm,n = Pm,m if m < n
⎪
⎪
39. When does a string belong to the set A of bit strings de- ⎪1 + Pm,m−1
⎪ if m = n > 1
⎪
⎩
fined recursively by Pm,n−1 + Pm−n,n if m > n > 1.
λ∈A c) Find the number of partitions of 5 and of 6 using this
0x1 ∈ A if x ∈ A, recursive definition.
where λ is the empty string? Consider an inductive definition of a version of Ackermann’s
∗ 40. Recursively define the set of bit strings that have more function. This function was named after Wilhelm Ackermann,
zeros than ones. a German mathematician who was a student of the great math-
41. Use Exercise 37 and mathematical induction to show that ematician David Hilbert. Ackermann’s function plays an im-
l(wi ) = i · l(w), where w is a string and i is a nonnegative portant role in the theory of recursive functions and in the study
integer. of the complexity of certain algorithms involving set unions.
∗ 42. Show that (wR )i = (wi )R whenever w is a string and i is (There are several different variants of this function. All are
a nonnegative integer; that is, show that the ith power of called Ackermann’s function and have similar properties even
the reversal of a string is the reversal of the ith power of though their values do not always agree.)
⎧
the string. ⎪ 2n if m = 0
⎪
⎪
43. Use structural induction to show that n(T ) ≥ 2h(T ) + 1, ⎨0 if m ≥ 1 and n = 0
where T is a full binary tree, n(T ) equals the number of A(m, n) =
⎪2
⎪ if m ≥ 1 and n = 1
vertices of T , and h(T ) is the height of T . ⎪
⎩
A(m − 1, A(m, n − 1)) if m ≥ 1 and n ≥ 2
The set of leaves and the set of internal vertices of a full binary
tree can be defined recursively. Exercises 48–55 involve this version of Ackermann’s func-
Basis step: The root r is a leaf of the full binary tree with tion.
exactly one vertex r. This tree has no internal vertices. 48. Find these values of Ackermann’s function.
Recursive step: The set of leaves of the tree T = T1 · T2 is a) A(1, 0) b) A(0, 1)
the union of the sets of leaves of T1 and of T2 . The inter- c) A(1, 1) d) A(2, 2)
nal vertices of T are the root r of T and the union of the 49. Show that A(m, 2) = 4 whenever m ≥ 1.
set of internal vertices of T1 and the set of internal vertices 50. Show that A(1, n) = 2n whenever n ≥ 1.
of T2 .
51. Find these values of Ackermann’s function.
44. Use structural induction to show that l(T ), the number
of leaves of a full binary tree T , is 1 more than i(T ), the a) A(2, 3) *b) A(3, 3)
number of internal vertices of T . ∗ 52. Find A(3, 4).
 360 5 / Induction and Recursion

⎧
∗∗ 53. Prove that A(m, n + 1) > A(m, n) whenever m and n are ⎪ n if k = 0
⎪
⎪
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 c) log 2(3) 65536 d) log(4) 22
65536

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.
58. Show that each of these proposed recursive definitions of a) 2 b) 4 c) 8 d) 16
a function on the set of positive integers does not produce e) 256 f) 65536 g) 22048
a well-defined function. 62. Find the largest integer n such that log∗ n = 5. Determine
a) F (n) = 1 + F (n/2) for n ≥ 1 and F (1) = 1. the number of decimal digits in this number.
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. 
(k) n if k = 0
59. Show that each of these proposed recursive definitions of f (n) =
a function on the set of positive integers does not produce f (f (k−1) (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 c∗ is the number of iterations of f required to reduce
F (1) = 1. its argument to c or less, so f c∗ (n) is the smallest nonnegative
b) F (n) = 1 + F (n − 2) for n ≥ 2 and F (1) = 0. integer k such that f k (n) ≤ c.
c) F (n) = 1 + F (n/3) for n ≥ 3, F (1) = 1, F (2) = 2,
and F (3) = 3. 63. Let f (n) = n − a, where a is a positive integer. Find a
d) F (n) = 1 + F (n/2) if n is even and n ≥ 2, F (n) = formula for f (k) (n). What is the value of f 0∗ (n) when n
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
Exercises 60–62 deal with iterations of the logarithm function. value of f 1∗ (n) when n is a positive integer?
√
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 (k) (n). What is the
function log(k) n is defined recursively by value of f 2∗ (n) when n is a positive integer?

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
humorous quote: “To the original problem can be found with a sequence of reductions, until the problem has been
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.