Page 376 - Discrete Mathematics and Its Applications

5.3 Recursive Definitions and Structural Induction 355

(¬p), (p ∨ q), (p ∧ q), (p → q), and (p ↔ q) also contains an equal number of left and right
parentheses. The number of left parentheses in the first of these compound propositions equals
l p + 1 and in each of the other compound propositions equals l p + l q + 1. Similarly, the number
of right parentheses in the first of these compound propositions equals r p + 1 and in each of the
other compound propositions equals r p + r q + 1. Because l p = r p and l q = r q , it follows that
each of these compound expressions contains the same number of left and right parentheses.
This completes the proof by structural induction. ▲

∗
SupposethatP(w)isapropositionalfunctionoverthesetofstringsw ∈ .Tousestructural
∗
induction to prove that P(w) holds for all strings w ∈ , we need to complete both a basis step
and a recursive step. These steps are:
BASIS STEP: Show that P (λ) is true.
∗
RECURSIVE STEP: Assume that P(w) is true, where w ∈ . Show that if x ∈ , then P(wx)
must also be true.
Example 12 illustrates how structural induction can be used in proofs about strings.
EXAMPLE 12 Use structural induction to prove that l(xy) = l(x) + l(y), where x and y belong to , the set
∗
of strings over the alphabet .

Solution: We will base our proof on the recursive definition of the set given in Definition 1
∗
and the definition of the length of a string in Example 7, which specifies that l(λ) = 0 and
∗
l(wx) = l(w) + 1 when w ∈ and x ∈ . Let P(y) be the statement that l(xy) = l(x) + l(y)
∗
whenever x belongs to .
BASIS STEP: To complete the basis step, we must show that P (λ) is true. That is, we must
∗
show that l(xλ) = l(x) + l(λ) for all x ∈ . Because l(xλ) = l(x) = l(x) + 0 = l(x) + l(λ)
for every string x, it follows that P (λ) is true.
RECURSIVE STEP: To complete the inductive step, we assume that P(y) is true and
show that this implies that P(ya) is true whenever a ∈ . What we need to show is that
l(xya) = l(x) + l(ya) for every a ∈ .To show this, note that by the recursive definition of l(w)
(given in Example 7), we have l(xya) = l(xy) + 1 and l(ya) = l(y) + 1. And, by the inductive
hypothesis, l(xy) = l(x) + l(y). We conclude that l(xya) = l(x) + l(y) + 1 = l(x) + l(ya). ▲

We can prove results about trees or special classes of trees using structural induction. For
example, to prove a result about full binary trees using structural induction we need to complete
this basis step and this recursive step.
BASIS STEP: Show that the result is true for the tree consisting of a single vertex.

RECURSIVE STEP: Show that if the result is true for the trees T 1 and T 2 , then it is true for
tree T 1 · T 2 consisting of a root r, which has T 1 as its left subtree and T 2 as its right subtree.
Before we provide an example showing how structural induction can be used to prove a
result about full binary trees, we need some definitions. We will recursively define the height
h(T ) and the number of vertices n(T ) of a full binary tree T . We begin by defining the height
of a full binary tree.

DEFINITION 6 We define the height h(T ) of a full binary tree T recursively.

BASIS STEP: The height of the full binary tree T consisting of only a root r is h(T ) = 0.

RECURSIVE STEP: If T 1 and T 2 are full binary trees, then the full binary tree T = T 1 · T 2
has height h(T ) = 1 + max(h(T 1 ), h(T 2 )).