Solving Linear Recurrence Relations
1. Linear Homogeneous Recurrence Relations with Con-
stant Coefficients
A recurrence relation is said to be linear homogeneous with constant coefficients if it
is of the form:
an = c1 an−1 + c2 an−2 + · · · + ck an−k
where c1 , . . . , ck are constants and the right-hand side involves only the previous terms (no
constant or non-zero function).
Steps to Solve
Step 1. Write the recurrence in standard form.
Step 2. Form the characteristic (auxiliary) equation by replacing an with rn . The result
is:
rk − c1 rk−1 − c2 rk−2 − · · · − ck = 0
Step 3. Solve the characteristic equation to find the roots.
• If all roots are real and distinct: General solution is
an = A1 r1n + A2 r2n + · · · + Ak rkn
• If there are repeated roots: For a root r with multiplicity m, include terms:
(B0 + B1 n + · · · + Bm−1 nm−1 )rn
• If complex roots exist: Use Euler’s formula to express in real form.
Step 4. Use initial conditions to solve for constants A1 , A2 , . . .
1
Example
Solve:
an = 5an−1 − 6an−2 , a0 = 0, a1 = 1
Solution: Characteristic equation:
r2 − 5r + 6 = 0 ⇒ (r − 2)(r − 3) = 0 ⇒ r = 2, 3
General solution:
an = A · 2n + B · 3n
Using initial conditions:
a0 = A + B = 0a1 = 2A + 3B = 1 ⇒ A = −1, B = 1
Final answer:
an = −2n + 3n
2
2. Linear Non-Homogeneous Recurrence Relations
These take the form:
an = c1 an−1 + c2 an−2 + · · · + ck an−k + f (n)
Where f (n) ̸= 0 is a known function.
Solution Structure
an = a(h) (p)
n + an
Where:
(h)
• an : General solution to the associated homogeneous equation.
(p)
• an : Particular solution to the non-homogeneous equation.
Steps to Solve
(h)
Step 1. Solve the associated homogeneous recurrence (as above) to get an .
(p)
Step 2. Guess a particular solution an depending on the form of f (n):
(p)
• If f (n) is a polynomial of degree d: Try an = P (n) (a polynomial of degree d).
(p)
• If f (n) = c · rn : Try an = Arn
(p)
• If f (n) = c · nk rn : Try an = (A0 + A1 n + · · · + Ak nk )rn
If the guess overlaps with the homogeneous solution, multiply by n, n2 , etc., until it
doesn’t.
(p)
Step 3. Plug into the recurrence to solve for coefficients in an .
(h) (p)
Step 4. Add both parts: an = an + an
Step 5. Use initial conditions to solve for constants.
3
Example
Solve:
an = 2an−1 − an−2 + 3, a0 = 1, a1 = 3
Step 1: Solve homogeneous equation:
an = 2an−1 − an−2 ⇒ r2 − 2r + 1 = 0 ⇒ (r − 1)2 = 0
General solution:
a(h)
n = A + Bn
(p)
Step 2: Particular solution (constant RHS = 3): Try an = C
Plug into full recurrence:
C = 2C − C + 3 ⇒ C = C + 3 ⇒ Contradiction ⇒ Try linear: a(p)
n = Cn
Plug in:
Cn = 2C(n − 1) − C(n − 2) + 3 = 2C(n − 1) − C(n − 2) + 3 = 2C(n − 1) − C(n − 2) + 3
(p)
Try quadratic: an = Dn2
Eventually, find:
a(p)
n = 3n ⇒ (can verify by substitution)
Step 3: Final solution:
an = A + Bn + 3n = A + (B + 3)n
Use initial conditions:
a0 = A = 1a1 = A + (B + 3) = 3 ⇒ 1 + B + 3 = 3 ⇒ B = −1
Final answer:
an = 1 + 2n
