Matrix Treatment of the Fibonacci sequence
1. Rabbits do not breed in the first month after being born.
2. In subsequent months each pair of rabbits produces one pair of offspring per month.
3. Assume that none of the rabbits die.
4. There is one pair of newborn rabbits at the start of the first month.
How many rabbits will there be after
\[n\]
months?The number of pairs of rabbits in each month follows the sequence Fibonacci sequence 1, 1, 2, 3, 5, 8,...
The sequence obeys the recurrence relation
\[x_n=x_{n-1}+x_{n-2}\]
.We can represent this recurrence relation in matrix form.
\[(x_n, x_{n-1})=(x_{n-1}, x_{n-2})\left( \begin{array}{cc} 1 & 1 \\ 1 & 0 \end{array} \right)\]
Repeated application of this relation to this vector
\[(x_1,x_0)=(1,1)\]
gives\[(x_n, x_{n-1})=(1, 1) \left( \begin{array}{cc} 1 & 1 \\ 1 & 0 \end{array} \right)^n\]
We can manipulate this to find expressions for
\[x_n, \; x_{n-1}\]
. Find the eigenvalues and eigenvectors of the matrix \[A=\left( \begin{array}{cc} 1 & 1 \\ 1 & 0 \end{array} \right)\]
.\[det(A- \lambda I)=0 \rightarrow det \left( \begin{array}{cc} 1 - \lambda & 1 \\ 1 & - \lambda \end{array} \right) =(1- \lambda)(- \lambda )-1=\lambda^2- \lambda-1=0\]
This equation has solutions
\[\lambda_1 = \frac{1- \sqrt{5}}, \; \lambda_2 = \frac{1+ \sqrt{5}}{2}\]
.These are the eigenvalues.
Now find the eigenvectors. These are the solutions to
\[(v_1,v_2)(A- \lambda I)=(0,0)\]
.\[\lambda_1 = \frac{1- \sqrt{5}}{2}\]
\[(v_1,v_2) \left( \begin{array}{cc} 1 - \lambda_1 & 1 \\ 1 & - \lambda_1 \end{array} \right) =(0,0)\]
.\[(v_1,v_2) \left( \begin{array}{cc} \frac{1+ \sqrt{5}}{2} & 1 \\ 1 & \frac{-1+ \sqrt{5}}{2} \end{array} \right)=(v_1(\frac{1+ \sqrt{5}}{2})+v_2,v_1+v_2(\frac{-1+ \sqrt{5}}{2}) =(0,0)\]
.We can take
\[v_1=\frac{1- \sqrt{5}}{2}, \; v_2= \frac{1+ \sqrt{5}}{2}\]
.}
\[\lambda_2 = \frac{1+ \sqrt{5}}{2}\]
\[(v_1,v_2) \left( \begin{array}{cc} 1 - \lambda_2 & 1 \\ 1 & - \lambda_2 \end{array} \right) =(0,0)\]
.\[(v_1,v_2) \left( \begin{array}{cc} \frac{1- \sqrt{5}}{2} & 1 \\ 1 & \frac{-1- \sqrt{5}}{2} \end{array} \right)=(v_1(\frac{1- \sqrt{5}}{2})+v_2,v_1+v_2(\frac{-1- \sqrt{5}}{2}) =(0,0)\]
.We can take
\[v_1=\frac{1+ \sqrt{5}}{2}, \; v_2= \frac{1- \sqrt{5}}{2}\]
.The matrix of eigenvectors is
\[P=\left( \begin{array}{cc} \frac{1- \sqrt{5}}{2} & \frac{1+ \sqrt{5}}{2} \\ \frac{1+ \sqrt{5}}{2} & \frac{1- \sqrt{5}}{2} \end{array} \right)\]
.The corresponding matrix of eigenvalues is
\[B=\left( \begin{array}{cc} \frac{1- \sqrt{5}}{2} & 0 \\ 0 & \frac{1+ \sqrt{5}}{2} \end{array} \right)\]
.The matrices obey the relationship
\[A=P^{-1}BP\]
\[A^n=(P^{-1}BP)(P^{-1}BP)...(P^{-1}BP)(P^{-1}BP)=P^{-1}B^nP\]
Then
\[\begin{equation} \begin{aligned} (x_n, x_{n-1})A^n (1, 1)P^{-1}BP &= (\frac{\sqrt{5}}{5} (\frac{1+ \sqrt{5}}{2})^{n+1}- \frac{\sqrt{5}}{5} (\frac{1- \sqrt{5}}{2})^{n+1}, \\ & \frac{\sqrt{5}}{5} (\frac{1+ \sqrt{5}}{2})^n- \frac{\sqrt{5}}{5} (\frac{1- \sqrt{5}}{2}))^n)) \end{aligned} \end{equation}\]
