(41) Fibonacci & Lucas numbers

[Albert Chan]

Let g = (1+√5)/2 ≈ 1.618
Let h = 1-g ≈ -0.618 < 0

g^n = g F(n) + F(n-1)
h^n = h F(n) + F(n-1)

sum: L(n) = g^n + h^n = (g+h) F(n) + 2 F(n-1) = F(n) + 2 F(n-1)
difference: g^n - h^n = (g-h) F(n) = (2g-1) F(n) = √(5) F(n)

We can also get F(n) L(n) by curve fitting

XCas> g := (1+sqrt(5))/2
XCas> f(n) := c0*g^n + c1*(1-g)^n
XCas> solve([f(0),f(1)] = [0,1], [c0,c1])     → F(n) coeff = [1/√5, -1/√5]
XCas> solve([f(0),f(1)] = [2,1], [c0,c1])     → L(n) coeff = [1, 1]

As n gets big: F(n+1)/F(n) ≈ g, L(n)/F(n) ≈ 1 + 2/g = 1 + 2*(g^2-g)/g = 2g-1 = √(5)

For n≥3, F(n) = floor(g F(n-1) + .5)
For n≥3, L(n) = floor(√(5) F(n) + .5)