How do you prove Binet's Formula for Fibonacci Numbers using mathematical induction?

Question

The Fibonacci numbers form the sequence 1, 1, 2, 3, 5, 8, 13, 21, 34, ...

where F₁ = 1, F₂ = 1, F_N = F_N-2 + F_N-1.

Binet's Formula is:

F_N = ([(1+√5)/2]^N - [(-1+√5)/2]^N)/√5

Answer 1

You certainly can prove it by induction, but it is more easily proved by solving the difference equation:

E²f_n - Ef_n - f_n = 0 using appropriate initial conditions.

The general solution is immediate:

f_n = A Pⁿ + B Qⁿ where P=[1+√5)/2 and Q=[1-√5)]/2.