Page 367 - Discrete Mathematics and Its Applications

346 5 / Induction and Recursion

EXAMPLE 1 Suppose that f is defined recursively by

f(0) = 3,
f(n + 1) = 2f (n) + 3.

Find f(1), f(2), f(3), and f(4).

Solution: From the recursive definition it follows that

f(1) = 2f(0) + 3 = 2 · 3 + 3 = 9,
f(2) = 2f(1) + 3 = 2 · 9 + 3 = 21,
f(3) = 2f(2) + 3 = 2 · 21 + 3 = 45,
f(4) = 2f(3) + 3 = 2 · 45 + 3 = 93.
▲

Recursively defined functions are well defined. That is, for every positive integer, the
value of the function at this integer is determined in an unambiguous way. This means
that given any positive integer, we can use the two parts of the definition to find the value
of the function at that integer, and that we obtain the same value no matter how we ap-
ply the two parts of the definition. This is a consequence of the principle of mathemati-
cal induction. (See Exercise 56.) Additional examples of recursive definitions are given in
Examples 2 and 3.
n
EXAMPLE 2 Give a recursive definition of a , where a is a nonzero real number and n is a nonnegative
integer.

0
0
Solution: The recursive definition contains two parts. First a is specified, namely, a = 1. Then
n
n
the rule for finding a n+1 from a , namely, a n+1 = a · a , for n = 0, 1, 2, 3,..., is given. These
n
two equations uniquely define a for all nonnegative integers n. ▲
EXAMPLE 3 Give a recursive definition of
n

a k .
k = 0

Solution: The first part of the recursive definition is

0

a k = a 0 .
k = 0

The second part is

n+1 n

a k = a k + a n+1 .
k = 0 k = 0 ▲

In some recursive definitions of functions, the values of the function at the first k positive
integers are specified, and a rule is given for determining the value of the function at larger inte-
gers from its values at some or all of the preceding k integers. That recursive definitions defined
in this way produce well-defined functions follows from strong induction (see Exercise 57).