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 be the number of rabbits living on the island after months.

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

(a) Find for .
(b) Find a formula for in terms of the for . (This is called a recurrence relation.)
(c) Use your formula from (b) to find .

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.