Recurrence Relation Calculator
Solve linear recurrence relations a_n = p*a_{n-1} + q*a_{n-2} with given initial conditions.
About this calculator
This calculator computes term a(n) of a second-order linear recurrence a_n = p·a_{n-1} + q·a_{n-2} by iterating forward from two initial values, a₀ and a₁ — the default inputs (a₀ = 0, a₁ = 1, p = 1, q = 1) build the ordinary Fibonacci sequence, so a(10) comes out to 55. Target n has the largest measured effect on a(n) Value among the five inputs under a small nudge, ahead of Coefficient p, Coefficient q, and a₁ — a₀ is excluded from that ranking entirely because it defaults to 0, and a percentage-based nudge of zero stays zero. Alongside the iterative value, the calculator also computes a Closed-Form Estimate from the recurrence's characteristic equation x² − px − q = 0, but only for two of its three possible root cases: a real, distinct-roots formula when the discriminant p² + 4q is positive, and a repeated-root formula when it equals exactly 0.
When the discriminant is negative — meaning the characteristic roots are complex, which happens for oscillating recurrences like p = 1, q = -1 — neither branch runs, and closedFormEstimate silently falls back to its initialized value of the plain iterative a(n), rather than computing an actual closed form or flagging that one wasn't produced. The default inputs never reach that branch, since p² + 4q = 5 stays positive under any small nudge to p or q alone.
Inputs
Results
a(n) Value
55
How to Use This Calculator
- Enter the initial values a0 and a1 for the two-term recurrence.
- Set Coefficient p (for a_{n-1}) and Coefficient q (for a_{n-2}).
- Enter Target n to compute the nth term of the sequence.
- Review a(n) Value from the iterative calculation and the Closed-Form Estimate.
- Use the Closed-Form Estimate to identify the dominant growth rate (exponential, polynomial, etc.).
How the result changes with Target n
| Target n | a(n) Value |
|---|---|
| 5 | 5 |
| 7.5 | 21 |
| 15 | 610 |
| 25 | 75,025 |
What each input means
- a₀ (initial value)
- First initial condition a₀
- a₁ (initial value)
- Second initial condition a₁
- Coefficient p
- Coefficient of a_{n-1} in the recurrence a_n = p*a_{n-1} + q*a_{n-2}
- Coefficient q
- Coefficient of a_{n-2} in the recurrence a_n = p*a_{n-1} + q*a_{n-2}
- Target n
- Compute the sequence up to this index
How this is calculated
Worked example, using the default values
- Identify Input Parameters4 parametersa₀ (initial value) = 0, a₁ (initial value) = 1, Coefficient p = 1, Coefficient q = 1 = 5 input(s) provided
- Calculate a(n) Valuea(n) Value55 = 55
- Calculate Closed-Form EstimateClosed-Form Estimate55 = 55
Engine last updated . Checked against 3 independently-derived tests — how we verify calculators. Built by Paul Gunder, a software engineer, not a licensed financial, medical, or legal professional.
Frequently Asked Questions
Why does Target n move a(n) Value more than any other input?
Every other input holds the recurrence's shape fixed while Target n decides how many times the recurrence a_n = p·a_{n-1} + q·a_{n-2} gets applied. For the default Fibonacci-like setup, a(n) grows roughly exponentially with n, so a small nudge to Target n moves the result proportionally more than the same-sized nudge to a coefficient or initial value does.
What happens to the Closed-Form Estimate when the characteristic roots are complex?
The engine only computes a closed form when the discriminant p² + 4q is positive (distinct real roots) or exactly 0 (a repeated real root); when it's negative, neither of those code paths runs, and closedFormEstimate silently keeps its initial value, which is just the plain iterative a(n) — not an actual closed-form formula, and with no indication in the output that this happened.
Why does a₀ never show up as affecting a(n) Value in a sensitivity check?
a₀ defaults to 0, and the check nudges each input to 110% and 90% of its current value in turn. Since 110% and 90% of zero are both still zero, a₀ never actually changes during that test, so it's left out of the ranking altogether rather than being reported with a measured effect of zero.
Why does the default setup produce exactly the Fibonacci sequence?
With a₀ = 0, a₁ = 1, Coefficient p = 1, and Coefficient q = 1, the recurrence a_n = p·a_{n-1} + q·a_{n-2} becomes a_n = a_{n-1} + a_{n-2} with the standard Fibonacci starting values — the exact definition of the Fibonacci sequence, which is why a(10) comes out to 55, the eleventh Fibonacci number counting from F(0) = 0.
Related Calculators
The questions that sit next to this one — chosen by subject, including calculators filed under a different category.
Permutations & Combinations Calculator
Calculate permutations and combinations with or without repetition for any n and r values.
Discrete MathematicsSequence Analyzer & Generating Function
Analyze a sequence to detect arithmetic, geometric, or polynomial patterns and predict the next term.
Math & StatisticsQuadratic Equation Solver
Solve quadratic equations (ax² + bx + c = 0). Find roots, discriminant, vertex, and axis of symmetry with a visual graph.
Number TheoryFibonacci Calculator
Calculate the nth Fibonacci number, its predecessor, and the golden ratio approximation F(n)/F(n-1).
Astrophysics & AstronomyStellar Mass Calculator
Calculate stellar mass using mass-luminosity relation, mass-radius relation, and orbital dynamics.
More in Math & Statistics.