Leonard Pisano (i.e. Leonardo of Pisa) (1170 -1240) a.k.a. Fibonacci (i.e.
son of Bonacci)

was the greatest mathematician of the Middle Age. Being unaware of this fact (or
rather

unable to make a living on it), he worked as a merchant and diplomat and
traveled a lot.

During his traves he used to think about various mathematical problems. The
fol lowing

one from his Liber Abaci made him famous

**Rabbit Problem**

Suppose a newly-born pair of rabbits, one male, one female,
are put in a field. Rabbits are

sexually mature after one month so that at the end of its second month a female
can

produce another pair of rabbits. Suppose that our rabbits never die and that the
female

always produces one pair (one male, one female) every month from the second
month on.

How many pairs will there be in one year?

The n^{th} Fibonacci number f _{n} is the number of pairs of rabbits at
the end of the n^{th} month.

Therefore f_{0} = 1, f_{1} = 1, f_{2} = 2, . . .

**1 Exercise**. Find f_{3}, f_{4},
f_{5}, . . . , f_{10}. Show that:

and solve the Rabbit Problem.

Equation ?? is convenient for finding values of f _{n}
only for small n. To find f_{200} for

example, we will need to perform 198 additions , and for f_{1000…}

The goal of this project is to find a direct formula for computing f_{n}
for arbitrary n. A

surprising thing is that in doing this we will be using power series .

Consider the power series

The idea is to try to find an analytic ex pression for the
function F(x) and then to compute

the coefficients at x^{n} in the power series ??.

**2 Exercise.** Compute the ratio f_{n+1}/f_{n}
for the first 10 values of n. What predictions

can you make about the behavior of this ratio as
? What does it tell us about the

interval of convergence of the series ???

**3 Exercise.** Using Equation ?? replace the
coefficient f_{n+2} at x^{n+2} in the series F(x).

Then rearrange the terms to present F(x) as the sum of two series, one related
to xF(x)

and another related to x^{2}F(x).

Using this equation, find a formula for F(x). [Hint: Your
answer should give F(x) as a

rational function (i.e. a ratio of two polynomials ) with a quadratic function in
the

denominator .

**4 Exercise.** Find a power series expansion in terms
of x^{n} for the function F(x) you

obtained in the previous problem. [Hint: You could use a Taylor series if you
knew how to

find all the derivatives of F(x) at x = 0. Since this cannot be done by a
straightforward

computation (try it!), we have to think of a better way. What could be better in
our case

than partial fractions ?]

**5 Exercise.** Write down the coefficient at x^{n}
in the series you produced in the previous

problem. Comparing it with series ?? find a formula for the n^{th}
Fibonacci number f_{n}.

Check your formula against f_{0}, f_{1}, . . . , f_{10}.

If it works, then it must be the formula found by the
French mathematician Binet in 1843.

Is not it a remarkable formula? Put the formula in a prominent place in your
report.

6 Exercise. Using your (and Binet’s) formula ( and a
calculator ) compute accurately

writing down the results of the intermediate calculations. Do you see that one
of the two

terms with n^{th} powers is always very small?

7 Exercise. Using your observations from the previous
step , find a simpler procedure

for computing fn. Use it to find f_{40} and f_{50}. About how
big is f_{100}? f_{1000}?

8 Exercise. Findand the
interval of convergence of the series ??.