F(n+2)  =  F(n+1) + F(n)       F(1)  =  1        F(2)  =  1

We can express the recurrence relation F(n+2)= F(n+1) + F(n) in terms of the action of a 2×2 matrix.

A matrix is an ordered set of numbers listed rectangular form. If a matrix A has n rows and m columns then we say it's a n x m  matrix. The two-dimensional vector V is an ordered pair of elements, called scalars, of a field : V = (a,b). If U = (a,b) is written as (a,b) then U is  a 1 x 2 matrix which we shall call a row-vector. Similarly, if U = (a,b) is written vertically, then U becomes a  2 x 1 matrix which we shall call a column – vector.

Writing the two successive Fibonacci terms F(n+2) and F(n+1) as a column vector we have

In other words, the matrix

allows us to transition from one pair of Fibonacci numbers to the next.

Plugging in the first pair 0, 1 we have

Plugging in the second pair 1, 1 we have

Observing that   and   are simply the columns of Q, we can put these two calculations together. In other words we can write

Then we have

What about   Q³?

A little mathematical induction shows that the entries in the matrix for the powers of Q are Fibonacci numbers:

for n >= 1.

An identity matrix I is a diagonal matrix with all diagonal element = 1.

What about Q⁰  ?

If the determinant D(A) of a two-by-two matrix A is non-zero, then there exists a matrix
A^-1, such that A^-1A¹ = I. The inverse of the matrix  Q is

The equation

is called the characteristic equation of matrix A, where  λ  is a scalar and X is a vector from the equation  A*X = λ*X . The values of  λ  are the characteristic vectors of matrix A. The characteristic polynomial of A is D(A-λI). The zero vector, Ø, is  a vector whose elements are  each zero; Ø = ( 0, 0 ).

The characteristic equation for the Q matrix is

Observe that this is the same polynomial that appeared in calculation of the limiting ratio between successive Fibonacci numbers.

The roots of this polynomial are the eigenvalues

of the transition matrix Q.

The Cayley-Hamilton Theorem states that a matrix satisfies its own characteristic equation, so that for the Q matrix

We now seek a fancy way to find a power of a matrix.  The answer comes with diagonalization.  We have that if Q is diaogonalizable with

then

We can diagonalize this matrix with 

The n^th Fibonacci number ( Binet’s formula ) can be found by 

If you carefully multiply this out and take the first component of the result, we get

Suppose we prove, recalling that   and   that     
F(1)+F(2)+F(3)+ …. +F(n) = F(n+2) -1.

It is easy to establish by mathematical induction that

If  (Q-I) has an inverse  ( Q – I )^-1 , then multiplying on each side yields

It is easy to verify that Q satifies the matrix equation  Q² = Q + I . Thus

(Q – I ) *Q = I    and   ( Q – I )^-1 = Q .  Therefore

Equating elements in the upper right in the above matrix equation yields

To each n-square matrix A = (a_ij) we assign a specific number called the determinant of A, denoted by Det (A) or |A|.

The determinants of order one and two are defined as follows:

Det (a₁₁) = |a₁₁|= a₁₁

For any two n-square matrices A and B we have

Det (AB) = (Det A)  (Det B).

It follows from this theorem that

Det (Aⁿ) = (Det A)ⁿ.

It follows from this the following property for the determinant of the Q-matrix

Det Qⁿ = (-1)ⁿ,                                                            

Then we get the following identity connecting three neighboring Fibonacci numbers

Since  Q^m+n= Q^m Qⁿ   it follows that

Examining the lower left corner of the matrix product we find that

F(m+n) = F(m-1)*F(n) + F(m)*F(n+1)

Let   , which satisfies  Q² =Q + I. Thus, since  Q⁰ = I ,

Equating elements in the upper right yields

From previous equation

which gives