Since you have come here, I assume you have already known quite a bit of linear algebra.
And as convention used throughout this video, we are going to use f_n to denote the nth
Fibonacci number, which satisfies the recurrence relation and the initial conditions.
First we are going to transform a vector into another vector using a matrix A. Now because
of these two defining relations for Fibonacci numbers, we have A to be the yellow matrix
shown. Give yourself some time to verify that this is the required linear transformation.
Now since we can also do it with lower subscripts, we substitute this back to the original formula,
and so ultimately, we would have this. What we need to do is figure out this bit. Luckily,
this is actually quite a standard procedure. We first figure out the eigenvalues of the
matrix, which helps us find the eigenvectors associated with different eigenvalues. Next
we consider a matrix P that consist of the two different eigenvectors, and then the product
of P inverse, A and P would yield a diagonal matrix. The power of diagonal matrices is
much more manageable. Finally, A^n can be obtained by multiplying the nth power of diagonal
matrix by P to the left and P inverse to the right.
We first figure out the eigenvalues. Starting with the characteristic equation, we solve
for it. We then call the two roots of the equation to be alpha and beta to save space.
The second step now is to find the eigenvectors. We start off with the defining equation for
eigenvectors. Usually, we would write an augmented matrix ready for Gaussian elimination. However,
in this 2 by 2 case, it will be trivial to do the elimination, as this only means covering
up one of the equations. If you don’t believe me, try doing the Gaussian elimination by
multiplying the first row by lambda, then adding the second row. Then simply note the
value of lambda should satisfy this equation, as discussed a minute ago. If we then write
the vector x as shown, then from this equation, we have x_1 to be lambda times x_2. The most
convenient values of x_1 and x_2 to take is that x_2 being 1, and x_1 taking one of the
two values lambda can take. Hence the two eigenvectors associated with the different
eigenvalues are these two vectors.
The third major step is actually to find P inverse. We start with this matrix P, then
we use the formula for the inverse matrix for 2 by 2 matrices, and directly substitute
for it, to get the expression for P inverse. Then we only have the last step to consider.
Recall P and its inverse here. Remember that P inverse times A times P is a diagonal matrix
with the two eigenvalues as entries. Now apply this final formula, and plug in the known
matrices, and now we need to do some matrix multiplication. Recall why we have
to do all these. This is because we can transform the vector with first two Fibonacci numbers
as entries to another vector with consecutive Fibonacci numbers as entries using a power
of a matrix. Unfortunately, the power is n-2, so what we can do is go back with the formula
for power n, and replace all n with n-2. Now, substitute this power of matrix back to the
original relation, and since the first two Fibonacci numbers are both 1, we get this.
By simply comparing the first entry of the vector on both sides, we can finally get an
explicit general term of Fibonacci numbers. To simplify this, we simply group up the terms,
and found out this kinda simplified expression. This can be further simplified though. Notice
that right from the beginning of finding the power of the matrix, alpha and beta denote
the roots of the quadratic characteristic equation, and here the two roots add up to
1. Going back, with the new relation between alpha and beta, we can further simplify to
this, which is the Binet formula.
So here is how we can use linear algebra to derive the Binet formula. If you enjoyed this
video, leave a like and subscribe with notifications on, and don’t forget to check out the previous
video if you haven’t already. Bye!