Solving a Recurrence Relation
Find the solution to the recurrence relation,
a_n = 6a_(n-1) + 11a_(n-2) – 6a_(n-3), given a_0 = 20, a_1 = 5, a_2 = 15
Assuming a solution of the form a_n = c.r^n, then
a_(n-1) = c.r^(n-1), a_(n-2) = c.r^(n-2), a_(n-3) = c.r^(n-3)
Substituting for the above into the recurrence relation,
c.r^n = 6c.r^(n-1) + 11c.r^(n-2) – 6c.r^(n-3)
r^n = 6r^(n-1) + 11r^(n-2) – 6r^(n-3)
1 = 6r^(-1) + 11r^(-2) – 6r^(-3)
r^3 = 6r^(2) + 11r^(1) – 6
r^3 – 6r^2 – 11r + 6 = 0
Solving the cubic equation above would give three root values for r, and a recurrence relation of the form
a_n = c1.r1^n + c2.r2^n + c3.r3^n
where the three constants, c1, c2, c3 are determined from the initial values for a_0, a_1 and a_2.
The solutions for our cubic equation, r^3 – 6r^2 – 11r + 6 = 0, is
r1 = -1.8256153, r2 = 0.4453157. r3 = 7.3802996
Our recurrence relation now becomes,
a_n = c1*(-1.8256153)^n + c2*(0.4453157)^n + c3*(7.3802996)^n
Using the initial values for a_0, a_1 and a_2, we get
a_0 = 20 = c1*(-1.8256153)^0 + c2*(0.4453157)^0 + c3*(7.3802996)^0
a_1 = 5 = c1*(-1.8256153)^1 + c2*(0.4453157)^1 + c3*(7.3802996)^1
a_2 = 15 = c1*(-1.8256153)^2 + c2*(0.4453157)^2 + c3*(7.3802996)^2
20 = c1 + c2 + c3
5 = c1*(-1.8256153 + c2*(0.4453157) + c3*(7.3802996)
15 = c1*(-1.8256153)^2 + c2*(0.4453157)^2 + c3*(7.3802996)^2
The last three simultaneous equations can now be solved for c1, c2 and c3.
The values are: c1 = 1.990012, c2 = 17.9216148, c3 = 0.08837315
Our recurrence relation finally becomes,
a_n = 1.990012*(-1.8256153)^n + 17.9216148*(0.4453157)^n + 0.08837315*(7.3802996)^n
Check
Substituting for n = 0, 1, 2 in the final expression gives results for the initial values of a_0, a_1, a_2.
n = 0: 19.99999995 (a_0 = 20)
n = 1: 5.000000410 (a_1 = 5)
n = 2: 15.00000017 (a_2 = 15)