Fibonacci posed the following problem: Suppose that rabbits live forever and that every month each pair produces a new pair which becomes productive at age 2 months. If we start with one newborn pair, how many pairs of rabbits will we have in the nth month? Show that the answer is fn, where {fn} is the Fibonacci sequence defined in Example 2(c)

From the example 2(c): The Fibonacci sequence {fn} is defined recursively by the conditions
f1 = 1, f2 = 1, fn = fn-1 + fn-2 where n is greater or equal to 3

Each term is the sum of the two preceding terms. The first few terms are {1,1,2,3,5,8,13,21,...}

Proof. Assume that we will have x(n) pairs of rabbits in the nth month. Now we can set up the recurrence relation as follows.

First of all, we know that x(1)=x(2)=1, since in the first month, we have one newborn pair; and in the second month, we still have one pair. x(3)=2, since one pair newborn bears in the first month now can produce a pair new bears. Simialrly, x(4)=3.

For n>3, namely, n>=4, there are x(n-1) bears in the (n-1)th month. Those bears born in the (n-1)-th month can not produce new bears, so only x(n-2) pair bears can produce new bears. So,

x(n)=x(n-1)+x(n-2)

Hence, we get
x(1)=x(2)=1
x(3)=2, x(4)=3
x(n)=x(n-1)+x(n-2) , n>3
which shows that x(n) is exactly the same as fn. We are done.

b) Let an = fn+1/fn and show that an-1 = 1+1/an-2 assuming that {an} is convergent, find its limit.

As an = fn+1/fn, we have
an-1 = fn/fn-1 and an-2 = fn-1/fn-2
So,
1+1/ an-2 =1+ fn-2/fn-1=(fn-1+fn-2)/fn-1

Note that fn=fn-1+fn-2. So,
1+1/ an-2 =1+ fn-2/fn-1=(fn-1+fn-2)/fn-1
=fn/fn-1=an-1

So, we proved that
an-1=1+1/an-2 .......................(*)

Now assuming the limit of an exists, say a. Then we take limit on both sides of (*) , we get

a=1+1/a
So,
a^2-a-1=0

Note that a>0. So, we get

a=[1+sqrt(5)]/2

Note: sqrt(5) is the square root of 5, in other words, [sqrt(5)]^2=5