March 28 exercise from lecture

In the following exercise, you will be defining sequences of numbers recursively. That means that a number in the sequence is defined in terms of the numbers coming before it.

Exercise 1: Complete parts (a), (b), and (c) below for your team.

Team rabbit:
One pair of very young rabbits (one male and one female) is dropped on a deserted island. After they are two months old, they give birth to one new pair of rabbits (one male and one female) per month. Let f_n be the number of rabbits living on the island after n months.

Team bitstring:
Let f_n be the number of bitstrings of length n that do not have two consecutive 0s.

(a) Find f_n for n=0, 1, 2, 3, 4, 5, 6, 7, 8.
(b) Find a formula for f_n in terms of the f_i for i<n. (This is called a recurrence relation.)
(c) Use your formula from (b) to find f_9, f_{10}, f_{11}.

Edit: We saw in class that both teams’ sequences of numbers were equal. This sequence is known as the Fibbonacci sequence. This sequence pops up all over mathematics, not just in the two examples above. You can read more about it here.

This entry was posted in Discussion. Bookmark the permalink.

Leave a Reply

Your email address will not be published. Required fields are marked *