It irks me that the elementary derivation of F(2n+1)=4F(n)2−F(n−1)2+2(−1)nF(2n + 1) = 4 F(n)^2 - F(n - 1)^2 + 2(-1)^n feels like a magic trick. I wasn't satisfied with that, so I used a lifeline. I contacted the author of this algorithm in the GMP library, Kevin Ryde. His response offers a peek behind the curtain at how such a result would be found, not just proved.

I won't pretend to understand exactly how it worked, and because this was two decades ago I'm not sure the full process can be retraced. Some highlights to spur your own exploration:

  • Binet's formula highlights the importance of the two roots of x2−x−1=0x^2 - x - 1 = 0, namely ϕ=1+52\phi = \frac{1 + \sqrt{5}}{2} and ψ=1−52\psi = \frac{1 - \sqrt{5}}{2}. Those are the two numbers with the property that ϕ1,ϕ2,ϕ3,…\phi^1, \phi^2, \phi^3, \dots form a sequence obeying the Fibonacci recurrence.
  • We can note that ϕψ\phi \psi = (1+5)(1−5)2×2=−1\frac{(1 + \sqrt{5})(1 - \sqrt{5})}{2 \times 2} = -1.
  • So, if F(n)=aϕn+bψnF(n) = a\phi^n + b \psi^n, with a,ba, b being constants that determine the starting values, we have that F(2n)=aϕ2n+bψ2nF(2n) = a \phi^{2n} + b \psi^{2n}. Comparing with F(n)2F(n)^2, which is a2ϕ2n+2ab(ϕψ)n+b2ϕ2na^2 \phi^{2n} + 2ab(\phi \psi)^n + b^2 \phi^{2n}, we note that (ϕψ)n=(−1)n(\phi \psi)^n = (-1)^n plays an important role.
  • From this, we might conjecture that F(2n+1)F(2n + 1) can be represented as xF(n)2+yF(n−1)2+z(−1)nx F(n)^2 + y F(n - 1)^2 + z(-1)^n. (This is the part I'm still not 100% on, if you couldn't tell.)
  • Once we make this conjecture, it's actually quite simple to find the proper constants. We can simply pick any three values of nn to get three equations in three variables and then solve the system for x,y,zx, y, z. Doing this gives you (x,y,z)=(4,−1,2)(x, y, z) = (4, -1, 2), exactly the values we derived above.
  • From there, you're trying to prove the identity holds for all nn, which can be achieved many ways: through algebraic manipulation, as above, or through induction or Binet's formula.

Hopefully that helps if you also find random algebra disheartening. My thanks to Kevin Ryde for responding to a random email about a decades-old piece of programming he did!

We're almost to the conclusion of our tour through the land of Fibonacci. What remains is to use this recursion and arrive at the current state of the art for computing F(n)F(n).

It irks me that the elementary derivation of F(2n+1)=4F(n)2−F(n−1)2+2(−1)nF(2n + 1) = 4 F(n)^2 - F(n - 1)^2 + 2(-1)^n feels like a magic trick. I wasn't satisfied with that, so I used a lifeline. I contacted the author of this algorithm in the GMP library, Kevin Ryde. His response offers a peek behind the curtain at how such a result would be found, not just proved.

I won't pretend to understand exactly how it worked, and because this was two decades ago I'm not sure the full process can be retraced. Some highlights to spur your own exploration:

  • Binet's formula highlights the importance of the two roots of x2−x−1=0x^2 - x - 1 = 0, namely ϕ=1+52\phi = \frac{1 + \sqrt{5}}{2} and ψ=1−52\psi = \frac{1 - \sqrt{5}}{2}. Those are the two numbers with the property that ϕ1,ϕ2,ϕ3,…\phi^1, \phi^2, \phi^3, \dots form a sequence obeying the Fibonacci recurrence.
  • We can note that ϕψ\phi \psi = (1+5)(1−5)2×2=−1\frac{(1 + \sqrt{5})(1 - \sqrt{5})}{2 \times 2} = -1.
  • So, if F(n)=aϕn+bψnF(n) = a\phi^n + b \psi^n, with a,ba, b being constants that determine the starting values, we have that F(2n)=aϕ2n+bψ2nF(2n) = a \phi^{2n} + b \psi^{2n}. Comparing with F(n)2F(n)^2, which is a2ϕ2n+2ab(ϕψ)n+b2ϕ2na^2 \phi^{2n} + 2ab(\phi \psi)^n + b^2 \phi^{2n}, we note that (ϕψ)n=(−1)n(\phi \psi)^n = (-1)^n plays an important role.
  • From this, we might conjecture that F(2n+1)F(2n + 1) can be represented as xF(n)2+yF(n−1)2+z(−1)nx F(n)^2 + y F(n - 1)^2 + z(-1)^n. (This is the part I'm still not 100% on, if you couldn't tell.)
  • Once we make this conjecture, it's actually quite simple to find the proper constants. We can simply pick any three values of nn to get three equations in three variables and then solve the system for x,y,zx, y, z. Doing this gives you (x,y,z)=(4,−1,2)(x, y, z) = (4, -1, 2), exactly the values we derived above.
  • From there, you're trying to prove the identity holds for all nn, which can be achieved many ways: through algebraic manipulation, as above, or through induction or Binet's formula.

Hopefully that helps if you also find random algebra disheartening. My thanks to Kevin Ryde for responding to a random email about a decades-old piece of programming he did!

We're almost to the conclusion of our tour through the land of Fibonacci. What remains is to use this recursion and arrive at the current state of the art for computing F(n)F(n).