Binet's Formula

Combinatorics · Axiom Academy

Deriving the closed-form formula for Fibonacci numbers using the characteristic equation method 1. The Characteristic Equation We start by assuming solutions of the form F n = r n for some constant r . Substituting this into the recurrence relation gives us the characteristic equation. For linear recurrence relations, we can find solutions by solving a polynomial equation called the characteristic equation. We solve the characteristic equation r 2 - r - 1 = 0 using the quadratic formula. The two roots are intimately connected to the golden ratio. Since we have two distinct roots, the general solution is a linear combination: F n = A n + B n . We use initial conditions to find the constants A and B. 4. Applying Initial Conditions We use F 0 = 0 and F 1 = 1 to create a system of equations that determines A and B. From F 0 = 0: A + B = 0, so B = -A Solving for A and B yields the remarkable closed-form formula for Fibonacci numbers.

This is the written version of the interactive lesson above. See the full Combinatorics course.