Solving a recurrence relation


by silvermane
Tags: combinatorics, recurrence relations
silvermane
silvermane is offline
#1
Mar23-10, 10:39 AM
PF Gold
silvermane's Avatar
P: 117
1. The problem statement, all variables and given/known data

Solve the recurrence relation
an = 5an−1 − 3an−2 − 9an−3 for n ≥ 3
with initial values a0 = 0, a1 = 11, and a2 = 34.

2. Relevant equations

its given lol

3. The attempt at a solution

I found that the characteristic equation for this rr is x3 - 5x2 + 3x + 9 and found that the characteristic roots are 3, 3, -1...because we have 2 indistinct roots, I multiplied one of the 3 terms by n to get

an = r3n + sn3n - t
and so plugging back into the give rr we have

r3n + sn3n - t = 5(r3n-1 + s(n-1)3n-1 - t) - 3(r3n-2 + s(n-2)3n-2 - t) - 9(r3n-3 + s(n-3)3n-3 - t)

I'm thinking that in order to solve this, we're going to have to set this up as a system of equations, but I'm not sure how to do that with what I have. Any hints/tips/ suggestions on where to go next would be very helpful.
Phys.Org News Partner Science news on Phys.org
Better thermal-imaging lens from waste sulfur
Hackathon team's GoogolPlex gives Siri extra powers
Bright points in Sun's atmosphere mark patterns deep in its interior
JSuarez
JSuarez is offline
#2
Mar23-10, 01:07 PM
P: 403
an = r3n + sn3n - t
Given this, then r,s and t must be equal to what for you to have a0 = 0, a1 = 11, and a2 = 34? This above expression must be valid for all n, after all, not only for [itex]n\geq 3[/itex].

By the way, you claim that one of your roots is -1; are you sure that the above is entirely correct?
silvermane
silvermane is offline
#3
Mar23-10, 08:23 PM
PF Gold
silvermane's Avatar
P: 117
Quote Quote by JSuarez View Post
By the way, you claim that one of your roots is -1; are you sure that the above is entirely correct?
To see if a root exists, we would plug it into the characteristic equation. When -1 is plugged into the equation, we obtain 0, therefore it is a root of the equation. Corollary, I saw that 3 was a root in same fashion, and found that it was a root of multiplicity 2 when I plugged it into the derivative. This was how we were showed to find the roots.

JSuarez
JSuarez is offline
#4
Mar23-10, 08:28 PM
P: 403

Solving a recurrence relation


I don't have any doubt that -1 is a root: it is. But, if 3 is a root (forget the multiplicity for a moment) and it gives rise to a term 3n in the solution, then what would be the term corresponding to -1?


Register to reply

Related Discussions
Recurrence Relation Calculus & Beyond Homework 0
Recurrence Relation Help Calculus & Beyond Homework 5
Recurrence relation General Math 7
Recurrence Relation General Math 11
Recurrence Relation General Math 5