We use MathJax
Leonardo of Pisa, son of Bonaccio, studied mathematics at the beginning of the thirteenth century. He did much to bring Arabic mathematical notation and methods to the attention of Europe. He is most famous, though, for the sequence that bears his "name", the Fibonacci sequence.
The Fibonacci sequence is typically defined by the recursive formula
\begin{equation*} F_n=F_{n-1}+F_{n-2}, \quad F_1=1, \quad F_2=1 \end{equation*}In words, each term of the Fibonacci sequence is the sum of the previous two terms. The first several terms of the sequence are
\begin{equation*} 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, \ldots \end{equation*}An immediate consequence of the definition is that previous terms may be produced from consecutive later terms as well. In other words, $F_{n-2}=F_n-F_{n-1}$.
Imagine that you are going to breed rabbits. We will suppose that rabbits do not breed until their second month, so we distinguish between newborn rabbits and breeding rabbits. We will also assume that each month every pair of breeding rabbits will produce one newborn pair of rabbits. If you begin with a pair of newborn rabbits, how will the rabbit population grow?
To solve this, consider the table below where we keep track of the newborn and breeding rabbits each month. We begin with zero breeder pairs and one newborn pair, so we have a total of one pair of rabbits, $P_1=1$, the cell with green highlighting in the first column. In other words, the numbers in each column add to the total. Then in the second month, the number of breeders will equal the previous total, since the newborns become breeders in their second month, while the previous breeders still breed. This is illustrated by the green highlighting in the first two months. Also, the number of newborns will equal the previous number of breeders, and this is shown by the blue highlighting in the first two months. We observe that the total in the second month is also one pair of rabbits, $P_2=1$, but this time it is a breeding pair.
| Month | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 |
| Breeding | 0 | 1 | 1 | 2 | 3 | 5 | 8 | 13 | 21 | 34 | 55 |
| Newborn | 1 | 0 | 1 | 1 | 2 | 3 | 5 | 8 | 13 | 21 | 34 |
| Total | 1 | 1 | 2 | 3 | 5 | 8 | 13 | 21 | 34 | 55 | 89 |
If we continue this general pattern, we see that the total in month $n-2$ becomes the number of breeders in month $n-1$, and the number of newborns in month $n$. If we use $n=6$, we see this fact illustrated by the yellow highlighting in months 4, 5, and 6, as well as the blue highlighting in months 5 and 6. But the total number in any month is equal to the number of newborns and the number of breeders, so in month 6 we see that the green cell equals the blue cell plus the yellow cell. But those same colors also appeared in the bottom row of the table, in months 4, 5, and 6, and they imply the equation $P_n=P_{n-1}+P_{n-2}$, which is just the recursive formula for the Fibonacci sequence. In other words, the number of rabbits in month $n$ is the $n$th Fibonacci number.
The Fibonacci sequence can be used to construct a spiral pattern of rectangles whose dimensions converge to the Golden Rectangle. The process is as follows:
At each stage of the process, a new rectangle is produced. At step $n$, the ratio of the sides of the new rectangle is $r_n=\dfrac{F_{n+1}}{F_n}$. This sequence of ratios produces the values
\begin{equation*} \frac11,\frac21,\frac32,\frac53,\frac85,\frac{13}{8},\frac{21}{13},\frac{34}{21},\frac{55}{34},\ldots \end{equation*}Examining decimal approximations of this sequence, we get:
\begin{equation*} 1, 2, 1.5, 1.667, 1.6, 1.625, 1.615, 1.619, 1.618,\ldots \end{equation*}We see that this sequence alternately increases and decreases, but in ever smaller steps. It is converging to a value that is approximately equal to 1.618. To determine the exact value of this result, we consider the ratio
\begin{equation*} r_{n+1}=\dfrac{F_{n+2}}{F_{n+1}}=\dfrac{F_{n+1}+F_n}{F_{n+1}}=1+\dfrac{F_n}{F_{n+1}}=1+\dfrac{1}{r_n} \end{equation*}
As $n$ grows ever larger, the ratios are growing ever closer to one another. In the limit of this process (as $n$ approaches infinity), the values of $r_n$ and $r_{n+1}$ will approach the same value, which we shall simply call $r$. In the limit, the equation becomes . $r=1+\dfrac{1}{r}$. Multiplying both sides by the denominator $r$, we obtain the quadratic equation $r^2-r-1=0$, which can be solved by the quadratic formula. One of the two solutions will be negative, but our rectangles had positive sides, and so we discard the negative solution. Therefore, we obtain the value commonly called the Golden Ratio, $r=\dfrac{1+\sqrt{5}}{2}$. And rectangles having the Golden Ratio as the ratio of their sides are known as Golden Rectangles.
Suppose we define the matrix $M=\pmatrix{ 1 & 1 \\ 1 & 0}$. The first few terms of the sequence of matrices $M^n$ are:
\begin{equation*} \pmatrix{ 1 & 1 \\ 1 & 0}, \pmatrix{ 2 & 1 \\ 1 & 1}, \pmatrix{ 3 & 2 \\ 2 & 1}, \pmatrix{ 5 & 3 \\ 3 & 2}, \pmatrix{ 8 & 5 \\ 5 & 3}, \pmatrix{ 13 & 8 \\ 8 & 5}, \ldots \end{equation*}By observation, it would appear that $M^n=\pmatrix{ F_{n+1} & F_n \\ F_n & F_{n-1}}$, and this result can be proven by induction. The result is certainly true for $n=2$ (and for $n=1$ if we define $F_0=0$). So we assume it is true for $n$, and derive the formula for $n+1$. We get:
\begin{equation*} M^{n+1}=M^n M = \pmatrix{ F_{n+1} & F_n \\ F_n & F_{n-1}} \pmatrix{ 1 & 1 \\ 1 & 0} = \pmatrix{F_{n+1}+F_n & F_{n+1} \\ F_n+F_{n-1} & F_n} = \pmatrix{ F_{n+2} & F_{n+1} \\ F_{n+1} & F_n} \end{equation*}An explicit formula for the $n$th term of the Fibonacci sequence is $F_n=\dfrac{\left(\dfrac{1+\sqrt{5}}{2}\right)^n-\left(\dfrac{1-\sqrt{5}}{2}\right)^n}{\sqrt{5}}$. For a proof of the formula using a geometric series, see A Proof of Binet's Formula.