Recurrence Relation Solver Calculator

Work out recurrence relation solver instantly with clear inputs, formula shown and shareable results.

About Recurrence Relation Solver Calculator

A first-order linear recurrence T(n) = a·T(n−1) + b has the closed form aⁿT(0) + b(aⁿ − 1)/(a − 1), found by unrolling the recursion and summing a geometric series. When a = 1 the growth is linear instead.

Formula

Closed form

T(n) = aⁿ·T(0) + b·(aⁿ − 1)/(a − 1) for a ≠ 1

Worked example

With the default values below, Recurrence Relation Solver Calculator returns T(n) from the closed form of 4,093.000000. Change any input above and every figure here is recalculated in your browser.

Inputs used

Coefficient a in T(n) = a·T(n−1) + b: 2
Constant b: 3
Initial value T(0): 1
Evaluate at naccepts 0–200: 10

Results

T(n) from the closed form: 4,093.000000
T(n) by direct iteration: 4,093.000000
Closed form used: T(n) = aⁿ·T(0) + b(aⁿ − 1)/(a − 1)
Fixed point b/(1 − a): -3.00000000

Step by step

1Values used
2Closed form
3T(n) from the closed form= 4,093.000000
4T(n) by direct iteration= 4,093.000000
5Closed form used= T(n) = aⁿ·T(0) + b(aⁿ − 1)/(a − 1)
6Fixed point b/(1 − a)= -3.00000000

Assumptions and limits

The result is derived only from the 4 inputs listed above. Anything not among them is not part of the calculation.
In particular, this calculator does not take inflation, tax, fees or charges or compounding frequency into account.
Figures are rounded for display to 8 decimal places, so totals built from several rounded parts can differ slightly from the unrounded arithmetic.

How these calculators are built and tested is described on the Methodology page. If a figure looks wrong, please report it.

Frequently Asked Questions

For T(n) = 2T(n−1) + 3 with T(0) = 1?

T(10) = 1024 + 3 × 1023 = 4093, which the direct iteration confirms.

Why does a > 1 mean exponential growth?

The aⁿ factor dominates, so the recursion multiplies rather than adds — the reason naive recursive Fibonacci is so slow.