# 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

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

|Contact| |Front page| |Contents| |Generalizations| |Geometry|

Copyright © 1996-2018 Alexander Bogomolny

63210822 |