Fibonacci Inequalities

Real Analysis · Axiom Academy

EXAMPLE Fibonacci Inequalities Proving the bound with strong induction The Fibonacci numbers are defined by F(0) = 0 , F(1) = 1 , and F(n) = F(n-1) + F(n-2) for . Prove that for every integer . You proved by strong induction. The reusable ideas: Strong vs. ordinary induction: strong induction assumes the property for every index , not just for n — exactly what a two-term recurrence needs. Match base cases to the recurrence depth: F(n) = F(n-1) + F(n-2) reaches back two terms, so verify two base cases ( n = 0 and n = 1 ). Apply the hypothesis to several terms: for F(n+1) = F(n) + F(n-1) , both indices are , so the hypothesis bounds each summand. Close the algebra with a clean estimate: . What the bound says: F(n) grows exponentially, but strictly slower than 2^n . The same template proves sharper bounds — try showing with , where the golden ratio's identity does the algebraic work.

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