Determining the $k^{th}$ Fibonacci Number

One of the most famous recurrence relations occuring in all of mathematics is the sequence of numbers satisfying

$$a_{n+2}=a_{n+1}+a_{n},$$

which when $a_0=0$ and $a_1=1$ defines the Fibonacci sequence:

$$0,1,1,2,3,5,8,13,\dots$$

This sequence is a solution to a couting problem posed in 1202 by Leonardo of Pisa. In his book, Liber Abaci, Leonardo (Fibonacci, or son of Bonacci) suggested the following problem:

A newly born pair of rabbits of opposite sexes is placed in an enclosure at the beginning of a year. Beginning with the second month, the female gives birth to a pair of rabbits of opposite sexes each month. Each new pair also gives birth to a pair of rabbits each month starting with their second month. Find the number of pairs of rabbits in the enclosure after one year.

If we define $a_n$ to be the number of rabbits in the enclosure at the beginning of month $n$, with a litttle thought we see that the terms of the sequence $\{a_n\}$ satisfy the Fibonacci recurrence relation.

This sequence appears in a most fantastic variety of applications, perhaps the most familiar being patterns in nature, such as ratios of leaves to turns around a stem or ratios of seed patterns. We pose the problem of determining the $k^{th}$ Fibonacci number. Obviously, one could start with $a_0=0$ and $a_1=1$ and derive each number in the sequence one at a time until the $k^{th}$ number is reached. Our goal will be to find the $k^{th}$ number in the sequence in a single step. We will solve the recurrence relation $a_{n+2}=a_{n+1}+a_{n}$ using techniques from linear algebra.

We start with a standard trick for solving a difference equation that has order $s$. That is we group our initial equation with a system of $s-1$ trivial equations to form a system of $s$ equations. In our case, the difference equation is of order 2 so we add the single trivial equation $a_{n+1}=a_{n+1}$. We now have the following system of difference equations.

$$a_{n+2} = a_{n+1}+a_{n}$$

$$a_{n+1} = a_{n+1}$$

Notice that this system of equations can be transformed into the matrix vector equation, $u_{k+1}=Au_k$, where

$$u_k=\left(\begin{array}{c} a_{k+1}\\ a_k\\ \end{array}\right)\;\;\;\;A=\left(\begin{array}{cc} 1&1\\ 1&0\\ \end{array}\right)$$

Unfortunately, this equation still requires knowledge of the $k^{th}$ term in the sequence to determine the $(k+1)^{st}$ term in the sequence. This is unless you notice that $u_{k}=A^ku_0$. The following computations should convince you of this fact.

$$u_0 = u_0$$

$$u_1 = Au_0$$

$$u_2 = Au_1$$

$$= A(Au_0)$$

$$= A^2u_0$$

$$u_3 = Au_2$$

$$= A(A^2u_0)$$

$$= A^3u_0$$

$$\vdots$$

$$u_k = Au_{k-1}$$

$$= A(A^{k-1}u_0)$$

$$= A^ku_0$$

So computing the $k^{th}$ Fibonnaci number breaks down to computing powers of $A$. Fortunately, the matrix $A$ is diagonalizeable. To see this we compute the eigenvalues of $A$ by solving the characteristic equation.

$$det(A-\lambda I) = det\left(\begin{array}{cc} 1-\lambda&1\\ 1&-\lambda\\ \end{array}\right)$$

$$= -\lambda(1-\lambda)-1$$

$$= \lambda^2-\lambda-1$$

The characteristic polynomial has two roots

$$\lambda_1=\displaystyle \frac{1+\sqrt{5}}{2}\;\;\;\;\;\;\;\; \lambda_2=\dfrac{1-\sqrt{5}}{2}$$

which are the eigenvalues of $A$. Since every $n\times n$ matrix with $n$ distinct eigenvalues is diagonalizeable, we look for a basis for each eigenspace.

For any value of $\lambda$ we would get

$$A-\lambda I=\left(\begin{array}{cc} 1-\lambda&1\\ 1&-\lambda\\ \end{array}\right) \sim \left(\begin{array}{cc} 1&-\lambda\\ 0&\lambda^2-\lambda-1\\ \end{array}\right)$$

But since both $\lambda_1$ and $\lambda_2$ are roots of $\lambda^2-\lambda-1$, this would be

$$A-\lambda I\sim\left(\begin{array}{cc} 1&-\lambda\\ 0&0\\ \end{array}\right).$$

So a basis for the $\lambda_1$-eigenspace is $\left(\begin{array}{c} \lambda_1\\ 1\\ \end{array}\right)$.

And a basis for the $\lambda_2$-eigenspace is $\left(\begin{array}{c} \lambda_2\\ 1\\ \end{array}\right)$.

It follows that

$$\left(\begin{array}{cc} 1&1\\ 1&0\\ \end{array}\right) = \left(\begin{array}{cc} \lambda_1&\lambda_2\\ 1&1\\ \end{array}... ...t)\left(\begin{array}{cc} \lambda_1&\lambda_2\\ 1&1\\ \end{array}\right)^{-1}$$

$$= \left(\begin{array}{cc} \displaystyle \frac{1+\sqrt{5}}{2}&\displ... ...}&\displaystyle \frac{1-\sqrt{5}}{2}\\ \\ [1mm] 1&1\\ \end{array}\right)^{-1}$$

and so when computing $A^k$ we get

$$\left(\begin{array}{cc} 1&1\\ 1&0\\ \end{array}\right)^k=\lef... ...displaystyle \frac{1-\sqrt{5}}{2}\\ \\ [1mm] 1&1\\ \end{array}\right)^{-1}$$

If we define the fixed vector

$$u^*=\left(\begin{array}{cc} \displaystyle \frac{1+\sqrt{5}}{2}&\d... ...\ \end{array}\right)^{-1}\left(\begin{array}{c} 1\\ 0\\ \end{array}\right)$$

we get

$$u^*=\left(\begin{array}{c} 1/(\lambda_1-\lambda_2)\\ -1/(\lambda_1-\lambda_2)\\ \end{array}\right)$$

and the following formula for $u_k$.

$$u_k = \left(\begin{array}{cc} \lambda_1&\lambda_2\\ 1&1\\ \end{array}... ...\\ \\ [1mm] \displaystyle \frac{-1}{\lambda_1-\lambda_2}\\ \end{array}\right)$$

$$= \left(\begin{array}{cc} \displaystyle \frac{1+\sqrt{5}}{2}&\displ... ...}{\sqrt{5}}\\ \\ [1mm] -\displaystyle \frac{1}{\sqrt{5}}\\ \end{array}\right)$$

$$= \left(\begin{array}{cc} \displaystyle \frac{1+\sqrt{5}}{2}&\displ... ...\ [1mm] -\displaystyle \frac{(1-\sqrt{5})^k}{2^k\sqrt{5}}\\ \end{array}\right)$$

Now recall that the $k^{th}$ Fibonacci number is the second entry in the vector $u_k$. It now follows from the product above that the $k^{th}$ Fibonacci number is

$$F_k=\displaystyle \frac{1}{\sqrt{5}}\left[\left(\displaystyle \fr... ...\sqrt{5}}{2}\right)^k- \left(\displaystyle \frac{1-\sqrt{5}}{2}\right)^k\right]$$

What is surprising here is that the $k^{th}$ number in the Fibonacci sequence must be an integer. Fortunately, this formula does produce integer values for each $k$. If we are clever, we can actual simplify the computations in the formula a bit more.

See that $\Big\vert(1-\sqrt{5})^k/(2^k\sqrt{5})\Big\vert<1/2$ for any $k$, and so the $k^{th}$ Fibonacci number must actually be the integer that is closest to $(1+\sqrt{5})^k/(2^k\sqrt{5})$. Furthermore, now there is no need to worry about round-off error in the computer computations.

Lets consider a few examples. The $6^{th}$ Fibonacci number is the closest integer to

$$\displaystyle \frac{1}{\sqrt{5}}\left(\displaystyle \frac{1+\sqrt{5}}{2}\right)^6=8.02492$$

Therefore the $6^{th}$ Fibonacci number must be 8. This is easy to check. How about the $30^{th}$ Fibonacci number? It is the closest integer to

$$\displaystyle \frac{1}{\sqrt{5}}\left(\displaystyle \frac{1+\sqrt{5}}{2}\right)^{30}=832040.0....$$

It follows that the $30^{th}$ Fibonacci number is $83240$. What about the $1000^{th}$ number in the sequence? Again it is the closest integer to

$$\displaystyle \frac{1}{\sqrt{5}}\left(\displaystyle \frac{1+\sqrt{5}}{2}\right)^{1000}$$

To compute this number, my calculator gives as $4.3466557687064\times 10^{208}$. This is a very large number, but we can see all that is required to compute any Fibonacci number in the sequence the ability to compute

$$\displaystyle \frac{1}{\sqrt{5}}\left(\displaystyle \frac{1+\sqrt{5}}{2}\right)^{k}$$

It is worth noting that as $k$ gets large, the terms $(1-\sqrt{5})^k/(2^k\sqrt{5})$ approach zero, and so as $k$ gets very large the ratio $F_{k+1}/F_k$ must approach $(1+\sqrt{5})/2\approx1.618$. This number was known to the greeks as the ``golden mean,'' or the ``golden ratio,'' and appears as a ratio of lengths of the sides of many greek buildings, as a rectangle with this ratio was believed to be the most aesthetically pleasing to the eye. There are entire books dedicated to this subject for anybody interested in further research.

Now that we have solved the problem, lets take a slightly different approach. The Fibonacci recurrence relation is actually a homogeneous linear recurrence relation as it can be arranged as

$$a_n-a_{n-1}-a_{n-2}=0$$

For the moment, lets ignore any initial conditions on $a_0$ and $a_1$ and solve the general recurrence relation.

One method of solving linear homogeneous recurrence relations is to look for a solution of the form $a_n=q^n$ where $q$ is some non-zero number. So $a_n=q^n$ satisfies the recurrence relation if and only if $q$ satisfies the homogeneous equation

$$q^n-q^{n-1}-q^{n-2}=q^{n-2}\left(q^2-q-1\right)=0.$$

Since we have assumed $q\not=0$ we get the following possibilities for $q$:

$$q_1=\displaystyle \frac{1+\sqrt{5}}{2}\;\;\;\;\;\;\;\;q_2=\displaystyle \frac{1-\sqrt{5}}{2}$$

Thus,

$$a_n=\left(\displaystyle \frac{1+\sqrt{5}}{2}\right)^n\;\;$$and$$\;\; a_n=\left(\displaystyle \frac{1-\sqrt{5}}{2}\right)^n$$

are both solutions of the Fibonacci recurrence relation.

What might seem disturbing at first is that neither of these values for $a_n$ produce a sequence that satisfies the familiar Fibonacci sequence. In fact, neither choice for $a_n$ appears to produce an integer for any value of $n$. However, we simply need to notice that the original homogeneous recurrence relation is linear, and so any linear combination of these solutions will also satisfy the Fibonacci recurrence relation. That is,

$$a_n=c_1\left(\displaystyle \frac{1+\sqrt{5}}{2}\right)^n+ c_2\left(\displaystyle \frac{1-\sqrt{5}}{2}\right)^n$$

will satisfy the recurrence relation for any choice of $c_1$ and $c_2$.

We now ask if there are values for $c_1,c_2$ so that we satisfy the initial conditions $a_0=0$ and $a_1=1$. We have the following system of linear equations in $c_1$ and $c_2$:

$$c_1+c_2 =$$ 0

$$c_1\left(\displaystyle \frac{1+\sqrt{5}}{2}\right)+ c_2\left(\displaystyle \frac{1-\sqrt{5}}{2}\right) = 1$$

Row reduction gives us

$$\left(\begin{array}{ccc} 1&1&0\\ \left(\displaystyle \frac{1+\s... ...ft(\begin{array}{ccc} 1&0&1/\sqrt{5}\\ 0&1&-1/\sqrt{5}\\ \end{array}\right)$$

and

$$c_1=\displaystyle \frac{1}{\sqrt{5}}\;\;\;\;\;c_2=\displaystyle \frac{-1}{\sqrt{5}}.$$

It follows that

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

is the $(n+1)^{st}$ number in the Fibonnaci sequence. This is the same result we arrived at earlier.

In fact, we can use this technique to give a formula for any sequence satisfying the Fibonacci recurrence relation and having initial conditions $a_0=a$ and $a_1=b$. This follows since

$$det\left(\begin{array}{cc} 1&1\\ \left(\displaystyle \frac{1+\s... ...displaystyle \frac{1-\sqrt{5}}{2}\right)\\ \end{array}\right)=-\sqrt{5}\not=0$$

Put differently, there is a unique solution set $c_1,c_2$ for any system of equations

$$c_1+c_2 = a$$

$$c_1\left(\displaystyle \frac{1+\sqrt{5}}{2}\right)+ c_2\left(\displaystyle \frac{1-\sqrt{5}}{2}\right) = b$$

For example, the sequence $\{b_n\}$ with terms satisfying the Fibonacci recurrence relation $b_n=b_{n-1}+b_{n-2}$ with initial conditions $b_0=2$ and $b_1=-1$ has the following formula for its terms:

$$b_n=\displaystyle \frac{\sqrt{5}-2}{\sqrt{5}}\left(\displaystyle ... ...le \frac{\sqrt{5}+2}{\sqrt{5}}\left(\displaystyle \frac{1-\sqrt{5}}{2}\right)^n$$

We conclude these notes with a general theorem about solutions to linear homogeneous recurrence relations.

Theorem 1   Let $q$ be a non-zero number. Then $h_n=q^n$ is a solution of the linear homogeneous recurrence relation

$$h_n-a_{1}h_{n-1}-a_{2}h_{n-2}-\cdots-a_{k}h_{n-k} = 0, \;\;(a_k\not=0)$$ (1)

with constant coefficients if and only if $q$ is a root of the polynomial equation

$$x^k-a_1x^{k-1}-a_2x^{k-2}-\cdots-a_k =$$ 0 (2)

If the polynomial equation has $k$ distinct roots $q_1,q_2,\dots,q_k,$ then

$$h_n = c_1q^n_1+c_2q^n_2+\cdots+c_kq^n_k$$ (3)

is the general solution of (1) in the following sense: No matter what initial values for $h_0,h_1,\dots,h_{k-1}$ are given, there are constants $c_1,c_2,\dots,c_{k-1}$ so that (3) is the unique solution which satisfies both the recurrence relation (1) and the initial conditions.

Proof. We have that $h_n=q^n$ is a solution of (1) if and only if

$$q_n-a_{1}q_{n-1}-a_{2}q_{n-2}-\cdots-a_{k}q_{n-k}=0$$

for all $n\ge k$. Since we assume that $q\not=0$ this is equivalent to the equation

$$q^k-a_1q^{k-1}-\cdots-a_k=0$$

We conclude that $h_n=q^n$ is a solution of (1) if and only if $q$ is a root of the polynomial equation (2).

Since $a_k\not=0$, none of the roots of (2) will be zero. So there are exactly $k$, not necessarily distinct, roots $q_1,q_2,\dots,q_k$ to (2).

Suppose that these roots are distinct. Then

$$h_n=q^n_1,\;\;\;h_n=q^n_2,\;\;\;\dots,\;\;\;h_n=q^n_k$$

are all different solutions of (1). Then since (1) is linear and homogeneous,

$$h_n=c_1q^n_1+c_2q^n_2+\cdots c_kq^n_k$$

is also solution to (1) for every set of values $c_1,c_2,\dots,c_k$.

Next suppose that we have the initial conditions

$$h_0=b_0,\;\;h_1=b_1,\;\;\dots,\;\;h_{k-1}=b_{k-1}$$

To choose appropriate constants $c_1,c_2,\dots,c_k$ we solve the following system of linear equations in $c_1,c_2,\dots,c_k$.

$$c_1+c_2+\cdots+c_k = b_0$$

$$c_1q_1+c_2q_2+\cdots+c_kq_k = b_1$$

$$c_1q^2_1+c_2q^2_2+\cdots+c_kq^2_k = b_2$$

$$\vdots$$

$$c_1q^{k-1}_1+c_2q^{k-1}_2+\cdots+c_kq^{k-1}_k = b_{k-1}$$

Since this is a system of $k$ equations in $k$ unknowns, there will be a (unique) solution for all values $b_0,b_1,\dots,b_{k-1}$ if and only if the following matrix is invertible.

$$\left(\begin{array}{cccc} 1&1&\cdots&1\\ q_1&q_2&\cdots&q_k\\ ... ...s&\ddots&\vdots\\ q^{k-1}_1&q^{k-1}_2&\cdots&q^{k-1}_k\\ \end{array}\right)$$

But this matrix is invertible if and only if its determinant is non-zero.

Fortunately, this matrix is an important matrix called a Vandermonde matrix, and it is well known (we shall not prove it here) that the determinant of this matrix is

$$\displaystyle \prod_{1\le i<j\le k}(q_j-q_i)$$

Expanded, this determinant looks like

$$(q_k-q_{k-1})(q_k-q_{k-2})\cdots(q_k-q_1)(q_{k-1}-q_{k-2})(q_{k-1}-q_{k-3}) \cdots(q_{k-1}-q_1)\cdots(q_2-q_1)$$

We have assumed that we have $k$ distinct roots. Therefore, since $q_i\not= q_i$ whenever $i\not=j$, this determinant is non-zero and there is a unique solution set $c_1,c_2,\dots,c_k$ for each set of initial values as claimed. This completes the proof.
$\qedsymbol$

The solutions of homogeneous linear recurrence relations using this technique obviously depends on finding distinct roots of polynomial equations, which can be a difficult problem in its own right. Many times when we can find $k$ non-distinct roots we can employ techniques similar to those used in solving differential equations. However, it should be clear that this technique is not a fail safe. Many recurrence relations must be solved using more sophisticated techinques, such as creating generating functions, that we do not discuss here.