Recurrence Relation Solver

Math Algebra • Sequences and Series

Written by STEM Calculators Team Published December 19, 2025 Updated February 24, 2026

3. Recurrence Relation Solver

Solve linear recurrences (order 1 or 2) using characteristic equations + initial conditions. Includes Fibonacci preset and term step-through.

Order: Compute up to \(n\) (max 50):

Recurrence coefficients

\(p\):

\(q\):

Include constant term \(c\) (non-homogeneous)

\(c\):

If \(c\neq 0\), the solver shows a particular solution (constant / linear / quadratic).

Initial conditions

\(a_0\):

Used for both order 1 and order 2.

\(a_1\):

Needed for order 2. (Order 1 computes \(a_1\) automatically.)

Graph options:

Connect points Show values on all points Auto label density (for large \(N\))

Step-through:

Ready

Graph

Axes are labeled clearly: n (index) and aₙ (value). Drag to pan • wheel/pinch to zoom • values are written on points.

n: 0, aₙ: 0 sx: 60, sy: 35 Step: \(n=10\)

Click Solve & Generate to see the characteristic equation, closed form, and a term table.

Rate this calculator

0.0 /5 (0 ratings)

Be the first to rate.

Your rating

Name (optional) Review (optional)

You can update your rating any time.

Theory: Solving Linear Recurrence Relations (Order 1–2)

A recurrence relation defines a sequence using previous terms. In this calculator we focus on constant-coefficient recurrences up to order 2, with given initial values (like \(a_0\), \(a_1\)).

1) Order 1: \(a_n = p\,a_{n-1} + c\)

If \(c=0\), the recurrence is homogeneous and the solution is exponential:

\[ a_n = a_0\,p^n. \]

If \(c\neq 0\) (non-homogeneous), we look for a particular solution. A constant trial \(a_n^{(p)}=P\) works when \(p\neq 1\):

\[ P = pP + c \;\Rightarrow\; P=\frac{c}{1-p}. \]

When \(p=1\), the constant trial fails and the particular becomes linear:

\[ a_n = a_0 + cn \qquad (p=1). \]

2) Order 2 (homogeneous): \(a_n = p\,a_{n-1} + q\,a_{n-2}\)

Try \(a_n=r^n\). Substituting gives the characteristic equation:

\[ r^2 - pr - q = 0. \]

Let the roots be \(r_1, r_2\). Then:

\[ a_n= \begin{cases} A r_1^n + B r_2^n, & r_1\neq r_2,\\[6pt] (A+Bn)\,r^n, & r_1=r_2=r. \end{cases} \]

If the roots are complex \(r=\alpha\pm i\beta\), the real form is:

\[ a_n=\rho^n\left(C\cos(n\theta)+D\sin(n\theta)\right), \quad \rho=\sqrt{\alpha^2+\beta^2},\quad \theta=\arg(\alpha+i\beta). \]

The constants \(A,B\) (or \(C,D\)) are determined by the initial conditions.

3) Order 2 with constant term: \(a_n = p\,a_{n-1} + q\,a_{n-2} + c\)

When a constant \(c\) is present, we write \[ a_n = b_n + a_n^{(p)}, \] where \(b_n\) solves the homogeneous recurrence and \(a_n^{(p)}\) is a particular solution.

A constant trial \(a_n^{(p)}=P\) works if \(1-p-q\neq 0\):

\[ P=\frac{c}{1-p-q}. \]

If \(1-p-q=0\), then \(r=1\) is a root of the characteristic equation, so the particular must be multiplied by \(n\) (linear), and in the double-root case by \(n^2\) (quadratic).

4) Fibonacci as a classic example

Fibonacci satisfies \(a_n=a_{n-1}+a_{n-2}\), \(a_0=0\), \(a_1=1\). The roots are \(\varphi=\frac{1+\sqrt5}{2}\) and \(\psi=\frac{1-\sqrt5}{2}\), giving:

\[ \boxed{a_n=\frac{\varphi^n-\psi^n}{\sqrt5}}. \]

University note

For harder recurrences (non-constant coefficients, or more complicated forcing terms), a common next tool is generating functions. The idea is to encode \(\{a_n\}\) into a power series \(G(x)=\sum_{n\ge0}a_n x^n\) and turn the recurrence into an algebraic equation for \(G(x)\).

Frequently Asked Questions

How do I solve a second-order recurrence relation with this calculator?

Choose Order 2, enter p and q (and optionally c), then provide a_0 and a_1. The solver uses the characteristic equation to find a closed-form solution and also generates a term table up to your chosen n.

What is the characteristic equation for a_n = p a_(n-1) + q a_(n-2)?

Assuming a solution of the form a_n = r^n leads to the characteristic equation r^2 - p r - q = 0. The roots determine whether the closed form uses two exponentials, a repeated-root form, or a real sinusoidal form for complex roots.

What does the constant term c do in a recurrence relation?

A nonzero c makes the recurrence non-homogeneous, so the solution is the sum of a homogeneous solution and a particular solution. Depending on the coefficients, the particular solution may be constant, linear, or quadratic.

Can this tool solve the Fibonacci recurrence?

Yes. Use the Fibonacci preset (or set p = 1, q = 1 with a_0 = 0 and a_1 = 1) to generate Fibonacci terms and the closed-form expression derived from the characteristic roots.

Rate this calculator

Frequently Asked Questions

Questions related to this topic