A matrix derivation of Binet's formula
by t0rajir0u, Nov 18, 2007, 12:52 AM
Some of you are probably familiar with the characteristic-equation derivation of the formula
for the Fibonacci sequence, defined here as
(
are the positive and negative roots of 
, respectively, or the "Golden Ratios"). This derivation can either be presented in a simple way ("what geometric series work?") or in a complicated way ("what is the generating function?"). An alternate derivation exists, however, using matrix methods.
Lemma:![$ \left[ \begin{array}{cc} 1 & 1 \\
1 & 0 \end{array} \right] \left[ \begin{array}{c} F_{n + 1} \\
F_n \end{array} \right] = \left[ \begin{array}{c} F_{n + 2} \\
F_{n + 1} \end{array} \right]$](//latex.artofproblemsolving.com/5/a/5/5a5dbcc9d29656d3c0917086dd953106ab1aa405.png)
Proof: Matrix multiplication. This is what I call the "Fibonacci operator," the linear operator
, which describes the behavior of pairs of consecutive Fibonacci numbers.
Corollary:![$ \left[ \begin{array}{cc} 1 & 1 \\
1 & 0 \end{array} \right]^n = \left[ \begin{array}{cc} F_{n + 1} & F_n \\
F_n & F_{n - 1} \end{array} \right]$](//latex.artofproblemsolving.com/2/d/1/2d11552ef4067e1580cc6a09638d482e7e2de49a.png)
Proof: Induct on the columns separately.
The value in this matrix representation of the Fibonacci sequence is that it allows us to quickly and directly prove several identities.
Exercise 1: Prove that
.
Exercise 2: Prove that
.
Exercise 3: Prove that
.
The "Fibonacci operator" matrix
![$ \mathbf{M} = \left[ \begin{array}{cc} 1 & 1 \\
1 & 0 \end{array} \right]$](//latex.artofproblemsolving.com/2/1/8/2183025b6d2605539fbd7f375ff7a5dce1f194c7.png)
has interesting properties in its own right. For starters, its characteristic equation is
Its eigenvalues are
, which seems to have a deep connection to Binet's formula. That connection is justified by the corresponding eigenvectors
![$ \mathbf{v}_1 = \left[ \begin{array}{c} \phi \\
1 \end{array} \right]$](//latex.artofproblemsolving.com/f/2/e/f2ee4654d9aa3ca3bdbaa4f2f048e46937496e51.png)
![$ \mathbf{v}_2 = \left[ \begin{array}{c} \varphi \\
1 \end{array} \right]$](//latex.artofproblemsolving.com/6/2/c/62cea98561aa0e0997fee2b7632481d68b3b4192.png)
These vectors are linearly independent and form a basis of
. We can therefore write, for any vector 
,
![$ \left[ \begin{array}{c} a \\
b \end{array} \right] = x \mathbf{v}_1 + y \mathbf{v}_2$](//latex.artofproblemsolving.com/a/a/4/aa49861f1f00184781731ab084614b2d13d03278.png)
Consider the repeated application of
to an arbitrary vector . We get the vectors 
.... The coefficients of 
are, of course, Fibonacci numbers, and this is represented by the lemmas we proved earlier. However, we can also apply repeatedly to the above linear combination of its eigenvectors, which gives us
![$ \left[ \begin{array}{cc} F_{n + 1} & F_n \\
F_n & F_{n - 1} \end{array} \right] \left[ \begin{array}{c} a \\
b \end{array} \right] = \mathbf{M}^n \left( x \mathbf{v}_1 + y \mathbf{v}_2 \right) = \phi^n x \mathbf{v}_2 + \varphi^n y \mathbf{v}_2$](//latex.artofproblemsolving.com/a/3/3/a33a901f23a1fab0d2e2961e25bf2e9629c6c42c.png)
Solving for
in terms of gives us an alternate proof of Binet's formula by comparing entries. 
Remark: The value in this particular derivation is that the explicit sum of two geometric series comes about naturally as a result of using an eigenvector basis and repeatedly applying a matrix transformation. That form is, in my opinion, somewhat without motivation in the usual derivation of Binet's formula. This approach can be applied to more general recursions in a similar way. In particular, the inspiration for this entry is Hamster1800's post in this thread:
http://www.artofproblemsolving.com/Forum/viewtopic.php?t=174372
I hadn't made the connection between characteristic equations of recursions and characteristic equations of matrices until then. Thanks, Hamster1800!
for the Fibonacci sequence, defined here as
(
are the positive and negative roots of 
, respectively, or the "Golden Ratios"). This derivation can either be presented in a simple way ("what geometric series work?") or in a complicated way ("what is the generating function?"). An alternate derivation exists, however, using matrix methods.Lemma:
![$ \left[ \begin{array}{cc} 1 & 1 \\
1 & 0 \end{array} \right] \left[ \begin{array}{c} F_{n + 1} \\
F_n \end{array} \right] = \left[ \begin{array}{c} F_{n + 2} \\
F_{n + 1} \end{array} \right]$](http://latex.artofproblemsolving.com/5/a/5/5a5dbcc9d29656d3c0917086dd953106ab1aa405.png)
Proof: Matrix multiplication. This is what I call the "Fibonacci operator," the linear operator
, which describes the behavior of pairs of consecutive Fibonacci numbers.Corollary:
![$ \left[ \begin{array}{cc} 1 & 1 \\
1 & 0 \end{array} \right]^n = \left[ \begin{array}{cc} F_{n + 1} & F_n \\
F_n & F_{n - 1} \end{array} \right]$](http://latex.artofproblemsolving.com/2/d/1/2d11552ef4067e1580cc6a09638d482e7e2de49a.png)
Proof: Induct on the columns separately.
The value in this matrix representation of the Fibonacci sequence is that it allows us to quickly and directly prove several identities.
Exercise 1: Prove that
.Exercise 2: Prove that
.Exercise 3: Prove that
.The "Fibonacci operator" matrix
![$ \mathbf{M} = \left[ \begin{array}{cc} 1 & 1 \\
1 & 0 \end{array} \right]$](http://latex.artofproblemsolving.com/2/1/8/2183025b6d2605539fbd7f375ff7a5dce1f194c7.png)
has interesting properties in its own right. For starters, its characteristic equation is
Its eigenvalues are
, which seems to have a deep connection to Binet's formula. That connection is justified by the corresponding eigenvectors![$ \mathbf{v}_1 = \left[ \begin{array}{c} \phi \\
1 \end{array} \right]$](http://latex.artofproblemsolving.com/f/2/e/f2ee4654d9aa3ca3bdbaa4f2f048e46937496e51.png)
![$ \mathbf{v}_2 = \left[ \begin{array}{c} \varphi \\
1 \end{array} \right]$](http://latex.artofproblemsolving.com/6/2/c/62cea98561aa0e0997fee2b7632481d68b3b4192.png)
These vectors are linearly independent and form a basis of
. We can therefore write, for any vector 
,![$ \left[ \begin{array}{c} a \\
b \end{array} \right] = x \mathbf{v}_1 + y \mathbf{v}_2$](http://latex.artofproblemsolving.com/a/a/4/aa49861f1f00184781731ab084614b2d13d03278.png)
Consider the repeated application of
to an arbitrary vector . We get the vectors 
.... The coefficients of 
are, of course, Fibonacci numbers, and this is represented by the lemmas we proved earlier. However, we can also apply repeatedly to the above linear combination of its eigenvectors, which gives us![$ \left[ \begin{array}{cc} F_{n + 1} & F_n \\
F_n & F_{n - 1} \end{array} \right] \left[ \begin{array}{c} a \\
b \end{array} \right] = \mathbf{M}^n \left( x \mathbf{v}_1 + y \mathbf{v}_2 \right) = \phi^n x \mathbf{v}_2 + \varphi^n y \mathbf{v}_2$](http://latex.artofproblemsolving.com/a/3/3/a33a901f23a1fab0d2e2961e25bf2e9629c6c42c.png)
Solving for
in terms of gives us an alternate proof of Binet's formula by comparing entries. Remark: The value in this particular derivation is that the explicit sum of two geometric series comes about naturally as a result of using an eigenvector basis and repeatedly applying a matrix transformation. That form is, in my opinion, somewhat without motivation in the usual derivation of Binet's formula. This approach can be applied to more general recursions in a similar way. In particular, the inspiration for this entry is Hamster1800's post in this thread:
http://www.artofproblemsolving.com/Forum/viewtopic.php?t=174372
I hadn't made the connection between characteristic equations of recursions and characteristic equations of matrices until then. Thanks, Hamster1800!
April 2009
March 2009