Page 378 - Discrete Mathematics and Its Applications

5.3 Recursive Definitions and Structural Induction 357

EXAMPLE 13 Suppose that a m,n is defined recursively for (m, n) ∈ N × N by a 0,0 = 0 and

a m−1,n + 1 if n = 0 and m> 0
a m,n =
a m,n−1 + n if n> 0.
Show that a m,n = m + n(n + 1)/2 for all (m, n) ∈ N × N, that is, for all pairs of nonnegative
integers.

Solution:Wecanprovethata m,n = m + n(n + 1)/2usingageneralizedversionofmathematical
induction. The basis step requires that we show that this formula is valid when (m, n) = (0, 0).
The induction step requires that we show that if the formula holds for all pairs smaller than
(m, n) in the lexicographic ordering of N × N, then it also holds for (m, n).

BASIS STEP: Let (m, n) = (0, 0). Then by the basis case of the recursive definition of a m,n
we have a 0,0 = 0. Furthermore, when m = n = 0, m + n(n + 1)/2 = 0 + (0 · 1)/2 = 0. This
completes the basis step.

INDUCTIVE STEP: Suppose that a m ,n = m + n (n + 1)/2 whenever (m,n ) is less

than (m, n) in the lexicographic ordering of N × N. By the recursive definition, if n = 0,
then a m,n = a m−1,n + 1. Because (m − 1,n) is smaller than (m, n), the inductive hypoth-
esis tells us that a m−1,n = m − 1 + n(n + 1)/2, so that a m,n = m − 1 + n(n + 1)/2 + 1 =
m + n(n + 1)/2, giving us the desired equality. Now suppose that n> 0, so a m,n = a m,n−1 + n.
Because (m, n − 1) is smaller than (m, n), the inductive hypothesis tells us that a m,n−1 =
2
m + (n − 1)n/2, so a m,n = m + (n − 1)n/2 + n = m + (n − n + 2n)/2 = m + n(n + 1)/2.
This finishes the inductive step. ▲
As mentioned, we will justify this proof technique in Section 9.6.
Exercises

1. Find f(1), f(2), f(3), and f(4) if f (n) is defined recur- 5. Determine whether each of these proposed definitions is
sively by f(0) = 1 and for n = 0, 1, 2,... a valid recursive definition of a function f from the set
a) f(n + 1) = f (n) + 2. of nonnegative integers to the set of integers. If f is well
b) f(n + 1) = 3f (n). defined, find a formula for f (n) when n is a nonnegative
c) f(n + 1) = 2 f (n) . integer and prove that your formula is valid.
2
d) f(n + 1) = f (n) + f (n) + 1. a) f(0) = 0, f (n) = 2f(n − 2) for n ≥ 1
2. Find f(1), f(2), f(3), f(4), and f(5) if f (n) is defined b) f(0) = 1, f (n) = f(n − 1) − 1 for n ≥ 1
recursively by f(0) = 3 and for n = 0, 1, 2,... c) f(0) = 2, f(1) = 3, f (n) = f(n − 1) − 1 for
a) f(n + 1) =−2f (n). n ≥ 2
b) f(n + 1) = 3f (n) + 7. d) f(0) = 1, f(1) = 2, f (n) = 2f(n − 2) for n ≥ 2
2
c) f(n + 1) = f (n) − 2f (n) − 2. e) f(0) = 1, f (n) = 3f(n − 1) if n is odd and n ≥ 1
d) f(n + 1) = 3 f (n)/3 . and f (n) = 9f(n − 2) if n is even and n ≥ 2
3. Find f(2), f(3), f(4), and f(5) if f is defined recur- 6. Determine whether each of these proposed definitions is
sively by f(0) =−1, f(1) = 2, and for n = 1, 2,... a valid recursive definition of a function f from the set
a) f(n + 1) = f (n) + 3f(n − 1). of nonnegative integers to the set of integers. If f is well
2
b) f(n + 1) = f (n) f(n − 1). defined, find a formula for f (n) when n is a nonnegative
2
2
c) f(n + 1) = 3f (n) − 4f(n − 1) . integer and prove that your formula is valid.
d) f(n + 1) = f(n − 1)/f (n). a) f(0) = 1, f (n) =−f(n − 1) for n ≥ 1
4. Find f(2), f(3), f(4), and f(5) if f is defined recur- b) f(0) = 1, f(1) = 0, f(2) = 2, f (n) = 2f(n − 3)
sively by f(0) = f(1) = 1 and for n = 1, 2,... for n ≥ 3
c) f(0) = 0, f(1) = 1, f (n) = 2f(n + 1) for n ≥ 2
a) f(n + 1) = f (n) − f(n − 1).
b) f(n + 1) = f (n)f (n − 1). d) f(0) = 0, f(1) = 1, f (n) = 2f(n − 1) for n ≥ 1
3
2
c) f(n + 1) = f (n) + f(n − 1) . e) f(0) = 2, f (n) = f(n − 1) if n is odd and n ≥ 1 and
d) f(n + 1) = f (n)/f (n − 1). f (n) = 2f(n − 2) if n ≥ 2