Recurrence Relation Solver

Use this Recurrence Relation Solver to enter values, adjust options, and review results in a compact responsive workspace.

Results are calculated automatically as you enter data.

Rule

Initial values a(0), a(1), ... Terms to generate Term explorer Display precision

Use a(n-1), a(n-2), numbers, n, common functions, and + - * / ^. Enter exactly one initial value per recurrence order, starting at a(0).

Step-by-step expansion

Selected term a(n) appears here.

Disclaimer: All tools on this site are intended for educational and informational purposes only. Mathematical output for educational use. Verify the rule, initial values, and method before relying on results. See our Terms of Use.

Assumptions and limitations

This Recurrence Relation Solver is for general educational use. Results are estimates or mathematical outputs based on the inputs and stated assumptions, not professional engineering, safety, financial, legal, or academic advice. Check units, rounding, formulas, and limitations before using results for important work. For professional, safety-sensitive, construction, engineering, official, or high-cost uses, verify results with an appropriate method, current standards, required tolerances, and a qualified professional. Use of this calculator is subject to our Terms of Use.

▼ See explanations and tips below ▼

Related Calculators

What Is a Recurrence Relation?

A recurrence relation is a rule that defines each new term of a sequence from earlier terms. Instead of giving one direct formula for the value of $a(n)$, it gives a step-by-step rule for building the sequence.

For example, the recurrence relation

$$ a(n)=a(n-1)+5 $$

says that each new term is $5$ more than the previous term. If the starting value is $a(0)=3$, the sequence begins:

$$ 3,\ 8,\ 13,\ 18,\ 23,\ldots $$

The starting value matters because the recurrence rule alone does not tell you where the sequence begins. With $a(0)=3$, the next term is $8$; with $a(0)=10$, the same rule would produce $10, 15, 20, 25,\ldots$ instead.

In this calculator, sequence indexes are zero-based. That means the first term is labeled $a(0)$, the second is $a(1)$, and the selected term $a(n)$ refers to the term at index $n$ in that zero-based sequence.

Why Recurrence Relations Matter

Recurrence relations are useful whenever a pattern is easier to describe by “what happens next” than by a direct formula. They appear in algebra, discrete mathematics, computer science, combinatorics, algorithm analysis, population models, finance examples, and many classroom sequence problems.

They are especially helpful for:

Generating the first several terms of a sequence.
Checking whether a pattern is arithmetic, geometric, Fibonacci-style, or something more complex.
Connecting recursive definitions with closed-form formulas.
Understanding how starting values affect the entire sequence.
Studying processes where each state depends on one or more earlier states.

A recurrence relation is not always the fastest way to compute a far-away term by hand, but it is often the clearest way to define the pattern.

Key Terms to Know

Sequence: An ordered list of values, such as $3, 8, 13, 18,\ldots$.
Term: One value in a sequence. The expression $a(n)$ means the value at index $n$.
Index: The position label of a term. This calculator uses $0, 1, 2,\ldots$.
Initial values: The starting terms supplied before the recurrence rule begins generating new terms.
Lag: How far back a rule looks. The term $a(n-2)$ has lag $2$ because it uses the term two positions before $a(n)$.
Order: The largest lag used in the recurrence rule. A rule that uses $a(n-2)$ is at least second order.
Closed form: A direct formula for $a(n)$ that does not require calculating every previous term first.
Arithmetic sequence: A sequence with a constant difference between consecutive terms.
Geometric sequence: A sequence with a constant ratio between consecutive nonzero terms.
Linear recurrence relation: A recurrence where previous terms are multiplied by constants and added together, sometimes with an additional term.
Characteristic equation: An algebraic equation used to solve many homogeneous linear recurrence relations with constant coefficients.

How Recurrence Relations Work

A recurrence relation starts with one or more known terms, then applies a rule repeatedly. A general way to write this idea is:

$$ a(n)=f\bigl(a(n-1),a(n-2),\ldots,n\bigr) $$

The function $f$ represents the rule. It might use only the previous term, or it might use several earlier terms. It may also use the index $n$ itself.

For example:

$$ a(n)=a(n-1)+a(n-2) $$

uses the two previous terms, so it needs exactly two starting values. If $a(0)=0$ and $a(1)=1$, then:

$$ a(2)=a(1)+a(0)=1+0=1 $$

$$ a(3)=a(2)+a(1)=1+1=2 $$

$$ a(4)=a(3)+a(2)=2+1=3 $$

The sequence begins:

$$ 0,\ 1,\ 1,\ 2,\ 3,\ 5,\ldots $$

Arithmetic and geometric recurrence rules

An arithmetic sequence can be described recursively as:

$$ a(n)=a(n-1)+d $$

where $d$ is the common difference. With zero-based indexing, the matching closed form is:

$$ a(n)=a(0)+dn $$

A geometric sequence can be described recursively as:

$$ a(n)=r\,a(n-1) $$

where $r$ is the common ratio. With zero-based indexing, the matching closed form is:

$$ a(n)=a(0)r^n $$

These two special cases are common because their patterns are easy to recognize: arithmetic sequences grow by repeated addition, while geometric sequences grow by repeated multiplication.

First-order affine recurrence rules

A first-order affine recurrence has the form:

$$ a(n)=r\,a(n-1)+c $$

Here, $r$ multiplies the previous term and $c$ adds a constant. When $r\ne 1$, one common closed form is:

$$ a(n)=r^n a(0)+c\left(\frac{r^n-1}{r-1}\right) $$

When $r=1$, the rule becomes arithmetic:

$$ a(n)=a(n-1)+c $$

so the closed form is:

$$ a(n)=a(0)+cn $$

Second-order homogeneous linear recurrence rules

A second-order homogeneous linear recurrence has the form:

$$ a(n)=c_1a(n-1)+c_2a(n-2) $$

A standard method for many such recurrences is to form the characteristic equation:

$$ x^2-c_1x-c_2=0 $$

When the characteristic equation has two distinct real roots $\lambda_1$ and $\lambda_2$, the closed form often has this structure:

$$ a(n)=C_1\lambda_1^n+C_2\lambda_2^n $$

The constants $C_1$ and $C_2$ are determined from the initial values. This is why initial values are not optional: they select one sequence from the family of sequences that follow the same recurrence rule.

Not every recurrence relation has a simple closed form, and not every closed form is easy to detect. A generated table of terms can still be useful even when no closed form is shown.

Examples of Recurrence Relations in Practice

Example 1: Arithmetic growth

Suppose the rule is:

$$ a(n)=a(n-1)+5 $$

with initial value:

$$ a(0)=3 $$

Generate terms one at a time:

$$ a(1)=a(0)+5=3+5=8 $$

$$ a(2)=a(1)+5=8+5=13 $$

$$ a(3)=a(2)+5=13+5=18 $$

The first few terms are:

$$ 3,\ 8,\ 13,\ 18,\ldots $$

The common difference is $5$, so the closed form is:

$$ a(n)=3+5n $$

Example 2: Geometric growth

Suppose the rule is:

$$ a(n)=3a(n-1) $$

with initial value:

$$ a(0)=2 $$

Then:

$$ a(1)=3\cdot2=6 $$

$$ a(2)=3\cdot6=18 $$

$$ a(3)=3\cdot18=54 $$

The first few terms are:

$$ 2,\ 6,\ 18,\ 54,\ldots $$

The common ratio is $3$, so the closed form is:

$$ a(n)=2\cdot3^n $$

Example 3: Fibonacci-style recurrence

Suppose the rule is:

$$ a(n)=a(n-1)+a(n-2) $$

with initial values:

$$ a(0)=0,\qquad a(1)=1 $$

Because the rule refers to $a(n-2)$, it needs two initial values. The next terms are:

$$ a(2)=a(1)+a(0)=1+0=1 $$

$$ a(3)=a(2)+a(1)=1+1=2 $$

$$ a(4)=a(3)+a(2)=2+1=3 $$

The sequence begins:

$$ 0,\ 1,\ 1,\ 2,\ 3,\ 5,\ 8,\ldots $$

This is a second-order recurrence because each new term depends on the two previous terms.

Example 4: Match initial values to the recurrence order

Suppose the recurrence rule is:

$$ a(n)=a(n-1)+5 $$

If the only initial value is $a(0)=3$, the sequence begins:

$$ 3,\ 8,\ 13,\ldots $$

Because this is a first-order recurrence, entering $3, 10$ is ambiguous: the rule itself should determine $a(1)$ from $a(0)$.

$$ a(1)=a(0)+5=8 $$

The calculator therefore requires exactly one initial value for this rule and rejects extra values. A second-order rule such as $a(n)=a(n-1)+a(n-2)$ requires exactly two initial values.

$$ a(0)=3,\qquad a(1)=8,\qquad a(2)=13 $$

Matching the number of initial values to the order keeps the generated sequence and any closed form consistent.

$$ 3,\ 8,\ 13,\ 18,\ldots $$

How to Interpret the Result

The selected term result shows the value of $a(n)$ at the currently selected zero-based index. For example, $a(4)=23$ means the term at index $4$ is $23$. Since indexing starts at $0$, this is the fifth displayed term in ordinary counting language.

The order tells you the largest lag used in the rule. A rule using only $a(n-1)$ is first order. A rule using $a(n-2)$ is second order. Higher order rules require more initial values.

A detected arithmetic pattern means the generated terms have a constant difference. A detected geometric pattern means the generated terms have a constant ratio, with checks to avoid dividing by zero. Integer patterns are checked exactly; floating-point patterns use a numerical tolerance.

A detected closed form means the expression was structurally verified as a supported first-order affine or second-order homogeneous constant-coefficient recurrence. Irrational characteristic roots are kept in exact radical form. If no closed form is detected, the sequence may still have one outside these supported families.

The last term is $a(\text{count}-1)$, because the generated list begins at $a(0)$. If you generate $20$ terms, the last displayed index is $19$.

The chart and table are best used together. The chart helps reveal overall growth, decay, oscillation, or sudden changes, while the table gives exact displayed values for each generated term. Expansion steps show how early terms were substituted from previous values, which is often the clearest way to check whether the rule was entered as intended.

Integer-only rules are evaluated exactly, even beyond JavaScript’s ordinary safe-integer range. Rules using decimals, division, mathematical functions, or negative powers use floating-point approximation and are labeled accordingly. Approximate scientific notation follows the selected display precision. To keep the page responsive, an exact term may contain at most 10,000 digits.

Common Mistakes and Misconceptions

Using one-based indexing by habit: In many classrooms, a sequence starts at $a_1$. Here, the first term is $a(0)$.
Providing the wrong number of initial values: A rule that uses $a(n-2)$ needs exactly two initial values. A rule that uses $a(n-3)$ needs exactly three.
Using unsupported notation: Write previous terms as $a(n-k)$, such as $a(n-1)$ or $a(n-2)$.
Putting commas inside the recurrence rule: Commas can separate initial values, but they are not part of the recurrence expression itself.
Overlooking approximation: Functions such as square roots, logarithms, and trigonometric functions are supported, but they use floating-point arithmetic and may accumulate rounding error.
Rounding too early: If you copy rounded displayed values into another calculation, small differences can grow over many recurrence steps.
Assuming “closed form not detected” means “no closed form exists”: It only means the supported detector did not identify one.
Providing extra initial values: Extra values are rejected because they could contradict terms generated by the recurrence.

When to Use Recurrence Relations

Use a recurrence relation when a sequence is naturally described by how each term follows from earlier terms.

Common use cases include:

Generating terms from a recursive definition.
Checking arithmetic or geometric sequence patterns.
Exploring Fibonacci-style sequences.
Comparing a recursive rule with a closed-form expression.
Studying linear recurrences in discrete mathematics.
Testing how different initial values change a sequence.
Creating a table or chart for a sequence before solving it symbolically.

Recurrence relations are also useful when a direct formula is unknown, difficult to derive, or less intuitive than the step-by-step rule.

Limitations and Things to Keep in Mind

This calculator generates a finite list of terms. It does not prove every long-term property of the sequence. A pattern detected from generated terms is evidence about those displayed terms, not a universal proof unless it is supported by separate algebraic reasoning.

The recurrence rule must use supported notation and operations. Previous terms should be written with $a(n-k)$ notation, where $k$ is a positive integer. Rules may use numbers, arithmetic operations, parentheses, previous-term references, and the index $n$. Decimal numbers should use a period, not a decimal comma.

The number of generated terms is limited to $3$ through $80$. Display precision can be set to $4$, $8$, or $12$ decimal places. Floating-point values may be rounded or shown in scientific notation; exact integers are displayed in full up to the 10,000-digit safety limit.

The closed-form display is intentionally limited. It is designed for supported first-order affine rules and supported second-order homogeneous linear rules with real characteristic roots. Many valid recurrence relations, including higher-order recurrences, complex-root cases, nonhomogeneous second-order cases, and rules involving unsupported functions, may still generate terms but will not show a detected closed form.

If a recurrence involves division by zero, overflow, or another operation that produces a non-finite value, the generated sequence is not valid for display. For coursework, proofs, engineering, finance, or scientific work, treat generated values as a checking aid and verify important conclusions with exact algebra, appropriate software, or a qualified expert.

How to Use This Calculator

Enter a recurrence rule using notation such as $a(n)=a(n-1)+5$ or $a(n)=a(n-1)+a(n-2)$.
Enter exactly one initial value for each lag up to the largest lag in the rule. Separate values with commas, spaces, or semicolons.
Choose how many terms to generate, from $3$ through $80$.
Set the display precision to $4$, $8$, or $12$ decimal places.
Generate the sequence and use the term slider to choose which $a(n)$ appears as the main result.
Review the order, detected pattern, closed-form result if available, last term, chart, table, and expansion steps.
Use the examples if you want a quick starting point for Fibonacci-style, arithmetic, geometric, or first-order affine recurrence behavior.

Frequently Asked Questions

Why do recurrence relations need initial values?

A recurrence rule tells you how to continue a sequence, but it does not always tell you where to start. The initial values supply the starting point. Different initial values can produce different sequences even when the recurrence rule is the same.

What does the order of a recurrence relation mean?

The order is the largest number of steps backward that the rule references. A rule using $a(n-1)$ is first order, while a rule using $a(n-2)$ is second order. The calculator requires exactly that many initial values.

Why is the first term labeled $a(0)$?

This calculator uses zero-based indexing, so the first displayed term is $a(0)$. That means $a(1)$ is the second displayed term, $a(2)$ is the third, and so on. Always check the index before comparing results with a textbook that starts at $a_1$.

Does “closed form not detected” mean the sequence has no closed form?

No. It only means the rule did not match one of the supported closed-form detection patterns. Some recurrences have closed forms that require methods beyond the supported cases, and some do not have simple closed forms at all.

Why was my recurrence rule rejected?

The most common reasons are missing previous-term notation, too few initial values, unsupported symbols, decimal commas, non-integer lags, or unsupported function names. Use notation such as $a(n-1)$, keep lags positive integers, and enter initial values as a numeric list.

Sources and References

Books and Open Textbooks

Alan Doerr and Kenneth Levasseur. Applied Discrete Structures. Section 8.3, “Recurrence Relations.” Accessed July 4, 2026. https://discretemath.org/ads/s-recurrence-relations.html
Oscar Levin. Discrete Mathematics: An Open Introduction. 4th ed., Oscar Levin/Open Math Books, 2024. Sections 4.3, 4.4, and 6.1.4 on sequences, characteristic-root methods, and recurrence relations. https://discrete.openmathbooks.org/pdfs/dmoi4.pdf
Jay Abramson et al. Algebra and Trigonometry 2e. OpenStax, Dec. 21, 2021. Sections 13.2 “Arithmetic Sequences” and 13.3 “Geometric Sequences.” Arithmetic sequences; Geometric sequences

Recurrence Relation Solver