Explore discrete dynamics: linear recurrences, modular Fibonacci, and logistic map
1.618
-0.618
1.618
Tends to φ ≈ 1.618034
10
Characteristic roots determine whether the sequence converges, oscillates, or grows without bound.
Every term is a weighted sum of the two preceding ones. The coefficients p and q fully control the long-run behavior — not just the speed of growth, but whether growth happens at all. The Fibonacci sequence (p = 1, q = 1, a₀ = 0, a₁ = 1) is the canonical example: each term is the sum of the two before it, and the ratio between consecutive terms converges to the golden ratio φ ≈ 1.618.
Fibonacci sequence — OEIS A000045Substituting aₙ = rⁿ into the recurrence yields r² − pr − q = 0. The two roots r₁ and r₂ are the building blocks of the general solution: aₙ = A·r₁ⁿ + B·r₂ⁿ, where A and B are determined by the initial conditions a₀ and a₁. If the roots are complex (discriminant < 0), the sequence oscillates with a rotating envelope. The modulus of a complex root is what matters for growth: |r| > 1 means the oscillation grows, |r| < 1 means it decays.
Linear recurrence relations — BrilliantThe decisive quantity is max(|r₁|, |r₂|). If it exceeds 1, the dominant term rⁿ grows exponentially and the sequence diverges — the overflow warning tells you this happened before n = N. If it is exactly 1 (marginal stability), the sequence neither grows nor decays and can oscillate permanently. If it is less than 1, both components decay and the sequence approaches zero. The Convergence Ratio chart shows the quotient aₙ/aₙ₋₁ stabilizing at the dominant root — watching it settle onto the dashed line is a direct visual proof of this theorem.
Difference equations and stability — MIT OCW 18.03