[Discrete] Third Order Linear Recurrence Relation (finding an equation in terms of n only)
Not sure if the title is clear but I have a third order linear recurrence relation of the form:
A_n = A_n-3 + A_n-2 + A_n-1
(Basically, the n'th term is the sum of the 3 previous terms). I want to show that for n>1, A_n <= 2^(n-1). I have a good idea of how to do this for second order but I'm completely for third order. I found a method online that uses eigenvalues/vectors but I doubt it's the way I'm suppose to use here. If this were a second order relation, I'd find the roots and the characteristic equitation (I'm not taking this course in english so this might not be the actual name) and then prove the inequality by induction.
My problem is that I have no clue on how to find the equation to find A_n in terms of n only (not using recurrence). If someone could point me in the right direction for that I'm pretty sure I can prove the inequality.
Thanks!
Posted Dec 2, 2012, 8:23 PM UTC