Recurrence Sequence Calculator

Frequently Asked Questions

What is a linear recurrence?

A sequence where each term is a fixed linear combination of previous terms, e.g. Fibonacci: F(n) = F(n−1) + F(n−2).

What can I configure?

The order, the coefficients, and the seed (initial) values, so you can generate Fibonacci, Lucas, Pell, or any custom sequence.

How many terms can it generate?

As many as you request; very large terms grow quickly, so values are shown exactly until they exceed safe precision.

What is the characteristic equation?

Substituting xⁿ into the recurrence gives a polynomial whose roots determine the closed-form growth rate (the golden ratio for Fibonacci).

Provided by AllCalculators.io
Free online calculators for everyday. No registration required.

Estimates for informational purposes only.

Important Disclaimer: Estimates for informational purposes only.

This calculator provides estimates for informational purposes only. Results are based on assumptions and may not reflect actual outcomes. Consult qualified professionals in relevant fields before making important decisions based on these results.

JavaScript is required to use the interactive calculator above. The questions and answers below remain readable without JavaScript.

How This Calculator Works

A linear recurrence defines each term from the ones before it: a_n = c₁a_n−1 + c₂a_n−2 (optionally + c₃a_n−3). You supply the coefficients and the first few seed terms; the tool iterates the rule forward to list the sequence, report the n-th term, and track the ratio a_n÷a_n−1. For a second-order recurrence that ratio converges to the dominant root of the characteristic equation x² = c₁x + c₂, namely (c₁ + √(c₁² + 4c₂))÷2. This is intentionally distinct from the arithmetic/geometric Sequence calculator: those add or multiply by a fixed step, whereas a recurrence blends multiple previous terms, producing exponential growth governed by characteristic roots rather than a single common difference or ratio.

Worked Example: Fibonacci and φ

With c₁ = c₂ = 1 and seeds a₀ = 0, a₁ = 1 you get 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, … - each term the sum of the two before it. The ratio of consecutive terms marches toward the golden ratio φ = (1 + √5)÷2 ≈ 1.61803399, exactly the dominant characteristic root. Lucas numbers (seeds 2, 1) share that limit. Pell numbers use c₁ = 2, converging to the silver ratio 1 + √2 ≈ 2.41421356, and Tribonacci (order 3, all coefficients 1) tends to ≈ 1.83928676.

Where Recurrences Are Used

Algorithm analysis: running-time recurrences (e.g. T(n) = 2T(n÷2) + n) describe divide-and-conquer cost.

Finance: loan balances and annuities are first-order recurrences; population and compound models are higher order.

Nature & design: Fibonacci appears in phyllotaxis, spirals, and the golden ratio in art and architecture.

Signal processing: digital IIR filters are linear recurrences over past inputs and outputs.

Common Mistakes & Edge Cases

You need exactly as many seed terms as the order - a 2nd-order rule needs a₀ and a₁; a 3rd-order also needs a₂.

The index convention matters: here the first listed term is a₀, so the "10th term" is a₉.

The ratio limit exists only when the characteristic roots are real and distinct; equal or complex roots give oscillation, not convergence.

Growth is exponential - large n quickly exceeds JavaScript's exact-integer range, so far-out terms are approximate.

If the dominant |root| < 1 the sequence decays to 0; if a seed is 0 the printed ratio for that step is undefined.

The Characteristic Equation Explains Everything

Substituting the trial solution a_n = rⁿ into a_n = c₁a_n−1 + c₂a_n−2 and dividing through gives r² = c₁r + c₂, the characteristic equation. Its two roots r₁, r₂ determine the entire sequence: the general term is a_n = A·r₁ⁿ + B·r₂ⁿ, with A and B fixed by the seeds. The dominant root (largest in absolute value) eventually swamps the other, which is why consecutive ratios converge to it - for Fibonacci that root is φ, and the second root (1−φ) ≈ −0.618 decays to zero. Equal roots give a term n·rⁿ; complex roots give oscillation dressed as a damped or growing sinusoid. This single equation explains growth rate, the golden ratio limit, and stability all at once.

Related Tools & Limits

For purely additive or multiplicative progressions use the dedicated arithmetic/geometric Sequence calculator instead. Binet's closed form gives the n-th Fibonacci directly from φ, and the matrix-power method computes a_n in O(log n) - both natural extensions once the characteristic equation is understood. This tool supports orders 2 and 3 with constant coefficients; variable-coefficient or non-linear recurrences behave very differently. Terms beyond about a₇₈ for Fibonacci exceed the safe-integer range and lose exact precision.

Recurrence Sequence Calculator

Frequently Asked Questions

Related Math Calculators