Fibonacci Identities with Matrices

Since their invention in the mid-1800s by Arthur Cayley and later by Ferdinand Georg Frobenius, matrices became an indispensable tool in various fields of mathematics and engineering disciplines. So in fact indispensable that a copy of a matrix textbook can nowadays be had at Sears (although at amazon.com the same book is a little bit cheaper.)

At this site I used matrices to derive Binet's Formula for the Fibonacci numbers and Cassini's Identity that exhibits one of their properties. Here I would like to give additional examples to the same end, i.e., to demonstrate usefulness of the mathematical tool which is Matrix Algebra.

More specifically, we are going to observe some identities between various powers of matrix

\( A=\left( \begin{array}{cc} 0 & 1 \\ 1 & 1 \end{array} \right) \).

As we have seen, for \(n \ge 1\),

\( A^{n+1}=\left( \begin{array}{cc} F_{n-1} & F_{n} \\ F_{n} & F_{n+1} \end{array} \right) \).

To remind, we defined the Fibonacci sequence as,

\(F_{0}=F_{1}=1, F_{n+1}=F_{n}+F_{n-1}, n \ge 1.\)

Sometimes - if not more often - it is more convenient to work with the "shifted" sequence that starts with a \(0\) term:

\(f_{0}=0, f_{1}=1, f_{n+1}=f_{n}+f_{n-1}, n \ge 1.\)

The relation between the two sequences is simple: \(f_{k+1}=F_{k}\), for \(k\gt 0\). In terms of the sequence \( \{ f_{n}\},\)  the above matrix identity appears as

\( A^{n}=\left( \begin{array}{cc} f_{n-1} & f_{n} \\ f_{n} & f_{n+1} \end{array} \right) \).

Since multiplication of matrices is associative, \(A^{m+n}=A^{m}\times A^{n}\),

\( \left( \begin{array}{cc} f_{m+n-1} & f_{m+n} \\ f_{m+n} & f_{m+n+1} \end{array} \right) = \left( \begin{array}{cc} f_{m-1} & f_{m} \\ f_{m} & f_{m+1} \end{array} \right) \times \left( \begin{array}{cc} f_{n-1} & f_{n} \\ f_{n} & f_{n+1} \end{array} \right) \).

Carrying out the multiplication, we obtain

\( \left( \begin{array}{cc} f_{m+n-1} & f_{m+n} \\ f_{m+n} & f_{m+n+1} \end{array} \right) = \left( \begin{array}{cc} f_{m}f_{n} + f_{m-1}f_{n-1} & f_{m}f_{n+1} + f_{m-1}f_{n} \\ f_{m+1}f_{n} + f_{m}f_{n-1} & f_{m+1}f_{n+1} + f_{m}f_{n} \end{array} \right) \).

Two matrices are equal when so are their corresponding entries, implying that a single matrix identity is equivalent to four identities between the Fibonacci numbers. For a reference sake, I'll emphasize just one:

\( f_{m+n} = f_{m}f_{n+1} + f_{m-1}f_{n}. \)

With this we are going to establish an important property of the Fibonacci numbers, viz.,

Proposition

For \(m,n\ge 1\), \(f_{m}\) divides \(f_{mn}\).

Proof

Let \(m\) be fixed but, otherwise, arbitrary. The proof is by induction in \(n\).

For \(n=1\), the claim is trivial. Assume it holds, for \(n=k\ge 1\). Then

\( f_{m(k+1)}=f_{mk+m}=f_{mk}f_{m+1}+f_{mk-1}f_{m}. \)

Now, \(f_{m}\) obviously divides itself and, by the inductive assumption, also \(f_{mk}\), and, therefore, the sum in the right hand side.

(As a matter of fact, a stronger assertion holds, namely, \(\mbox{gcd}(f_{m},f_{n})=f_{\text{gcd}(m,n)}\). I shall prove that on a separate page.)

References

  1. R. Grimaldi, Fibonacci and Catalan Numbers: an Introduction, Wiley, 2012

Related material
Read more...

  • Matrices Help Relationships
  • Eigenvalues of an incidence matrix
  • Addition of Vectors and Matrices
  • Multiplication of a Vector by a Matrix
  • Multiplication of Matrices
  • Matrix Groups
  • Eigenvectors by Inspection
  • Vandermonde matrix and determinant
  • When the Counting Gets Tough, the Tough Count on Mathematics
  • Merlin's Magic Squares
  • |Contact| |Front page| |Contents| |Generalizations| |Geometry| |Store|

    Copyright © 1996-2017 Alexander Bogomolny

     62034979

    Search by google: