Solving Fibonacci Recurrence

Discrete Math · Axiom Academy

EXAMPLE Solving Fibonacci Recurrence Find the closed-form formula for F(n) = F(n-1) + F(n-2) using the characteristic equation method. Excellent work! You've discovered Binet's Formula, one of the most elegant results in discrete mathematics. Here's what we learned: Characteristic Equation Method: For linear recurrences, assume F(n) = r n and substitute to get a polynomial equation. Golden Ratio Connection: The Fibonacci sequence is intimately connected to φ = (1+√5)/2, which appears throughout nature and mathematics. Linear Combinations: With two distinct roots, the general solution is F(n) = Ar₁ n + Br₂ n , where constants are determined from initial conditions. Closed Form Power: Binet's formula lets us compute F(n) directly without recursion - a huge computational advantage! Verification Tip: Always verify your formula works for the initial conditions before trusting it for larger n. This same characteristic equation technique works for many other linear recurrence relations. You'll use it to solve problems in algorithm analysis, counting problems, and generating functions throughout discrete mathematics!

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