Page 380 - Discrete Mathematics and Its Applications

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 a m,n is defined recursively by a 0,0 = 0 and
b) Use structural induction to prove that ones(st) =
ones(s) + ones(t). a m,n = a m−1,n + 1if n = 0 and m> 0
33. a) Give a recursive definition of the function m(s), which a m,n−1 + 1if n> 0,
equals the smallest digit in a nonempty string of dec- then a m,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 a m,n is defined recursively by a 1,1 = 5 and
min(m(s), m(t)).

The reversal of a string is the string consisting of the symbols a m−1,n + 2if n = 1 and m> 1
a m,n =
of the string in reverse order. The reversal of the string w is a m,n−1 + 2if n> 1,
R
denoted by w .
then a m,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 P m equal the number of different
write a string w of length n + 1as xy, where x is a string partitions of m, and let P m,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.
R
R
R
∗ 36. Use structural induction to prove that (w 1 w 2 ) = w w . a) Show that P m,m = P m .
2 1
i
37. Give a recursive definition of w , where w is a string and b) Show that the following recursive definition for P m,n
i
i is a nonnegative integer. (Here w 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. P m,n = P m,m if m<n
⎪
39. When does a string belong to the set A of bit strings de- ⎪ if m = n> 1
⎪ 1 + P m,m−1
⎪
⎪
fined recursively by ⎩ P m,n−1 + P m−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 ofAckermann’s
∗ 40. Recursively define the set of bit strings that have more function.This function was named afterWilhelmAckermann,
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-
i
l(w ) = i · l(w), where w is a string and i is a nonnegative portantroleinthetheoryofrecursivefunctionsandinthestudy
integer. of the complexity of certain algorithms involving set unions.
i R
R i
∗ 42. Show that (w ) = (w ) whenever w is a string and i is (There are several different variants of this function. All are
calledAckermann’s function and have similar properties even
a nonnegative integer; that is, show that the ith power of
though their values do not always agree.)
the reversal of a string is the reversal of the ith power of
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 = T 1 · T 2 is a) A(1, 0) b) A(0, 1)
the union of the sets of leaves of T 1 and of T 2 . 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 T 1 and the set of internal vertices 50. Show that A(1,n) = 2 whenever n ≥ 1.
n
of T 2 .
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).