Fibonacci Sequence

Definition and formulas

• Recurrence: F(0) = 0, F(1) = 1, F(n) = F(n − 1) + F(n − 2) for n ≥ 2
• Binet's formula: F(n) = (φⁿ − ψⁿ) ÷ √5, with φ = (1 + √5)/2 ≈ 1.618034 and ψ = (1 − √5)/2 ≈ −0.618034
• Rounding shortcut: F(n) is the nearest integer to φⁿ ÷ √5 for n ≥ 0
• Ratio: F(n + 1) ÷ F(n) approaches the golden ratio φ as n grows
• Sum: F(0) + F(1) + … + F(n) = F(n + 2) − 1
• Test: a positive integer x is a Fibonacci number exactly when 5x² + 4 or 5x² − 4 is a perfect square

Sources: NIST Digital Library of Mathematical Functions: DLMF §24.15 Related Sequences of Numbers (Fibonacci numbers)

Fibonacci numbers F(0) to F(50)

Some books start the sequence at F(1) = 1, F(2) = 1. The values are the same; only the index shifts.

Sources: OEIS Foundation: A000045 Fibonacci numbers