# 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. (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.