Liber Abaci

0250124

A sequence is a function whose domain is a countable ordered set.

It can be identified by a recurrence relation or by a closed-form expression. A recurrence (relation) for a sequence is an expression that allows us to calculate a term of the sequence using its previous terms; while the closed-form expression is a direct relation between the index of the term and its value.

Fibonacci Sequence

In the book Liber Abaci, Leonardo Fibonacci presented the following problem:

A pair of rabbits becomes productive after two months of life and, from then on, produces a new pair every month. Starting with a single pair of newborn rabbits, how many pairs will there be at the end of a year?

Let us designate with \(f_n\) the number of pairs of rabbits existing after n months. Evidently, \(f_0 = f_1 = 1\). On the other hand, the number of pairs existing in the n-th month, \(f_n\), is equal to the number existing one month before, \(f_{n-1}\), plus the number of new births. Now, this number is precisely the number of pairs existing two months ago, \(f_{n-2}\), which are at least two months old and therefore able to reproduce. Therefore, each element of the Fibonacci sequence is the sum of the two preceding ones. Since we already know that \(f_0 = f_1 = 1\), we can construct it:

$$ f_0 = 1, $$ $$ f_1 = 1, $$ $$ f_2 = f_0 + f_1 = 2, $$ $$ f_3 = f_1 + f_2 = 3, $$ $$ f_4 = f_2 + f_3 = 5, $$ $$ f_5 = f_3 + f_4 = 8, $$ $$ f_6 = f_4 + f_5 = 13, $$ $$ \ldots $$

and so on infinitely.

The Closed-Form Expression

Let us look for a general term starting from an ansatz. First, we ignore the values of \(f_0\) and \(f_1\) and look for a particular solution of the form \(f_n= x^n\) for the recurrence

$$ f_n = f_{n-1} + f_{n-2} $$

It follows that \(x^n = x^{n-1} + x^{n-2} \) and, dividing both sides by \( x^{n-2} \), we obtain the equation

$$ x^2 = x + 1 $$

which has solutions \(x_1 = \frac{1+\sqrt{5}}{2} \) and \(x_2 = \frac{1-\sqrt{5}}{2}\).

Finally, considering the values of \(f_0\) and \(f_1\), we will look for a solution of the form

$$ \begin{align} f_n & = c_1x_1 ^n + c_2x_2 ^n \\ \\ & = c_1 \left (\frac{1+\sqrt{5}}{2} \right ) ^n + c_2 \left (\frac{1-\sqrt{5}}{2} \right ) ^n \end{align} $$

Replacing n by 0 and 1, respectively, and noting that \( x^0 _1 = x^0 _2 = 1 \), we have:

$$ \begin{cases} c_1 + c_2 = 0 \\ \\ c_1 \left (\dfrac{1+\sqrt{5}}{2} \right ) + c_2 \left (\dfrac{1-\sqrt{5}}{2} \right ) = 1 \end{cases} $$

Therefore, \( c_2 = -c_1 \) and substituting this into the second equation of the system we obtain

$$ \begin{align} c_1 & \left (\frac{1+\sqrt{5}}{2} \right ) - c_2 \left (\frac{1-\sqrt{5}}{2} \right ) = 1 \\ \\ & \Longrightarrow c_1 \left ( \frac{ 1+\sqrt{5} - (1-\sqrt{5})}{2} \right ) = 1 \\ \\ & \Longrightarrow c_1 \left ( \frac{ 2\sqrt{5}}{2} \right ) = 1 \\ \\ & \Longrightarrow c_1 = \frac{1}{\sqrt{5}} \end{align} $$

Finally, we conclude that

$$ f_n = \dfrac{1}{\sqrt{5}} \left ( \left (\frac{1+\sqrt{5}}{2} \right ) ^n - \left (\frac{1-\sqrt{5}}{2} \right ) ^n \right ) $$

It may seem odd, but for every natural number n the result of the expression above is a natural number; precisely, the n-th Fibonacci number.

470.32 kB