Deriving Binet's Formula

From before, we have that Mn(10)=(F(n+1)F(n))M^n \begin{pmatrix} 1 \\ 0 \end{pmatrix} = \begin{pmatrix} F(n + 1) \\ F(n) \end{pmatrix}. From this we can derive that F(n)F(n) is equal to the bottom left element of MnM^n. In fact, in general we have Mn=(F(n+1)F(n)F(n)F(n1))M^n = \begin{pmatrix} F(n + 1) & F(n) \\ F(n) & F(n - 1) \end{pmatrix}

(Proof left as an exercise to the reader!)

We can use our diagonalization to find a closed form for this value: let the number crunching commence! (I'm writing it out here for pedagogical purposes, but in the real world I am 100% using a computer to do all of this math for me.)

Mn=PDnP1=(ϕψ11)(ϕn00ψn)[15(1ψ1ϕ)]=15(ϕψ11)(ϕn00ψn)(1ψ1ϕ)=15(ϕψ11)(ϕnψϕnψnϕψn)=15(ϕn+1ψn+1ψϕn+1+ϕψn+1ϕnψnϕψnψϕn) \begin{aligned} M^n &= PD^nP^{-1} \\ &= \begin{pmatrix} \phi & \psi \\ 1 & 1 \end{pmatrix} \begin{pmatrix}\phi^n & 0 \\ 0 & \psi^n \end{pmatrix} \left[\frac{1}{\sqrt{5}} \begin{pmatrix} 1 & -\psi \\ -1 & \phi \end{pmatrix}\right] \\ &= \frac{1}{\sqrt{5}} \begin{pmatrix} \phi & \psi \\ 1 & 1 \end{pmatrix} \begin{pmatrix}\phi^n & 0 \\ 0 & \psi^n \end{pmatrix} \begin{pmatrix} 1 & -\psi \\ -1 & \phi \end{pmatrix} \\ &= \frac{1}{\sqrt{5}} \begin{pmatrix} \phi & \psi \\ 1 & 1 \end{pmatrix} \begin{pmatrix}\phi^n & -\psi \phi^n \\ -\psi^n & \phi \psi^n \end{pmatrix} \\ &= \frac{1}{\sqrt{5}} \begin{pmatrix} \phi^{n+1} - \psi^{n+1} & -\psi \phi^{n+1} + \phi \psi^{n+1} \\ \phi^n - \psi^n & \phi \psi^n - \psi \phi^n \end{pmatrix} \\ \end{aligned}

To simplify further, we can use a special property of the golden ratio to rewrite ψ\psi in terms of ϕ\phi: 1ϕ=21+5=2(15)(1+5)(15)=2(15)4=152=ψ \begin{aligned} -\frac{1}{\phi} &= \frac{-2}{1 + \sqrt{5}} \\ &= \frac{-2(1 - \sqrt{5})}{(1 + \sqrt{5})(1 - \sqrt{5})} \\ &= \frac{-2(1 - \sqrt{5})}{-4} \\ &= \frac{1 - \sqrt{5}}{2} \\ &= \psi \end{aligned}

This lets us simplify further:

Mn=PDnP1=15(ϕn+1ψn+1ψϕn+1+ϕψn+1ϕnψnϕψnψϕn)=15(ϕn+1ψn+1ϕnψnϕnψnϕn1ψn1) \begin{aligned} M^n &= PD^nP^{-1} \\ &= \frac{1}{\sqrt{5}} \begin{pmatrix} \phi^{n+1} - \psi^{n+1} & -\psi \phi^{n+1} + \phi \psi^{n+1} \\ \phi^n - \psi^n & \phi \psi^n - \psi \phi^n \end{pmatrix} \\ &= \frac{1}{\sqrt{5}} \begin{pmatrix} \phi^{n+1} - \psi^{n+1} & \phi^{n} - \psi^{n} \\ \phi^n - \psi^n & \phi^{n-1} - \psi^{n-1} \end{pmatrix} \\ \end{aligned}

Remember, F(n)F(n) is the bottom-left element.1 So, at long last, we have a closed form for F(n)F(n):

F(n)=ϕnψn5 \boxed{F(n) = \frac{\phi^n - \psi^n}{\sqrt{5}}}

🥳

That was quite the derivation!2 Our result is known as Binet's formula.


  1. You can instead multiply this by a vector like we did above: this lets you use any set of initial conditions, not just F(0)=0,F(1)=1F(0) = 0, F(1) = 1.
  2. There are other, faster derivations, but I think many of them suffer from a sense of pulling rabbits out of hats. Diagonalization is a very commmon real-world technique, especially for exponentiation of matrices, so it's only natural to try it here.

Deriving Binet's Formula

From before, we have that Mn(10)=(F(n+1)F(n))M^n \begin{pmatrix} 1 \\ 0 \end{pmatrix} = \begin{pmatrix} F(n + 1) \\ F(n) \end{pmatrix}. From this we can derive that F(n)F(n) is equal to the bottom left element of MnM^n. In fact, in general we have Mn=(F(n+1)F(n)F(n)F(n1))M^n = \begin{pmatrix} F(n + 1) & F(n) \\ F(n) & F(n - 1) \end{pmatrix}

(Proof left as an exercise to the reader!)

We can use our diagonalization to find a closed form for this value: let the number crunching commence! (I'm writing it out here for pedagogical purposes, but in the real world I am 100% using a computer to do all of this math for me.)

Mn=PDnP1=(ϕψ11)(ϕn00ψn)[15(1ψ1ϕ)]=15(ϕψ11)(ϕn00ψn)(1ψ1ϕ)=15(ϕψ11)(ϕnψϕnψnϕψn)=15(ϕn+1ψn+1ψϕn+1+ϕψn+1ϕnψnϕψnψϕn) \begin{aligned} M^n &= PD^nP^{-1} \\ &= \begin{pmatrix} \phi & \psi \\ 1 & 1 \end{pmatrix} \begin{pmatrix}\phi^n & 0 \\ 0 & \psi^n \end{pmatrix} \left[\frac{1}{\sqrt{5}} \begin{pmatrix} 1 & -\psi \\ -1 & \phi \end{pmatrix}\right] \\ &= \frac{1}{\sqrt{5}} \begin{pmatrix} \phi & \psi \\ 1 & 1 \end{pmatrix} \begin{pmatrix}\phi^n & 0 \\ 0 & \psi^n \end{pmatrix} \begin{pmatrix} 1 & -\psi \\ -1 & \phi \end{pmatrix} \\ &= \frac{1}{\sqrt{5}} \begin{pmatrix} \phi & \psi \\ 1 & 1 \end{pmatrix} \begin{pmatrix}\phi^n & -\psi \phi^n \\ -\psi^n & \phi \psi^n \end{pmatrix} \\ &= \frac{1}{\sqrt{5}} \begin{pmatrix} \phi^{n+1} - \psi^{n+1} & -\psi \phi^{n+1} + \phi \psi^{n+1} \\ \phi^n - \psi^n & \phi \psi^n - \psi \phi^n \end{pmatrix} \\ \end{aligned}

To simplify further, we can use a special property of the golden ratio to rewrite ψ\psi in terms of ϕ\phi: 1ϕ=21+5=2(15)(1+5)(15)=2(15)4=152=ψ \begin{aligned} -\frac{1}{\phi} &= \frac{-2}{1 + \sqrt{5}} \\ &= \frac{-2(1 - \sqrt{5})}{(1 + \sqrt{5})(1 - \sqrt{5})} \\ &= \frac{-2(1 - \sqrt{5})}{-4} \\ &= \frac{1 - \sqrt{5}}{2} \\ &= \psi \end{aligned}

This lets us simplify further:

Mn=PDnP1=15(ϕn+1ψn+1ψϕn+1+ϕψn+1ϕnψnϕψnψϕn)=15(ϕn+1ψn+1ϕnψnϕnψnϕn1ψn1) \begin{aligned} M^n &= PD^nP^{-1} \\ &= \frac{1}{\sqrt{5}} \begin{pmatrix} \phi^{n+1} - \psi^{n+1} & -\psi \phi^{n+1} + \phi \psi^{n+1} \\ \phi^n - \psi^n & \phi \psi^n - \psi \phi^n \end{pmatrix} \\ &= \frac{1}{\sqrt{5}} \begin{pmatrix} \phi^{n+1} - \psi^{n+1} & \phi^{n} - \psi^{n} \\ \phi^n - \psi^n & \phi^{n-1} - \psi^{n-1} \end{pmatrix} \\ \end{aligned}

Remember, F(n)F(n) is the bottom-left element.1 So, at long last, we have a closed form for F(n)F(n):

F(n)=ϕnψn5 \boxed{F(n) = \frac{\phi^n - \psi^n}{\sqrt{5}}}

🥳

That was quite the derivation!2 Our result is known as Binet's formula.


  1. You can instead multiply this by a vector like we did above: this lets you use any set of initial conditions, not just F(0)=0,F(1)=1F(0) = 0, F(1) = 1.
  2. There are other, faster derivations, but I think many of them suffer from a sense of pulling rabbits out of hats. Diagonalization is a very commmon real-world technique, especially for exponentiation of matrices, so it's only natural to try it here.