In Recurrence Relations we set up recurrences and solved simple first-order ones by unrolling. Unrolling breaks down for something like an = an−1 + 2an−2: each term depends on two earlier ones, and the expansion branches out of control. Fortunately, the most common family of recurrences, linear recurrences with constant coefficients, has a complete recipe that turns any such recurrence into a closed formula.
The idea is to guess that the solution looks like rn for some number r, find which r work by solving an ordinary polynomial equation, and combine those answers to fit the initial conditions. This chapter gives the method, explains why it works, and handles repeated roots and non-homogeneous terms, which is exactly the level asked in university exams and GATE.
A linear homogeneous recurrence of order k with constant coefficients has the form an = c1an−1 + c2an−2 + … + ckan−k, where c1, …, ck are constants and ck ≠ 0. Its characteristic equation is rk − c1rk−1 − c2rk−2 − … − ck = 0.
Every closed form in this chapter was derived by hand, then confirmed with SymPy's rsolve and by computing the first terms directly from the recurrence.
Where the Characteristic Equation Comes From
Try an = rn (with r ≠ 0) in an = c1an−1 + c2an−2:
rn = c1rn−1 + c2rn−2. Divide by rn−2: r2 = c1r + c2, i.e. r2 − c1r − c2 = 0.
So rn is a solution exactly when r is a root of this quadratic. The quadratic is the characteristic equation; its roots are the characteristic roots.
The second key fact is linearity: if sn and tn both satisfy a homogeneous linear recurrence, so does α sn + β tn for any constants α, β. (Substitute and collect terms: each side is just α times the s-equation plus β times the t-equation.) So once we have one solution rn per root, we can combine them.
Writing the characteristic equation is mechanical: replace an−j by rk−j. For example an = 6an−1 − 11an−2 + 6an−3 gives r3 − 6r2 + 11r − 6 = 0.
Case 1: Distinct Roots
Theorem. If r2 − c1r − c2 = 0 has two distinct roots r1 and r2, then a sequence satisfies an = c1an−1 + c2an−2 if and only if an = α1r1n + α2r2n for some constants α1, α2.
Proof.
Every such combination is a solution. Each rin is a solution because ri is a root, and linear combinations of solutions are solutions.
Every solution has this form. Let an be any solution. Choose α1, α2 to match the first two terms: α1 + α2 = a0 and α1r1 + α2r2 = a1. This linear system has determinant r2 − r1 ≠ 0, so it has a (unique) solution. Now an and bn = α1r1n + α2r2n satisfy the same recurrence and agree at n = 0 and n = 1. By strong induction they agree for every n, since each later term is determined by the two before it. ∎
The four-step recipe
Write the characteristic equation.
Find its roots.
Write the general solution with unknown constants.
Use the initial conditions to find the constants.
Worked example 1
Solve an = an−1 + 2an−2, with a0 = 2, a1 = 7.
r2 − r − 2 = 0.
(r − 2)(r + 1) = 0, so r = 2 and r = −1.
an = α12n + α2(−1)n.
n = 0: α1 + α2 = 2. n = 1: 2α1 − α2 = 7. Adding: 3α1 = 9, so α1 = 3 and α2 = −1.
an = 3 × 2n − (−1)n. Check: a2 = 7 + 4 = 11 from the recurrence, and 12 − 1 = 11 from the formula.
Worked example 2: Fibonacci numbers (Binet's formula)
Solve Fn = Fn−1 + Fn−2, F0 = 0, F1 = 1.
r2 − r − 1 = 0, so r = (1 ± √5)/2. Call them φ = (1 + √5)/2 ≈ 1.618 (the golden ratio) and ψ = (1 − √5)/2 ≈ −0.618.
Fn = α1φn + α2ψn.
n = 0: α1 + α2 = 0. n = 1: α1φ + α2ψ = 1. So α1(φ − ψ) = 1, and φ − ψ = √5, giving α1 = 1/√5, α2 = −1/√5.
Fn = (φn − ψn)/√5. Since |ψ| < 1, the ψn term shrinks quickly; in fact Fn is the integer nearest to φn/√5. This shows that Fibonacci numbers grow exponentially, like 1.618n, which is why naive recursive Fibonacci is so slow.
Higher order
The same theorem holds for order k: if the characteristic equation has k distinct roots r1, …, rk, then an = α1r1n + … + αkrkn, with k constants fixed by k initial conditions.
Example 3. an = 6an−1 − 11an−2 + 6an−3, a0 = 2, a1 = 5, a2 = 15.
r3 − 6r2 + 11r − 6 = (r − 1)(r − 2)(r − 3), roots 1, 2, 3.
an = α1 + α22n + α33n.
Equations: α1 + α2 + α3 = 2; α1 + 2α2 + 3α3 = 5; α1 + 4α2 + 9α3 = 15. Subtracting consecutive equations: α2 + 2α3 = 3 and 2α2 + 6α3 = 10, so α3 = 2, α2 = −1, α1 = 1.
an = 1 − 2n + 2 × 3n. Check a3: recurrence 6·15 − 11·5 + 6·2 = 47; formula 1 − 8 + 54 = 47.
Case 2: Repeated Roots
If the characteristic equation is (r − r0)2 = 0, the recipe above gives only one solution r0n, and α1r0n + α2r0n is really just one constant times r0n. It cannot fit two arbitrary initial conditions. The fix is a second solution, n r0n.
Theorem. If r2 − c1r − c2 = 0 has a single repeated root r0, then every solution of an = c1an−1 + c2an−2 has the form an = (α1 + α2n) r0n.
Why n r0n works. A double root means r2 − c1r − c2 = (r − r0)2, so c1 = 2r0 and c2 = −r02. Then
c1(n − 1)r0n−1 + c2(n − 2)r0n−2 = r0n[2(n − 1) − (n − 2)] = n r0n. ✓
The constants are found from a0 = α1 and a1 = (α1 + α2)r0, which always has a solution because r0 ≠ 0 (as c2 ≠ 0). The same uniqueness argument as before completes the proof.
Worked example 4
Solve an = 6an−1 − 9an−2, a0 = 1, a1 = 6.
r2 − 6r + 9 = (r − 3)2 = 0: double root 3.
an = (α1 + α2n)3n.
a0 = α1 = 1. a1 = (1 + α2) × 3 = 6, so α2 = 1.
an = (n + 1)3n. Check: a2 = 6·6 − 9·1 = 27 = 3 × 9.
The general theorem
If the characteristic equation has distinct roots r1, …, rt with multiplicities m1, …, mt (m1 + … + mt = k), then every solution is an = ∑i=1t (αi,0 + αi,1n + … + αi,mi−1nmi−1) rin.
Example: roots 2, 2, 2, −1 (a triple and a single) give an = (α + βn + γn2)2n + δ(−1)n. There are always exactly k constants, one per initial condition.
A note on complex roots
Roots may be complex. The method still works, and for a real recurrence with real initial conditions the imaginary parts cancel. Example: an = −an−2, a0 = 0, a1 = 1 has r2 + 1 = 0, roots ±i, and solution an = (in − (−i)n)/(2i) = sin(nπ/2), the repeating sequence 0, 1, 0, −1, 0, 1, …. Exam questions rarely go further than this.
Non-Homogeneous Recurrences
A linear non-homogeneous recurrence with constant coefficients looks like
an = c1an−1 + … + ckan−k + F(n),
where F(n) is not identically zero (like the "+ 1" in Tower of Hanoi). Dropping F(n) gives the associated homogeneous recurrence.
Theorem. If pn is any one solution (a particular solution) of the non-homogeneous recurrence, then every solution has the form an = pn + hn, where hn is a solution of the associated homogeneous recurrence.
Proof. If an and pn both satisfy the non-homogeneous recurrence, subtract the two equations: the F(n) terms cancel, so an − pn satisfies the homogeneous one. Conversely, adding a homogeneous solution to pn keeps the equation true. ∎
So the method is: general homogeneous solution + one particular solution, then apply the initial conditions to the sum.
Guessing a particular solution
F(n) | Try pn = | If the base is a characteristic root of multiplicity m |
|---|---|---|
constant c | A | If 1 is a root: multiply by nm |
polynomial of degree d in n | Adnd + … + A1n + A0 | If 1 is a root: multiply by nm |
c × sn | A sn | If s is a root: A nm sn |
(polynomial of degree d) × sn | (Adnd + … + A0) sn | If s is a root: multiply by nm |
The extra factor nm is needed because when s is already a root, A sn solves the homogeneous recurrence and gives 0 on the left, so it can never produce F(n). This "resonant" case is the most common GATE trap.
Worked example 5: constant forcing (Tower of Hanoi)
Solve Hn = 2Hn−1 + 1, H1 = 1.
Homogeneous: r = 2, so hn = α2n.
Particular: F = 1 is constant and 1 is not a root, so try pn = A: A = 2A + 1 gives A = −1.
General: Hn = α2n − 1. H1 = 2α − 1 = 1 gives α = 1.
Hn = 2n − 1, matching what unrolling gave in Recurrence Relations.
Worked example 6: exponential forcing
Solve an = 3an−1 + 2n, a0 = 0.
Homogeneous: hn = α3n.
Particular: 2 is not a root, try A2n: A2n = 3A2n−1 + 2n. Divide by 2n−1: 2A = 3A + 2, so A = −2.
General: an = α3n − 2 × 2n. a0 = α − 2 = 0, so α = 2.
an = 2 × 3n − 2n+1. Check: a1 = 3·0 + 2 = 2 and 6 − 4 = 2.
Worked example 7: the resonant case
Solve an = 2an−1 + 2n, a0 = 1.
Homogeneous: hn = α2n. Here s = 2 is a root (multiplicity 1).
Trying A2n fails: A2n = 2A2n−1 + 2n gives A = A + 1, impossible.
Try An2n: An2n = 2A(n − 1)2n−1 + 2n. Divide by 2n: An = A(n − 1) + 1, so A = 1.
General: an = α2n + n2n. a0 = α = 1.
an = (n + 1)2n. Terms: 1, 4, 12, 32, 80.
Worked example 8: polynomial forcing
Solve an = 3an−1 + 4n, a0 = 1.
Homogeneous: α3n. F(n) = 4n has degree 1 and 1 is not a root, so try pn = An + B.
An + B = 3(A(n − 1) + B) + 4n = (3A + 4)n + (3B − 3A). Matching coefficients: A = 3A + 4 gives A = −2; B = 3B − 3A gives 2B = 3A = −6, so B = −3.
General: an = α3n − 2n − 3. a0 = α − 3 = 1, so α = 4.
an = 4 × 3n − 2n − 3. Check: a1 = 3 + 4 = 7 and 12 − 2 − 3 = 7.
Worked example 9: decimal strings with an even number of 0s
From Recurrence Relations: an = 8an−1 + 10n−1, a1 = 9.
Homogeneous: α8n. Particular: 10n−1 = (1/10)10n and 10 is not a root, so try A10n: A10n = 8A10n−1 + 10n−1. Divide by 10n−1: 10A = 8A + 1, A = 1/2.
a1 = 8α + 5 = 9, so α = 1/2.
an = (8n + 10n)/2. Check: a2 = (64 + 100)/2 = 82.
Divide-and-Conquer by Change of Variable
T(n) = 2T(n/2) + n is not of the form above, but for n = 2k we can set bk = T(2k):
bk = 2bk−1 + 2k, b0 = T(1) = 1.
This is exactly worked example 7 with k in place of n, so bk = (k + 1)2k. Going back with k = log2 n: T(n) = n(log2 n + 1) = n log2 n + n, the merge sort bound from Recurrence Relations, now derived systematically.
Checking with Code
Always verify a closed form by computing the first few terms directly. The program below iterates each recurrence and compares with the formula found above.
def iterate(coeffs, initial, forcing, count):
"""a(n) = c1*a(n-1) + ... + ck*a(n-k) + forcing(n); returns a(0..count-1)."""
a = list(initial)
for n in range(len(a), count):
a.append(sum(c * a[n - 1 - i] for i, c in enumerate(coeffs)) + forcing(n))
return a
checks = [
("a(n) = a(n-1) + 2a(n-2)",
iterate([1, 2], [2, 7], lambda n: 0, 10),
lambda n: 3 * 2**n - (-1)**n),
("a(n) = 6a(n-1) - 9a(n-2)",
iterate([6, -9], [1, 6], lambda n: 0, 10),
lambda n: (n + 1) * 3**n),
("a(n) = 6a(n-1) - 11a(n-2) + 6a(n-3)",
iterate([6, -11, 6], [2, 5, 15], lambda n: 0, 10),
lambda n: 1 - 2**n + 2 * 3**n),
("a(n) = 3a(n-1) + 2^n",
iterate([3], [0], lambda n: 2**n, 10),
lambda n: 2 * 3**n - 2**(n + 1)),
("a(n) = 2a(n-1) + 2^n",
iterate([2], [1], lambda n: 2**n, 10),
lambda n: (n + 1) * 2**n),
]
for name, seq, closed in checks:
ok = all(seq[n] == closed(n) for n in range(10))
print(f"{name:38s} first terms {seq[:6]} closed form OK: {ok}")
Output:
a(n) = a(n-1) + 2a(n-2) first terms [2, 7, 11, 25, 47, 97] closed form OK: True
a(n) = 6a(n-1) - 9a(n-2) first terms [1, 6, 27, 108, 405, 1458] closed form OK: True
a(n) = 6a(n-1) - 11a(n-2) + 6a(n-3) first terms [2, 5, 15, 47, 147, 455] closed form OK: True
a(n) = 3a(n-1) + 2^n first terms [0, 2, 10, 38, 130, 422] closed form OK: True
a(n) = 2a(n-1) + 2^n first terms [1, 4, 12, 32, 80, 192] closed form OK: True
If you have the SymPy library installed, rsolve solves such recurrences symbolically:
from sympy import Function, rsolve, symbols
n = symbols("n", integer=True)
a = Function("a")
# a(n) = 3a(n-1) + 4n, a(0) = 1
print(rsolve(a(n) - 3*a(n - 1) - 4*n, a(n), {a(0): 1}))
Output:
4*3**n - 2*n - 3
This agrees with worked example 8. Use such tools to check your work, but learn the hand method: exams ask for the steps.
Common Mistakes
Sign errors in the characteristic equation. an = 5an−1 − 6an−2 gives r2 − 5r + 6 = 0 (move everything to one side), with roots 2 and 3, not −2 and −3.
Using α1r0n + α2r0n for a double root. The second term must be α2n r0n.
Applying initial conditions to the homogeneous part only. First add the particular solution, then solve for the constants.
Missing the resonant case. If F(n) = c sn and s is a characteristic root, the trial A sn fails; multiply by n (or nm).
Constant forcing when 1 is a root. For an = an−1 + 5, the root is 1, so try An, not A. The answer is an = a0 + 5n.
Initial conditions at the wrong index. If you are given a1 and a2, plug in n = 1 and n = 2, not 0 and 1.
Practice and GATE-Style Questions
Q1. Solve an = 5an−1 − 6an−2, a0 = 1, a1 = 0.
Roots 2 and 3: an = α2n + β3n. α + β = 1 and 2α + 3β = 0 give β = −2, α = 3. an = 3 × 2n − 2 × 3n. Check: a2 = 5·0 − 6·1 = −6 = 12 − 18.
Q2. What is the general form of the solution of an = 4an−1 − 4an−2? Find it for a0 = 1, a1 = 4.
r2 − 4r + 4 = (r − 2)2, double root 2: an = (α + βn)2n. α = 1 and 2(1 + β) = 4 give β = 1, so an = (n + 1)2n.
Q3. Solve an = an−1 + 2an−2, a0 = 0, a1 = 1.
Roots 2 and −1, as in example 1. α + β = 0 and 2α − β = 1 give α = 1/3, β = −1/3. an = (2n − (−1)n)/3: 0, 1, 1, 3, 5, 11, 21, 43, … (the Jacobsthal numbers).
Q4. What form of particular solution should be tried for an = 5an−1 − 6an−2 + 3n? Solve it with a0 = a1 = 0.
Roots are 2 and 3, and 3 is a root of multiplicity 1, so try pn = An3n. Substituting and dividing by 3n−2: 9An = 15A(n − 1) − 6A(n − 2) + 9, which simplifies to 0 = −3A + 9, so A = 3. General: α2n + β3n + n3n+1. From a0 = 0: α + β = 0; from a1 = 0: 2α + 3β + 9 = 0, so β = −9, α = 9. an = 9 × 2n + (n − 3)3n+1. Check: a2 = 0 − 0 + 9 = 9 and 36 − 27 = 9.
Q5. The characteristic roots of a linear homogeneous recurrence are 1, 1, 1, 4. Write the general solution.
The triple root 1 contributes (α + βn + γn2)1n and the root 4 contributes δ4n: an = α + βn + γn2 + δ4n, with four constants for a fourth-order recurrence.
Q6. Interview: how can Fn (Fibonacci) be computed in O(log n) arithmetic operations, and why not just use Binet's formula?
Use the matrix identity [[1, 1], [1, 0]]n = [[Fn+1, Fn], [Fn, Fn−1]] with fast exponentiation by squaring: O(log n) 2×2 matrix multiplications, all in exact integers (or mod m). Binet's formula needs √5 and powers of irrational numbers; with floating point it loses precision after about n = 70, so it is good for analysis but not for exact computation.
Summary
For an = c1an−1 + … + ckan−k, solve the characteristic equation rk − c1rk−1 − … − ck = 0.
Distinct roots: an = ∑ αirin. A root of multiplicity m contributes (α0 + α1n + … + αm−1nm−1)rn.
The k constants come from the k initial conditions; the proof rests on linearity plus uniqueness by induction.
Non-homogeneous: an = (homogeneous general solution) + (one particular solution). Guess the particular solution from the shape of F(n); multiply by nm if its base is a root of multiplicity m.
Divide-and-conquer recurrences become linear ones after substituting n = 2k.
Guess rn, solve a polynomial, combine the roots, fit the initial conditions. That four-step recipe solves every linear recurrence with constant coefficients.