Recurrence Relation Solver | Closed-Form Solution & Sequence Generator
Solve second-order linear homogeneous recurrence relations aₙ = p·aₙ₋₁ + q·aₙ₋₂ with initial conditions. Finds the characteristic equation, analyzes roots (distinct real, repeated, complex conjugate), builds the closed-form general solution, and generates the first N terms.
aₙ = p·aₙ₋₁ + q·aₙ₋₂ | a₀ = 0, a₁ = 1
What Is the Recurrence Relation Solver | Closed-Form Solution & Sequence Generator?
A linear recurrence relation defines each term of a sequence from previous terms using fixed coefficients. Second-order recurrences (like the Fibonacci sequence aₙ = aₙ₋₁ + aₙ₋₂) are the most common. The characteristic equation method finds a closed-form (non-recursive) formula by solving the quadratic r²−pr−q=0. The nature of the roots — distinct real, repeated, or complex conjugates — determines the form of the general solution, whose constants A and B are fixed by the initial conditions a₀ and a₁.
Formula
aₙ = p·aₙ₋₁ + q·aₙ₋₂
Characteristic equation: r² − p·r − q = 0
Δ = p² + 4q
Δ > 0: aₙ = A·r₁ⁿ + B·r₂ⁿ (distinct real roots)
Δ = 0: aₙ = (A + Bn)·rⁿ (repeated root)
Δ < 0: aₙ = Rⁿ(A·cos(nθ) + B·sin(nθ)) (complex)
How to Use
- 1
Enter p (coefficient of aₙ₋₁) and q (coefficient of aₙ₋₂)
- 2
Enter initial conditions a₀ and a₁
- 3
Set N to how many terms to generate (up to 30)
- 4
Or load a preset: Fibonacci, Lucas, Pell, complex roots, or repeated root
- 5
Click Solve
- 6
Read characteristic roots, discriminant type, and closed-form general solution
Enter the coefficients p (coefficient of aₙ₋₁) and q (coefficient of aₙ₋₂), plus the initial values a₀ and a₁. Set N to the number of terms you want to generate. Click Solve to see the characteristic equation, roots, closed-form formula, and the sequence table.
Example Calculation
Example: Fibonacci — aₙ = aₙ₋₁ + aₙ₋₂, a₀=0, a₁=1
p=1, q=1 → r² − r − 1 = 0
Roots: r = (1 ± √5)/2 → φ ≈ 1.618, ψ ≈ −0.618
General: aₙ = A·φⁿ + B·ψⁿ
Binet's formula: aₙ = (φⁿ − ψⁿ) / √5
Frequently Asked Questions
What is the characteristic equation?
For the recurrence aₙ = p·aₙ₋₁ + q·aₙ₋₂, we assume a solution of the form aₙ = rⁿ. Substituting and dividing by rⁿ⁻² gives the characteristic equation r² − p·r − q = 0. Its roots determine all solutions.
What happens with complex conjugate roots?
When the discriminant p²+4q < 0, the characteristic roots are complex conjugates r = α ± βi. Writing in polar form R·e^(±iθ) where R=√(α²+β²) and θ=arctan(β/α), the general real solution is aₙ = Rⁿ(A·cos(nθ) + B·sin(nθ)). This produces oscillating sequences.
What is the repeated root case?
When the discriminant equals zero, both roots equal r = p/2. The correct second solution in this case is n·rⁿ, giving the general solution aₙ = (A + B·n)·rⁿ, since A·rⁿ and B·rⁿ would be linearly dependent.
Can this solver handle non-homogeneous recurrences?
This calculator handles homogeneous second-order linear recurrences aₙ = p·aₙ₋₁ + q·aₙ₋₂. Non-homogeneous recurrences (with a forcing term like f(n)) require finding a particular solution, which depends on the form of f(n).
You Might Also Like
Explore 360+ Free Calculators
From math and science to finance and everyday life — all free, no account needed.