Fibonacci Formula Proof

Intro to Proofs · Axiom Academy

EXAMPLE Proving Binet's Formula Derive and prove the closed-form formula for the Fibonacci numbers using strong induction The Fibonacci numbers are defined recursively by F_n = F_ n-1 + F_ n-2 with F_0 = 0 and F_1 = 1 . Prove that they also satisfy the closed-form Binet's formula , where and are the roots of x^2 = x + 1 . You've proven one of mathematics' most striking formulas. Here's what makes this proof work: The golden ratio emerges: the Fibonacci sequence, which looks purely combinatorial, is tied to , a constant that appears throughout mathematics and nature. Closed form from recursion: we turned a recursive definition into an exact formula, so F_n can be computed directly without building up every earlier term. Strong induction structure: we needed two base cases and assumed two consecutive cases in the inductive hypothesis — the signature of strong induction. Algebraic magic: the proof hinges on and , which come straight from the characteristic equation x^2 = x + 1 . Integers from irrationals: the formula combines and powers of to produce whole numbers — a clean example of mathematical elegance. Binet's formula shows how induction can reveal a deep connection between seemingly unrelated ideas — here, the recursive Fibonacci numbers and the golden ratio that runs through nature, art, and architecture.

This is the written version of the interactive lesson above. See the full Intro to Proofs course.