STEP-BY-STEP LESSON · §5.8
Second-Order Linear Homogeneous Recurrence Relations with Constant Coefficients
Solve a simple second-order recurrence with distinct characteristic roots.
Before you begin
Defining Sequences Recursively
A recurrence relates terms but does not by itself specify where to start.
a_0=2
The rule a_n=2a_(n−1)+1 means: take the previous value, double it, and add 1.
a_n=2a_(n−1)+1, n≥1
Solving Recurrence Relations by Iteration
Replace a_(n−1) using the same rule until the repeated contribution becomes visible.
a_n=a_(n−1)+3=a_(n−2)+6
From n down to 0 there are exactly n steps, hence n threes.
a_n=a_0+3n
Symbols
- r
- trial exponential base
- C,D
- constants determined by initial values
- A,B
- fixed real recurrence coefficients; n is an integer at least 2
Definitions and notation for this topic
Recursive and explicit sequence formulas
A recursive rule defines later terms using earlier ones and initial values. An explicit formula gives a_n directly in terms of n and fixed parameters.
Check an explicit candidate against both the recurrence and the initial values. Matching a few terms alone does not prove the formulas agree for every index.
Separate glossary example
a₀=3, a_n=a_(n−1)+2 for n≥1 describes the same sequence as a_n=3+2n for n≥0.
Characteristic equation for a second-order recurrence
r²−Ar−B=0
For a_n=Aa_(n−1)+Ba_(n−2), n≥2, with fixed real A,B and B≠0, substitution of r^n leads to this characteristic equation.
For two distinct real roots r₁,r₂ use C r₁^n+D r₂^n. For a repeated nonzero real root r use (C+Dn)r^n. Determine C,D from two initial values; these displayed templates concern real roots.
Separate glossary example
a_n=3a_(n−1)−2a_(n−2) has roots 1 and 2, so a_n=C+D·2^n. With a₀=2,a₁=3, C=D=1.
Step by step
Step 1 / 6
Recognize the form
Each new term is a linear combination of the previous two with constant coefficients.
a_n=Aa_(n−1)+Ba_(n−2)
There is no separate forcing term, so the recurrence is homogeneous.
Worked example
a_0=2, a_1=5, a_n=5a_(n−1)−6a_(n−2).
- The equation r²−5r+6=0 factors as (r−2)(r−3)=0. The roots are 2 and 3.
- The initial values give C+D=2 and 2C+3D=5. Subtract twice the first equation from the second: D=1, then C=1.
- Verify the formula for every n≥2: 5·2^(n−1)−6·2^(n−2)=2^(n−2)(10−6)=2^n. Likewise, 5·3^(n−1)−6·3^(n−2)=3^(n−2)(15−6)=3^n. Adding these identities gives the original recurrence for 2^n+3^n.
- Thus a_n=2^n+3^n. At n=2 this is 13; the recurrence gives 5·5−6·2=13 too. The base values and recurrence determine all terms.
Optional self-check
What is the characteristic equation for a_n=3a_(n−1)+4a_(n−2)?
Show answer
r²−3r−4=0: move both terms to the left.