Section 3.1 Recursive Definitions
159
example 1
The sequence S is defined recursively by
1. S(1) = 2
2. S(n) = 2S(n − 1) for n ≥ 2
By statement 1, S(1), the first object in S, is 2. Then by statement 2, the second object in S is S(2) = 2S(1) = 2(2) = 4. By statement 2 again, S(3) = 2S(2) = 2(4) = 8.
Continuing in this fashion, we can see that S is the sequence
2, 4, 8, 16, 32, …
A rule like that of statement 2 in Example 1, which defines a sequence value
in terms of one or more earlier values, is called a recurrence relation.
■
PRaCtiCe 1 The sequence T is defined recursively as follows:
1. T(1) = 1
2. T(n) = T(n − 1) + 3 for n ≥ 2
Write the first five values in the sequence T.
example 2
The Fibonacci sequence of numbers, introduced in the thirteenth century by an
Italian merchant and mathematician, is defined recursively by
F(1) = 1
F(2) = 1
F(n) = F(n − 2) + F(n − 1) for n > 2
Here the first two values of the sequence are given, and the recurrence relation
defines the nth value for n > 2 in terms of the two preceding values. It’s best to
think of the recurrence relation in its most general form, which says that F at any
value—except 1 and 2—is the sum of F at the two previous values.
The Fibonacci sequence is famous because of its many interesting properties.
Here is a small list (without proofs):
a. Every positive integer can be written uniquely as a sum of 1 or more distinct, nonconsecutive Fibonacci numbers. For example 11 = 3 + 8, where
3 = F(4) and 8 = F(6).
b. gcd(F( p), F(q)) = F(gcd( p, q)). For example, if p = 6 and q = 9, then
F(6) = 8, F(9) = 34, and gcd(8, 34) = 2. Also, gcd(6, 9) = 3 and F(3) = 2.
c. Every two consecutive Fibonacci numbers are relatively prime, that
is, their greatest common divisor equals 1. As a result, the Euclidean
algorithm to find gcd(a, b) does the maximum amount of work when
a and b are two consecutive Fibonacci numbers.
PRaCtiCe 2 Write the first eight values of the Fibonacci sequence.
■
159
example 1
The sequence S is defined recursively by
1. S(1) = 2
2. S(n) = 2S(n − 1) for n ≥ 2
By statement 1, S(1), the first object in S, is 2. Then by statement 2, the second object in S is S(2) = 2S(1) = 2(2) = 4. By statement 2 again, S(3) = 2S(2) = 2(4) = 8.
Continuing in this fashion, we can see that S is the sequence
2, 4, 8, 16, 32, …
A rule like that of statement 2 in Example 1, which defines a sequence value
in terms of one or more earlier values, is called a recurrence relation.
■
PRaCtiCe 1 The sequence T is defined recursively as follows:
1. T(1) = 1
2. T(n) = T(n − 1) + 3 for n ≥ 2
Write the first five values in the sequence T.
example 2
The Fibonacci sequence of numbers, introduced in the thirteenth century by an
Italian merchant and mathematician, is defined recursively by
F(1) = 1
F(2) = 1
F(n) = F(n − 2) + F(n − 1) for n > 2
Here the first two values of the sequence are given, and the recurrence relation
defines the nth value for n > 2 in terms of the two preceding values. It’s best to
think of the recurrence relation in its most general form, which says that F at any
value—except 1 and 2—is the sum of F at the two previous values.
The Fibonacci sequence is famous because of its many interesting properties.
Here is a small list (without proofs):
a. Every positive integer can be written uniquely as a sum of 1 or more distinct, nonconsecutive Fibonacci numbers. For example 11 = 3 + 8, where
3 = F(4) and 8 = F(6).
b. gcd(F( p), F(q)) = F(gcd( p, q)). For example, if p = 6 and q = 9, then
F(6) = 8, F(9) = 34, and gcd(8, 34) = 2. Also, gcd(6, 9) = 3 and F(3) = 2.
c. Every two consecutive Fibonacci numbers are relatively prime, that
is, their greatest common divisor equals 1. As a result, the Euclidean
algorithm to find gcd(a, b) does the maximum amount of work when
a and b are two consecutive Fibonacci numbers.
PRaCtiCe 2 Write the first eight values of the Fibonacci sequence.
■