ℕ

Fibonacci Sequence

Middle School

Definition

The Fibonacci sequence is where each term is the sum of the two preceding terms. F(1)=1, F(2)=1, F(n)=F(n-1)+F(n-2).

Fₙ = F_n-1 + F_n-2

Fibonacci recurrence

Fₙ = (φⁿ - ψⁿ)/(√5)

Binet's formula (φ = golden ratio)

lim_n → ∈fty \fracF_n+1Fₙ = φ = \frac1+√52

Convergence to golden ratio

Example 1

List the first 10 Fibonacci numbers.

Discovered by: Leonardo Fibonacci (1202)

Fibonacci introduced this sequence while explaining rabbit breeding.

Sunflower seeds, shell spirals

Fibonacci retracement

Fibonacci heap, DP example