I have a homework assignment to find the characteristic equation of the set which a(n) = the number of sequences of length n which can be build from ${1,2,3...8}$ but you can't have two even numbers adjacent to each other, for example (1,2,2,3) is not legal.
I came up with the recurrence $a(n) = 8a(n-1) -16$ which I hope is correct.
But how can I find the characteristic equation of this recurrence and then use it to solve the recurrence?
P.S.
I don't know Taylor series and we have not learned it yet so the solution should not include it ( I saw some solutions on the Internet using it)
Thanks,