Fibonacci Sequence
Generate the Fibonacci sequence where each number is the sum of the two before it.
Found throughout nature and mathematics.
The Formula
F(n) = F(n-1) + F(n-2) where F(0) = 0, F(1) = 1
Each Fibonacci number is the sum of the two numbers before it. The sequence begins: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, ...
Binet's closed-form formula: F(n) = (φⁿ - ψⁿ) / √5, where φ = (1+√5)/2 ≈ 1.618 (the golden ratio) and ψ = (1-√5)/2 ≈ -0.618.
Variables
| Symbol | Meaning |
|---|---|
| F(n) | The nth Fibonacci number |
| n | Position in the sequence (starting from 0) |
| φ | Golden ratio (approximately 1.61803) |
Example 1
Find the 10th Fibonacci number
F(0)=0, F(1)=1, F(2)=1, F(3)=2, F(4)=3, F(5)=5
F(6)=8, F(7)=13, F(8)=21, F(9)=34, F(10)=55
F(10) = 55
Example 2
Use Binet's formula to find F(12)
F(12) = (1.618¹² - (-0.618)¹²) / √5
F(12) = (321.997 - 0.00319) / 2.236
F(12) = 144
When to Use It
Use the Fibonacci sequence when:
- Studying patterns in nature (sunflower seeds, pinecones, shells)
- Analyzing algorithm complexity (recursive algorithms)
- Working with the golden ratio in art and architecture
- Applying Fibonacci levels in financial trading
Key Notes
- The ratio of consecutive terms converges to the golden ratio φ ≈ 1.618: F(10)/F(9) = 55/34 ≈ 1.6176; by F(20) the ratio is accurate to five decimal places
- Binet's formula is mathematically exact but uses irrational numbers (√5, φ) — floating-point arithmetic introduces rounding errors for large n, making the iterative recurrence more reliable in practice
- Fibonacci spirals in nature (sunflower seeds, pinecones, shell growth) reflect a growth-optimization principle — consecutive Fibonacci numbers of petals or spirals minimize packing overlap, not a strict mathematical law
- Fibonacci numbers appear in Pascal's triangle as diagonal sums, in algorithm analysis (Fibonacci heaps, recursive time complexity), and as retracement levels (23.6%, 38.2%, 61.8%) in technical trading analysis
Key Notes
- Recurrence: F(n) = F(n−1) + F(n−2); F(0) = 0, F(1) = 1: Each term is the sum of the two preceding terms: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, … The sequence appears throughout nature, mathematics, and art.
- Binet's closed form: F(n) = (φⁿ − ψⁿ) / √5: φ = (1+√5)/2 ≈ 1.618 (the golden ratio) and ψ = (1−√5)/2 ≈ −0.618. Despite containing irrational numbers, the result is always an integer. The ψⁿ term becomes negligible for large n: F(n) ≈ φⁿ/√5 (nearest integer).
- Golden ratio connection: The ratio F(n+1)/F(n) converges to φ ≈ 1.618 as n increases. φ satisfies φ² = φ + 1 — it is the positive root of x² − x − 1 = 0. This self-referential property explains the golden ratio's appearance in art, architecture, and natural spiral growth.
- Fibonacci in nature: Petal counts of many flowers are Fibonacci numbers (3, 5, 8, 13 petals are common). Sunflower and pinecone spirals follow adjacent Fibonacci numbers (e.g., 34 and 55). This emerges from optimal packing of new growth, not a mystical preference.
- Applications: Fibonacci numbers appear in algorithm analysis (worst-case inputs for Euclidean GCD algorithm), financial analysis (Fibonacci retracement levels in technical trading), computer science (Fibonacci heaps, Zeckendorf's representation), and as the canonical example for recursion and dynamic programming in computer science courses.