(FYI, I was taught this in a uni class – don’t think I came up with it, I didn’t.)
So we want to show that Fn=(φn-ψn)/√ 5 , where φ=(1+√ 5)/2, and ψ=(1-√ 5)/2. How do we start? We use matrices. Essentially, this “proof” rests on the fact that you can go from one Fibonacci number to another by multiplying it by a certain matrix. We start with the rule we used to define the sequence,
Fn=Fn-1+Fn-2, for n≥2
So we set our numbers up in matrix form:
Essentially, we want to find a way to multiply a pair of consecutive Fibonacci numbers by a matrix to get the next pair (well, the overlapping next pair.) If you think about the rules of matrix multiplication, it’s pretty obvious why the mystery matrix has to be a 2×2 – it has to have the same number of rows as the answer, and the same number of columns as the other matrix has rows. Now, we know that Fn=Fn-1+Fn-2, and that Fn-1=Fn-1, which we can use to define our mystery matrix. As we want the top row to have 1xFn-1, and 1xFn-2, we know that “w” and “x” must be 1’s. Similarly, as we want Fn-1 to only have the value Fn-1, “y” is 1 and “z” is 0. (You can multiply all these out to check this!)
So we now have a formula for one pair of Fibonacci numbers in terms of the previous pair, and multiplied by a matrix. However, we can extend this idea further – the pair (Fn-1,Fn-2) can further be turned into the previous pair multiplied by our matrix, and so on, all the way down to the first pair, (1,0).
We can represent the matrix being multiplied over and over again by raising it to a power (the power is n-1, not n, because of the first pair being different, which you can check if you like!)
So, how do we turn this into a single formula? Is there a neat way to raise a matrix to some power that lets us do this? As it turns out, there is – the process is called “Diagonalisation”, and essentially involves turning a matrix into a diagonal matrix (one where the only entries are along the main diagonal). Why would you want to do this? Well, multiplying a matrix by itself is difficult, in general – but multiplying a diagonal matrix by itself is very easy! If you raise some diagonal matrix D to the power of n, you simply raise each term along the diagonal to the power of n.
The process of diagonalisation is a bit involved, so I might put that in a separate post. For now, however, here is the main result we need.
An = TDnT -1
Where A is the matrix you want to raise to some power n, T is a matrix created through diagonalisation, D is the diagonal matrix, and T -1 is the inverse of T. Essentially, we’re breaking A into 3 parts, one of which is diagonal, so that the chunk that’s multiplied out is the diagonal part, which is easy to raise to a power. For our matrix, this form looks something like this:
Even though it looks more complicated, it actually makes things easier, because the power of the matrix has been removed – now we only have 3 matrices to multiply, not n. If we sub this back into our formula, we get this:
Don’t worry, it gets better from here! We can multiply all the matrices on the right together into one, which gives us this:
And if we just take the top of each matrix, and substitute in φ and ψ, we get our original formula, Fn=(φn-ψn)/√ 5.
There is a shorter version of the formula – because the Magnitude of ψ is less than 1, ψn gets very small as n gets larger. This means that Fn= [φn/√ 5], where the square brackets mean the value should be rounded to the nearest whole number.