derivation of Binet formula
The characteristic polynomial for the Fibonacci recurrence is
The solutions of the characteristic equation are
so the closed formula for the Fibonacci sequence must be of the form
for some real numbers . Now we use the boundary conditions of the recurrence, that is, , which means we have to solve the system
The first equation simplifies to and substituting into the second one gives:
Therefore
and so