Page 366 - Discrete Mathematics and Its Applications

5.3 Recursive Definitions and Structural Induction 345

FIGURE 1 A Recursively Defined Picture.

We can use recursion to define sequences, functions, and sets. In Section 2.4, and in most
beginning mathematics courses, the terms of a sequence are specified using an explicit formula.
n
For instance, the sequence of powers of 2 is given by a n = 2 for n = 0, 1, 2,.... Recall from
Section 2.4 that we can also define a sequence recursively by specifying how terms of the
sequence are found from previous terms. The sequence of powers of 2 can also be defined
by giving the first term of the sequence, namely, a 0 = 1, and a rule for finding a term of the
sequence from the previous one, namely, a n+1 = 2a n for n = 0, 1, 2,.... When we define a
sequence recursively by specifying how terms of the sequence are found from previous terms,
we can use induction to prove results about the sequence.
When we define a set recursively, we specify some initial elements in a basis step and
provide a rule for constructing new elements from those we already have in the recur-
sive step. To prove results about recursively defined sets we use a method called structural
induction.

Recursively Defined Functions

We use two steps to define a function with the set of nonnegative integers as its domain:

BASIS STEP: Specify the value of the function at zero.
RECURSIVE STEP: Give a rule for finding its value at an integer from its values at smaller
integers.

Such a definition is called a recursive or inductive definition. Note that a function f (n) from
the set of nonnegative integers to the set of a real numbers is the same as a sequence a 0 ,a 1 ,...
where a i is a real number for every nonnegative integer i. So, defining a real-valued sequence
a 0 ,a 1 ,... using a recurrence relation, as was done in Section 2.4, is the same as defining a
function from the set of nonnegative integers to the set of real numbers.