Page 375 - Discrete Mathematics and Its Applications

354 5 / Induction and Recursion

In Example 10 we used mathematical induction over the set of positive integers and a
recursive definition to prove a result about a recursively defined set. However, instead of using
mathematical induction directly to prove results about recursively defined sets, we can use a more
convenient form of induction known as structural induction. A proof by structural induction
consists of two parts. These parts are
BASIS STEP: Show that the result holds for all elements specified in the basis step of the
recursive definition to be in the set.

RECURSIVE STEP: Show that if the statement is true for each of the elements used to construct
new elements in the recursive step of the definition, the result holds for these new elements.

The validity of structural induction follows from the principle of mathematical induction
for the nonnegative integers. To see this, let P (n) state that the claim is true for all elements
of the set that are generated by n or fewer applications of the rules in the recursive step of
a recursive definition. We will have established that the principle of mathematical induction
implies the principle of structural induction if we can show that P (n) is true whenever n is a
positive integer. In the basis step of a proof by structural induction we show that P(0) is true.
That is, we show that the result is true of all elements specified to be in the set in the basis
step of the definition. A consequence of the recursive step is that if we assume P(k) is true,
it follows that P(k + 1) is true. When we have completed a proof using structural induction,
we have shown that P(0) is true and that P(k) implies P(k + 1). By mathematical induction it
follows that P (n) is true for all nonnegative integers n. This also shows that the result is true
for all elements generated by the recursive definition, and shows that structural induction is a
valid proof technique.

EXAMPLES OF PROOFS USING STRUCTURAL INDUCTION Structural induction can
be used to prove that all members of a set constructed recursively have a particular property.
We will illustrate this idea by using structural induction to prove results about well-formed
formulae, strings, and binary trees. For each proof, we have to carry out the appropriate basis
step and the appropriate recursive step. For example, to use structural induction to prove a
result about the set of well-formed formulae defined in Example 8, where we specify that T, F,
and every propositional variable s are well-formed formulae and where we specify that if E
and F are well-formed formulae, then (¬E), (E ∧ F), (E ∨ F), (E → F), and (E ↔ F) are
well-formed formulae, we need to complete this basis step and this recursive step.
BASIS STEP: Show that the result is true for T, F, and s whenever s is a propositional variable.

RECURSIVE STEP: Show that if the result is true for the compound propositions p and q,it
is also true for (¬p), (p ∨ q), (p ∧ q), (p → q), and (p ↔ q).

Example11illustrateshowwecanproveresultsaboutwell-formedformulaeusingstructural
induction.

EXAMPLE 11 Show that every well-formed formula for compound propositions, as defined in Example 8,
contains an equal number of left and right parentheses.

Solution:

BASIS STEP: Each of the formula T, F, and s contains no parentheses, so clearly they contain
an equal number of left and right parentheses.
RECURSIVE STEP: Assume p and q are well-formed formulae each containing an equal
number of left and right parentheses. That is, if l p and l q are the number of left parentheses
in p and q, respectively, and r p and r q are the number of right parentheses in p and q, respec-
tively, then l p = r p and l q = r q . To complete the inductive step, we need to show that each of