Recurrence Relation Solver screenshot

Recurrence Relation Solver

Solve a linear homogeneous recurrence with constant coefficients: characteristic roots, a closed form, and the first N terms checked against the recurrence.

Privacy First
0 Runs
Updated 2026-11-22
Runs in your tab
No upload
Numeric roots
Named refusals

What this page makes

Parses a(n) = c1·a(n−1) + …, finds the characteristic roots numerically, builds the solution basis and prints a closed form with the first terms verified.

How to use it

Type the recurrence, the k initial terms separated by commas, and how many terms to print, then press Solve. The page prints the characteristic roots, the closed form and the checked sequence; a refusal replaces all three when the form is outside the supported set.

Worked example: a(n) = a(n−1) + a(n−2), a(0) = 0, a(1) = 1, 12 terms becomes roots 1.618034 and −0.618034; a(n) ≈ 0.447214·(1.618034)^n − 0.447214·(−0.618034)^n; 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89.

Method

The relation is parsed into coefficients c1 … ck and the polynomial x^k − c1·x^(k−1) − … − ck. Its roots are found with Durand–Kerner. The basis is r^n for a real root, n^j·r^n for multiplicity j+1, and ρ^n·cos(nθ) and ρ^n·sin(nθ) for a complex pair. The k constants solve the initial terms by Gaussian elimination, and the printed closed form is checked against the first N terms computed directly from the recurrence.

What it refuses

A coefficient that contains n is refused as non-constant; a product or power of two past terms is refused as non-linear; a bare constant is refused as inhomogeneous; a gap in the past terms and an order above six are refused by name. The roots are numeric, so a radical is never claimed.

Where it runs

The relation and terms are solved in this tab: nothing is uploaded and nothing is stored. The browser requirement is stated on the page: The solver is JavaScript arithmetic: it needs no browser API, no Web Audio and no network. The page works with scripting enabled and refuses outside its supported form.

The rest of the family

The other audio and recurrence pages are listed under Calculators: tone and binaural generation, the virtual piano, pitch shifting, looping and reversal, the stated noise filter chain, mid/side cancellation, microphone recording and the closed-form recurrence solver.

Parses a(n) = c1·a(n−1) + …, finds the characteristic roots numerically, builds the solution basis and prints a closed form with the first terms verified.

The relation is parsed into coefficients c1 … ck and the polynomial x^k − c1·x^(k−1) − … − ck. Its roots are found with Durand–Kerner. The basis is r^n for a real root, n^j·r^n for multiplicity j+1, and ρ^n·cos(nθ) and ρ^n·sin(nθ) for a complex pair. The k constants solve the initial terms by Gaussian elimination, and the printed closed form is checked against the first N terms computed directly from the recurrence. The relation and terms are solved in this tab: nothing is uploaded and nothing is stored.

Worked example: a(n) = a(n−1) + a(n−2), a(0) = 0, a(1) = 1, 12 terms becomes roots 1.618034 and −0.618034; a(n) ≈ 0.447214·(1.618034)^n − 0.447214·(−0.618034)^n; 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89.

The printed sequence is computed from the recurrence itself, and the closed form is checked against it before it is shown.

How to use the recurrence relation solver

Type the recurrence, the k initial terms separated by commas, and how many terms to print, then press Solve. The page prints the characteristic roots, the closed form and the checked sequence; a refusal replaces all three when the form is outside the supported set.

The relation and terms are solved in this tab: nothing is uploaded and nothing is stored.

  • Domain: Linear homogeneous constant-coefficient recurrences of order 1–6 with real numeric coefficients and k initial terms.

What the page proves

Parses a(n) = c1·a(n−1) + …, finds the characteristic roots numerically, builds the solution basis and prints a closed form with the first terms verified.

The relation is parsed into coefficients c1 … ck and the polynomial x^k − c1·x^(k−1) − … − ck. Its roots are found with Durand–Kerner. The basis is r^n for a real root, n^j·r^n for multiplicity j+1, and ρ^n·cos(nθ) and ρ^n·sin(nθ) for a complex pair. The k constants solve the initial terms by Gaussian elimination, and the printed closed form is checked against the first N terms computed directly from the recurrence.

  • Browser requirement: The solver is JavaScript arithmetic: it needs no browser API, no Web Audio and no network. The page works with scripting enabled and refuses outside its supported form.
  • The page states its domain: Linear homogeneous constant-coefficient recurrences of order 1–6 with real numeric coefficients and k initial terms.

What it refuses, and what it leaves out

A coefficient that contains n is refused as non-constant; a product or power of two past terms is refused as non-linear; a bare constant is refused as inhomogeneous; a gap in the past terms and an order above six are refused by name. The roots are numeric, so a radical is never claimed.

  • Not the right page for: non-constant coefficients such as n·a(n−1)
  • Not the right page for: non-linear recurrences
  • Not the right page for: an inhomogeneous recurrence with an added function of n
  • Reported as a named state: n in a coefficient is a non-constant refusal
  • Reported as a named state: two past terms multiplied is a non-linear refusal
  • Reported as a named state: an order above six is outside the solver

What to Expect

Best for

  • checking a recurrence from a textbook
  • seeing why Fibonacci has a closed form
  • getting the first terms of an order-4 recurrence

Not ideal for

  • non-constant coefficients such as n·a(n−1)
  • non-linear recurrences
  • an inhomogeneous recurrence with an added function of n

What this tool keeps

  • the coefficients, the roots to six decimals and the independently recomputed terms

What may need cleanup

  • nothing: the relation is parsed on each press

Common errors

  • n in a coefficient is a non-constant refusal
  • two past terms multiplied is a non-linear refusal
  • an order above six is outside the solver

Example use cases

  • Fibonacci and Lucas sequences
  • a second-order recurrence with a repeated root
  • a complex-root recurrence such as a(n) = a(n−1) − a(n−2)

Sample input

a(n) = a(n−1) + a(n−2), a(0) = 0, a(1) = 1, 12 terms

Sample output

roots 1.618034 and −0.618034; a(n) ≈ 0.447214·(1.618034)^n − 0.447214·(−0.618034)^n; 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89

Who this is for

  • students checking a recurrence
  • anyone who wants the first terms without iterating by hand

Frequently asked questions

Is my data sent anywhere?

The relation and terms are solved in this tab: nothing is uploaded and nothing is stored.

Which browser API does this page need?

The solver is JavaScript arithmetic: it needs no browser API, no Web Audio and no network. The page works with scripting enabled and refuses outside its supported form.

What can I download?

There is nothing to download: the result is the roots, the closed form and the checked terms on the page.

Is the closed form exact?

The roots are numeric, printed to six decimals, and the constants come from those roots. The printed sequence is computed directly from the recurrence and the closed form is checked against it, so an ill-conditioned root set is refused rather than shown.

Can it solve n·a(n−1)?

No. That is a non-constant coefficient and the page refuses it by name. The characteristic-polynomial method here requires constant coefficients.

What about a(n) = a(n−1) + 5?

That is inhomogeneous and is refused by name. This page solves only the homogeneous form.

Why only order six?

The root finder and the basis solve are numeric and grow quickly with order. Six is the stated limit; a higher order is refused rather than attempted and printed unverified.

Developer program

Build custom tools for your store

Join the SDK program to create useful ecommerce utilities for your store.