Page 374 - Discrete Mathematics and Its Applications

5.3 Recursive Definitions and Structural Induction 353

Basis step

Step 1

Step 2

FIGURE 4 Building Up Full Binary Trees.

DEFINITION 5 The set of full binary trees can be defined recursively by these steps:
BASIS STEP: There is a full binary tree consisting only of a single vertex r.
RECURSIVE STEP: If T 1 and T 2 are disjoint full binary trees, there is a full binary tree,
denoted by T 1 · T 2 , consisting of a root r together with edges connecting the root to each of
the roots of the left subtree T 1 and the right subtree T 2 .

Figure 4 shows how full binary trees are built up by applying the recursive step one and two
times.

Structural Induction

To prove results about recursively defined sets, we generally use some form of mathematical
induction. Example 10 illustrates the connection between recursively defined sets and mathe-
matical induction.
EXAMPLE 10 Show that the set S defined in Example 5 by specifying that 3 ∈ S and that if x ∈ S and y ∈ S,
then x + y ∈ S, is the set of all positive integers that are multiples of 3.

Solution: Let A be the set of all positive integers divisible by 3. To prove that A = S, we must
show that A is a subset of S and that S is a subset of A. To prove that A is a subset of S,we
must show that every positive integer divisible by 3 is in S. We will use mathematical induction
to prove this.
Let P(n) be the statement that 3n belongs to S. The basis step holds because by the first
part of the recursive definition of S,3 · 1 = 3isin S. To establish the inductive step, assume
that P(k) is true, namely, that 3k is in S. Because 3k is in S and because 3 is in S, it follows
from the second part of the recursive definition of S that 3k + 3 = 3(k + 1) is also in S.
To prove that S is a subset of A, we use the recursive definition of S. First, the basis step
of the definition specifies that 3 is in S. Because 3 = 3 · 1, all elements specified to be in S in
this step are divisible by 3 and are therefore in A. To finish the proof, we must show that all
integers in S generated using the second part of the recursive definition are in A. This consists
of showing that x + y is in A whenever x and y are elements of S also assumed to be in A.Now
if x and y are both in A, it follows that 3 | x and 3 | y. By part (i) of Theorem 1 of Section 4.1,
it follows that 3 | x + y, completing the proof. ▲