October 2017 – jped Maths

Fibonacci Sequence

Leonardo Pisano, or Leonardo Fibonacci, studied rabbit populations in 1202 in the following way.

Rabbit couples (male and female) inhabit an island. Each rabbit couple becomes fertile 2 months after being born and then begets a male-female pair every month thereafter. If the population of the island starts with one couple, how many couples, $f_{n}$ , are there after $n$ months?

To work this out one needs to add the number of rabbit couples alive after $n-1$ months, $f_{n-1}$ (since there are no deaths), with the new-born couples. The number of new-born couples is equal to the number of fertile rabbit couples, which is just the number of rabbit couples alive two months previously, $f_{n-2}$ . Hence,

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

resulting in the numbers,

0, 1, 1, 2, 3, 5, 8, … .

Some quote the first term as 1, but let’s say that $f_{0}=0$ and start from there instead.

Matrices

After teaching matrices as a Further Mathematics topic for many years I had always concentrated on geometric interpretations to illustrate the topic. The topic of diagonalisation, was restricted to symmetric matrices, which produce mutually perpendicular eigen-vectors. The denationalization process could be visualised as a rotation to a new set of axes, a readable transformation (stretch etc.) followed by a rotation back the original basis.

Recently, whilst reading a a text book on Number Theory and Cryptography (Baldoni,Ciliberto,Piacentini Cattaneo) I came across the following example, which should be within the reach of Further Mathematics students.

Fibonacci Sequence by Matrices

The Fibonacci Sequence can be expressed in matrices:

$A=\begin{pmatrix} 0 & 1\\ 1 & 1 \end{pmatrix}$

then,

$A \begin{pmatrix} f_{n-2} \\f_{n-1} \end{pmatrix}= \begin{pmatrix} f_{n-1} \\f_{n-2} +f_{n-1}\end{pmatrix}=\begin{pmatrix} f_{n-1} \\f_{n} \end{pmatrix}$ .

This is a recursive definition. A good questions is: Is there a formula for of $f_{n}$ , which does not involve calculating intermediate values?

Well, each stage of this calculation involves a matrix multiplication by $A$ , thus

$A \begin{pmatrix} f_{n-2} \\f_{n-1} \end{pmatrix}=A^{n} \begin{pmatrix} f_{0} \\f_{1} \end{pmatrix}$

and all that is needed is to calculate $A^{n}$ .

A little bit of matrix multiplication yields the following matrix power series for $A$ :

$A^{1}=\begin{pmatrix} 0 & 1 \\ 1 & 1 \end{pmatrix}$

$A^{2}=\begin{pmatrix} 1 & 1 \\ 1 & 2 \end{pmatrix}$

$A^{3}=\begin{pmatrix} 1 & 2 \\ 2 & 3 \end{pmatrix}$

$A^{4}=\begin{pmatrix} 2 & 3 \\ 3 & 5 \end{pmatrix}$

and so on, where the Fibonacci numbers appear as entries in successive matrices.

Interesting, but finding a formula for the $n^{th}$ Fibonacci number looks to be no closer.

Had the matrix $A$ been a diagonal matrix, things would have been different because if

$B=\begin{pmatrix} a & 0 \\ 0 & b \end{pmatrix}$

then,

$B^{n}=\begin{pmatrix} a^{n} & 0 \\ 0 & b^{n}\end{pmatrix}$ .

However, it is possible to diagonalise the matrix $A$ .

An $n \times n$ matrix can be diagonalised if and only if it has $n$ distinct eigen-values.

Eigen values are given by the characteristic equation,

$\begin{vmatrix} 0-t & 1 \\ 1 & 1-t \end{vmatrix}=0$

that is,

$-t(1-t)-1=0$ or $t^{2}-t-1=0$ .

The solution to this quadratic is the Golden Ratio $\Phi$ ,

$t=\Phi=\dfrac{ 1+ \sqrt{5}}{2}$ and $\dfrac{ 1- \sqrt{5}}{2}$

As it has distinct roots, $A$ can be diagonalised using it’s eigen-vectors,

$\begin{pmatrix} \frac{-1+\sqrt{5}}{2} \\ 1\end{pmatrix}$ and $\begin{pmatrix} \frac{-1-\sqrt{5}}{2} \\ 1\end{pmatrix}$ ,

to get matrix $C$ ,

$C=\begin{pmatrix} \frac{-1-\sqrt{5}}{2} & \frac{-1+\sqrt{5}}{2} \\ 1 & 1 \end{pmatrix}$ ,

in which case,

$C^{-1}AC=D=\begin{pmatrix} \frac{1-\sqrt{5}}{2} & 0 \\ 0 & \frac{1+\sqrt{5}}{2} \end{pmatrix}$

$A=CDC^{-1}$ .

It is now an easy matter to find successive powers of $A$ :

$A^{n}=(CDC^{-1})^{n}=CD^{n}C^{-1}$ .

Hence,

$\begin{pmatrix} f_{n-1} \\f_{n} \end{pmatrix}=A \begin{pmatrix} f_{n-2} \\f_{n-1} \end{pmatrix}=A^{n} \begin{pmatrix} f_{0} \\f_{1} \end{pmatrix}= CD^{n}C^{-1}\begin{pmatrix} f_{0} \\f_{1} \end{pmatrix}$

where,

$\begin{pmatrix} f_{n-1} \\f_{n} \end{pmatrix}=A^{n} \begin{pmatrix} f_{0} \\f_{1} \end{pmatrix}=\begin{pmatrix} \frac{-1-\sqrt{5}}{2} & \frac{-1+\sqrt{5}}{2} \\ 1 & 1 \end{pmatrix} \begin{pmatrix} \left(\frac{1-\sqrt{5}}{2}\right)^{n} & 0 \\ 0 & \left(\frac{1+\sqrt{5}}{2}\right)^{n} \end{pmatrix}\begin{pmatrix} -\frac{1}{\sqrt{5}} & \frac{5-\sqrt{5}}{10}\\\frac{1}{\sqrt{5}} & \frac{5+\sqrt{5}}{10}\end{pmatrix}\begin{pmatrix} f_{0} \\f_{1} \end{pmatrix}$

thus,

$\begin{pmatrix} f_{n-1} \\f_{n} \end{pmatrix}=\begin{pmatrix} \frac{1}{\sqrt{5}} \left[ \left( \frac{1+\sqrt{5}}{2} \right) ^{n-1}- \left( \frac{1-\sqrt{5}}{2} \right) ^{n-1}\right] \\ \frac{1}{\sqrt{5}} \left[ \left( \frac{1+\sqrt{5}}{2} \right) ^{n}- \left( \frac{1-\sqrt{5}}{2} \right) ^{n}\right]\end{pmatrix}$ ,

and hence the formula for the $n^{th}$ Fibonacci number is,

$f_{n}=\frac{1}{\sqrt{5}} \left[ \left( \frac{1+\sqrt{5}}{2} \right) ^{n}- \left( \frac{1-\sqrt{5}}{2} \right) ^{n}\right]$ .

Matrices and Wolfram Alpha

Tricky calculations are need to verify the above by hand. Help is at hand from the Wolfram Alpha website. Other computational engines and environments exist but this is free and readily available.

Encoding matrix $A$ as [[0,1],[1,1]] etc. a long string of characters can be prepared separately and then pasted into the command line as follows.

Month: October 2017

Rabbits, Matrices and the Golden Section – nth term of the Fibonacci Sequence by diagonalising a matrix

Fibonacci Sequence

Matrices

Fibonacci Sequence by Matrices

Matrices and Wolfram Alpha