Recurrence Relation Calculator: Solve & Find the Closed Form
First-Order: an = r·an-1 + d
Second-Order: an = c1an-1 + c2an-2
Example: Fibonacci is an=an-1+an-2 with a0=0, a1=1 (c1=1, c2=1) — try the defaults above.
What is Recurrence Relation Solver?
A recurrence relation defines each term of a sequence using earlier terms (like Fibonacci). Solving one means finding a direct formula that computes any term without needing all the previous ones.
How Does This Calculator Work?
Enter the coefficients of your linear recurrence relation and its base case(s). The solver derives the characteristic equation, finds its roots, and builds the closed-form solution step by step.
Common Formulas & Rules
Recurrence relation: a rule like an = an-1 + an-2, plus base case(s).
Closed-form solution: a direct formula for an not requiring earlier terms.
Characteristic equation: for linear recurrences, substituting an = rn turns the recurrence into a polynomial equation whose roots determine the closed form.
Master theorem: gives closed-form time complexity for divide-and-conquer recurrences like T(n) = aT(n/b) + f(n).
Worked Example
For an = 5an-1 - 6an-2, the characteristic equation is r² - 5r + 6 = 0, which factors to (r-2)(r-3) = 0, giving roots r = 2 and r = 3. The closed form is therefore an = C₁·2n + C₂·3n, with constants found from the base cases.
How to find a recurrence relation
A recurrence relation describes each term of a sequence using earlier terms. Finding one is a modelling skill: you look at how the problem for size n is built out of smaller versions of the same problem.
Define a_n precisely. For example, “the number of moves needed for n discs” or “the number of valid strings of length n”.
Compute the first few terms by hand. Small cases reveal the pattern and give you something to check against later.
Look at the last step. Ask what the final move, the last symbol or the last item must be, and how many ways the rest can be completed.
Write the equation that expresses a_n using a_(n−1), a_(n−2) and so on, adding any extra amount that the last step contributes.
State the initial conditions that the equation cannot produce by itself, usually a_0 or a_1 and a_2.
Check the equation against the terms from step 2. If it matches, solve it for a closed form.
Example 1: Tower of Hanoi
To move n discs, move the top n − 1 discs aside, move the largest disc, then move the n − 1 discs back on top. That gives h(n) = 2·h(n−1) + 1 with h(1) = 1, so the sequence is 1, 3, 7, 15, and the closed form is 2ⁿ − 1.
Example 2: binary strings with no two consecutive 0s
Let a_n count such strings of length n. A valid string ends in 1 (the first n − 1 symbols can be any valid string) or ends in 10 (the first n − 2 symbols can be any valid string). So a(n) = a(n−1) + a(n−2) with a(1) = 2 and a(2) = 3. The next terms are 5 and 8: a Fibonacci-type sequence.
Example 3: regions made by n lines
When n lines are drawn in general position, the n-th line crosses the previous n − 1 lines and so cuts n of the existing regions in two. That gives r(n) = r(n−1) + n with r(0) = 1, so the regions number 1, 2, 4, 7, 11, and the closed form is 1 + n(n + 1)/2.
If your recurrence has the form a_n = r·a_(n−1) + d, or a_n = c₁·a_(n−1) + c₂·a_(n−2), enter the coefficients and starting values in the calculator above to get the closed form with the algebra shown.
Study guide: Recurrence Relations
Written for students learning this topic for the first time. Last updated October 2026.
Overview
A recurrence relation defines each term of a sequence from earlier terms, together with initial conditions. Recurrences arise when analysing recursive algorithms (merge sort satisfies T(n) = 2T(n/2) + n), in counting problems, and in finance.
Solving a recurrence means finding a closed form, so you can compute any term directly and see how fast the sequence grows.
Key ideas explained
Recurrences and initial conditions
The recurrence aₙ = 2aₙ₋₁ + 1 with a₀ = 0 produces 0, 1, 3, 7, 15, …, which is 2ⁿ − 1. Without the initial condition there is a whole family of solutions.
First-order linear recurrences
For aₙ = r·aₙ₋₁ + d with r ≠ 1, the closed form is aₙ = rⁿ(a₀ + d/(r − 1)) − d/(r − 1). For r = 1 it is simply a₀ + n·d. The constant −d/(r − 1) is the fixed point of the recurrence.
Second-order linear homogeneous recurrences
For aₙ = c₁aₙ₋₁ + c₂aₙ₋₂, solve the characteristic equation x² − c₁x − c₂ = 0. Distinct roots r₁, r₂ give aₙ = α·r₁ⁿ + β·r₂ⁿ; a repeated root r gives aₙ = (α + βn)·rⁿ. The constants come from the two initial conditions.
Fibonacci and growth rates
The Fibonacci recurrence has roots φ = (1 + √5)/2 ≈ 1.618 and ψ = (1 − √5)/2, so Fₙ = (φⁿ − ψⁿ)/√5. The dominant root controls the long-run growth, which is exponential.
Worked examples
A first-order recurrence
Problem. Solve aₙ = 2aₙ₋₁ + 3 with a₀ = 1.
Here r = 2 and d = 3, so the fixed point is −d/(r − 1) = −3.
Problem. Solve aₙ = 5aₙ₋₁ − 6aₙ₋₂ with a₀ = 1 and a₁ = 4.
Characteristic equation: x² − 5x + 6 = 0, so the roots are 2 and 3.
aₙ = α·2ⁿ + β·3ⁿ.
n = 0 gives α + β = 1; n = 1 gives 2α + 3β = 4. So β = 2 and α = −1.
Check: a₂ = 5·4 − 6·1 = 14 and 2·9 − 4 = 14.
Answer. aₙ = 2·3ⁿ − 2ⁿ.
Enter these same values in the calculator above and compare each step with the working shown here.
Common mistakes to avoid
Forgetting the initial conditions, or applying them to the wrong index.
Sign error in the characteristic equation: aₙ = c₁aₙ₋₁ + c₂aₙ₋₂ gives x² − c₁x − c₂ = 0.
Using the distinct-roots form when the root is repeated.
Not checking the closed form against the first few terms.
Where this shows up in computer science
Divide-and-conquer runtimes such as T(n) = 2T(n/2) + n lead to Θ(n log n).
Compound interest with regular deposits satisfies balanceₙ = (1 + i)·balanceₙ₋₁ + d.
The Tower of Hanoi needs hₙ = 2hₙ₋₁ + 1 moves, which solves to 2ⁿ − 1.
Test yourself
Try each question before opening the answer.
Solve hₙ = 2hₙ₋₁ + 1 with h₁ = 1 (Tower of Hanoi).
hₙ = 2ⁿ − 1.
What is the characteristic equation of aₙ = aₙ₋₁ + aₙ₋₂?
x² − x − 1 = 0, with roots (1 ± √5)/2.
Find the closed form of aₙ = aₙ₋₁ + 4 with a₀ = 7.
aₙ = 7 + 4n.
Frequently asked questions
What is a closed-form solution?
A closed-form solution computes any term of a sequence directly from its index n, without needing to calculate every earlier term first — much faster than repeatedly applying the recurrence.
What is a characteristic equation?
For a linear recurrence, substituting aₙ = rⁿ turns the recurrence into a polynomial equation in r. The roots of this equation determine the structure of the closed-form solution.
Why does algorithm analysis use recurrence relations?
Recursive algorithms naturally define their own runtime as a recurrence (e.g. merge sort: T(n) = 2T(n/2) + n). Solving that recurrence gives the algorithm's actual time complexity.
How do I find a recurrence relation from a problem or sequence?
Define a_n precisely, work out the first few terms by hand, then ask how the n-th case can be built from smaller cases by looking at the last step. Write that as an equation, add initial conditions, and check it against your hand-computed terms.
What is the difference between a recurrence relation and its closed form?
A recurrence defines each term from earlier terms and needs initial conditions. A closed form gives a_n directly as a formula in n, so you can compute any term without calculating all the earlier ones.
We use cookies for essential site functionality and, where enabled, for ads (Google AdSense) and analytics
(Google Analytics). See our Privacy Policy for details.