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
71547287