Register to reply

Solving a recurrence relation

by silvermane
Tags: combinatorics, recurrence relations
Share this thread:
silvermane
#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
'Smart material' chin strap harvests energy from chewing
King Richard III died painfully on battlefield
Capturing ancient Maya sites from both a rat's and a 'bat's eye view'
JSuarez
#2
Mar23-10, 01:07 PM
P: 402
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
#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
#4
Mar23-10, 08:28 PM
P: 402
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