Page 377 - Discrete Mathematics and Its Applications

356 5 / Induction and Recursion

If we let n(T ) denote the number of vertices in a full binary tree, we observe that n(T ) satisfies
the following recursive formula:

BASIS STEP: The number of vertices n(T ) of the full binary tree T consisting of only a root
r is n(T ) = 1.

RECURSIVE STEP: If T 1 and T 2 are full binary trees, then the number of vertices of the full
binary tree T = T 1 · T 2 is n(T ) = 1 + n(T 1 ) + n(T 2 ).
We now show how structural induction can be used to prove a result about full binary trees.

THEOREM 2 If T is a full binary tree T , then n(T ) ≤ 2 h(T )+1 − 1.

Proof: We prove this inequality using structural induction.

BASIS STEP: For the full binary tree consisting of just the root r the result is true because
n(T ) = 1 and h(T ) = 0, so that n(T ) = 1 ≤ 2 0+1 − 1 = 1.

RECURSIVE STEP: For the inductive hypothesis we assume that n(T 1 ) ≤ 2 h(T 1 )+1 − 1 and
n(T 2 ) ≤ 2 h(T 2 )+1 − 1 whenever T 1 and T 2 are full binary trees. By the recursive formulae for
n(T ) and h(T ) we have n(T ) = 1 + n(T 1 ) + n(T 2 ) and h(T ) = 1 + max(h(T 1 ), h(T 2 )).
We find that

n(T ) = 1 + n(T 1 ) + n(T 2 ) by the recursive formula for n(T )
≤ 1 + (2 h(T 1 )+1 − 1) + (2 h(T 2 )+1 − 1) by the inductive hypothesis
≤ 2 · max(2 h(T 1 )+1 , 2 h(T 2 )+1 ) − 1 because the sum of two terms is at most 2
times the larger
y
x
= 2 · 2 max(h(T 1 ),h(T 2 ))+1 − 1 because max(2 , 2 ) = 2 max(x,y)
= 2 · 2 h(T ) − 1 by the recursive definition of h(T )
= 2 h(T )+1 − 1.

This completes the recursive step.

Generalized Induction

We can extend mathematical induction to prove results about other sets that have the well-
ordering property besides the set of integers. Although we will discuss this concept in detail in
Section 9.6, we provide an example here to illustrate the usefulness of such an approach.
As an example, note that we can define an ordering on N × N, the ordered pairs of non-
negative integers, by specifying that (x 1 ,y 1 ) is less than or equal to (x 2 ,y 2 ) if either x 1 <x 2 ,
or x 1 = x 2 and y 1 <y 2 ; this is called the lexicographic ordering. The set N × N with this
ordering has the property that every subset of N × N has a least element (see Exercise 53
in Section 9.6). This implies that we can recursively define the terms a m,n , with m ∈ N and
n ∈ N, and prove results about them using a variant of mathematical induction, as illustrated in
Example 13.