Use the recurrence relation and values for F0, F1, F2, ...

Chapter 5, Problem 24E

(choose chapter or problem)

Problem 24E

Use the recurrence relation and values for F0, F1, F2, ... given in Example to compute F13 and F14.

Example

The Fibonacci Numbers

One of the earliest examples of a recursively defined sequence arises in the writings of Leonardo of Pisa, commonly known as Fibonacci, who was the greatest European mathematician of the Middle Ages. In 1202 Fibonacci posed the following problem:

A single pair of rabbits (male and female) is born at the beginning of a year. Assume the following conditions:

1. Rabbit pairs are not fertile during their first month of life but thereafter give birth to one new male/female pair at the end of every month.

2. No rabbits die. How many rabbits will there be at the end of the year?

Solution One way to solve this problem is to plunge right into the middle of it using recursion. Suppose you know how many rabbit pairs there were at the ends of previous months. How many will there be at the end of the current month?

The crucial observation is that the number of rabbit pairs born at the end of month k is the same as the number of pairs alive at the end of month k – 2. Why? Because it is exactly the rabbit pairs that were alive at the end of month k – 2 that were fertile during month k. The rabbits born at the end of month k– 1 were not.

Now the number of rabbit pairs alive at the end of month k equals the ones alive at the end of month k –1 plus the pairs newly born at the end of the month. Thus

For each integer n ≥ 1, let

and let

Then by substitution into equation (5.5.2), for all integers k ≥ 2,

Fk= Fk–1 + Fk–2.

Now F0 = 1, as already noted, and F1 = 1 also, because the first pair of rabbits is not fertile until the second month. Hence the complete specification of the Fibonacci sequence is as follows: For all integers k ≥ 2,

(1) Fk = Fk–1 + Fk−2 recurrence relation

(2) F0 = 1, F1 = 1 initial conditions.

To answer Fibonacci’s question, compute F2, F3, and so forth through F12:

(3) F2 = F1 +F0 = 1 + 1 = 2 by (1) and (2)

(4) F3 = F2 +F1 = 2 + 1 = 3 by (1), (2) and (3)

(5) F4 = F3 +F2 = 3 + 2 = 5 by (1), (3) and (4)

(6) F5 = F4 +F3 = 5 + 3 = 8 by (1), (4) and (5)

(7) F6 = F5 +F4 = 8 + 5 = 13 by (1), (5) and (6)

(8) F7 = F6 +F5 = 13 + 8 = 21 by (1), (6) and (7)

(9) F8 = F7 +F6 = 21 + 13 = 34 by (1), (7) and (8)

(10) F9 = F8 +F7 = 34 + 21 = 55 by (1), (8) and (9)

(11) F10 = F9 +F8 = 55 + 34 = 89 by (1), (9) and (10)

(12) F11 = F10 +F9 = 89 + 55 = 144 by (1), (10) and (11)

(13) F12 = F11 +F10 = 144 + 89= 233 by (1), (11) and (12)

At the end of the twelfth month there are 233 rabbit pairs, or 466 rabbits in all.

Unfortunately, we don't have that question answered yet. But you can get it answered in just 5 hours by Logging in or Becoming a subscriber.

Becoming a subscriber
Or look for another answer

×

Login

Login or Sign up for access to all of our study tools and educational content!

Forgot password?
Register Now

×

Register

Sign up for access to all content on our site!

Or login if you already have an account

×

Reset password

If you have an active account we’ll send you an e-mail for password recovery

Or login if you have your password back