Page 403 - Discrete Mathematics and Its Applications

382 5 / Induction and Recursion

The set B of all balanced strings of parentheses is defined 69. Devise a recursive algorithm that counts the number of
recursively by λ ∈ B, where λ is the empty string; (x) ∈ B, times the integer 0 occurs in a list of integers.
xy ∈ B if x, y ∈ B. Exercises 70–77 deal with some unusual sequences, in-
59. Show that (( )( )) is a balanced string of parentheses and formally called self-generating sequences, produced by
(( ))) is not a balanced string of parentheses. simple recurrence relations or rules. In particular, Exer-
cises 70–75 deal with the sequence {a(n)} defined by
60. Find all balanced strings of parentheses with exactly six a(n) = n − a(a(n − 1)) for n ≥ 1 and a(0) = 0. (This se-
symbols.
quence, as well as those in Exercises 74 and 75, are defined
61. Find all balanced strings of parentheses with four or fewer in Douglas Hofstader’s fascinating book Gödel, Escher, Bach
symbols. ([Ho99]).
62. Use induction to show that if x is a balanced string of 70. Find the first 10 terms of the sequence {a(n)} defined in
parentheses, then the number of left parentheses equals the preamble to this exercise.
the number of right parentheses in x. ∗ 71. Prove that this sequence is well defined. That is, show that
Define the function N on the set of strings of parentheses by a(n) is uniquely defined for all nonnegative integers n.
√
∗∗ 72. Prove that a(n) = (n + 1)μ where μ = (−1 + 5)/2.
N(λ) = 0, N(( ) = 1,N()) =−1,
[Hint: First show for all n> 0 that (μn −`μn ) +
N(uv) = N(u) + N(v), (μ n −`μ n ) = 1. Then show for all real numbers α
2
2
where λ is the empty string, and u and v are strings. It can be with 0 ≤ α< 1 and α = 1 − μ that (1 + μ)(1 − α) +
shown that N is well defined. α + μ = 1, considering the cases 0 ≤ α< 1 − μ and
1 − μ<Ð < 1 separately.]
63. Find
∗ 73. Use the formula from Exercise 72 to show that
a) N(( )). b) N( )))( ))(( ).
a(n) = a(n − 1) if μn −`μn < 1 − μ and a(n) =
c) N((( )(( )). d) N( )((( )))(( ))). a(n − 1) + 1 otherwise.
∗∗ 64. Show that a string w of parentheses is balanced if and only 74. Find the first 10 terms of each of the following self-
if N(w) = 0 and N(u) ≥ 0 whenever u is a prefix of w, generating sequences:
that is, w = uv.
a) a(n) = n − a(a(a(n − 1))) for n ≥ 1, a(0) = 0
∗ 65. Give a recursive algorithm for finding all balanced strings b) a(n) = n − a(a(a(a(n − 1)))) for n ≥ 1, a(0) = 0
of parentheses containing n or fewer symbols. c) a(n) = a(n − a(n − 1)) + a(n − a(n − 2)) for n ≥
3, a(1) = 1 and a(2) = 1
66. Give a recursive algorithm for finding gcd(a, b), where
a and b are nonnegative integers not both zero, 75. Find the first 10 terms of both the sequences m(n) and
based on these facts: gcd(a, b) = gcd(b, a) if a> b, f (n) defined by the following pair of interwoven recur-
gcd(0,b) = b, gcd(a, b) = 2 gcd(a/2,b/2) if a and b are rence relations: m(n) = n − f (m(n − 1)), f (n) = n −
even, gcd(a, b) = gcd(a/2,b) if a is even and b is odd, m(f (n − 1)) for n ≥ 1, f(0) = 1 and m(0) = 0.
and gcd(a, b) = gcd(a, b − a). Golomb’s self-generating sequence is the unique nonde-
creasing sequence of positive integers a 1 , a 2 , a 3 , ... that has
67. Verify the program segment
the property that it contains exactly a k occurrences of k for
if x> y then each positive integer k.
x := y
76. Find the first 20 terms of Golomb’s self-generating se-
with respect to the initial assertion T and the final asser- quence.
tion x ≤ y. ∗ 77. Show that if f (n) is the largest integer m such
∗ 68. Develop a rule of inference for verifying recursive pro- that a m = n, where a m is the mth term of Golomb’s
n
a
grams and use it to verify the recursive algorithm for com- self-generating sequence, then f (n) = k = 1 k and
n
puting factorials given as Algorithm 1 in Section 5.4. f (f (n)) = ka k .
k = 1
Computer Projects
Write programs with these input and output.

n
n
∗∗ 1. Givena2 × 2 checkerboard with one square missing, the propositional variables p and q, or an operator from
construct a tiling of this checkerboard using right triomi- {¬, ∨, ∧, →, ↔}.
noes.
4. Given a string, find its reversal.
∗∗ 2. Generate all well-formed formulae for expressions in-
volving the variables x, y, and z and the operators 5. Given a real number a and a nonnegative integer n, find
n
{+, ∗,/, −} with n or fewer symbols. a using recursion.
∗∗ 3. Generate all well-formed formulae for propositions with 6. Given a real number a and a nonnegative integer n, find
n or fewer symbols where each symbol is T, F, one of a 2 n using recursion.