Finding characteristic equation of problem and solve recurrence relation 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,
 A: As @Austin pointed out in comments, the correct solution comes down to a case-by-case analysis.  To make things a little bit easier, we'll let $o(n)$ be the number of suitable sequences of length $n$ ending with an odd number, and $e(n)$ be the number of suitable sequences of length $n$ ending with an even number.  Obviously $a(n) = o(n)+e(n)$; also, of course, if a sequence is suitable (has no two even numbers adjacent), then any subsequence is also suitable - this is the key point that lets us write our formulas for suitable sequences of length $n$ in terms of the sequences of length $n-1$.


*

*If the last term of a sequence is odd, the rest of the terms can be anything; how does this let you express $o(n)$ in terms of $a(n-1)$?

*If the last term of a sequence is even, what does this say about the last term of the rest of the sequence (the $n-1$st term)? How does this let you express $e(n)$ in terms of $o(n-1)$ and $e(n-1)$?

*Can you use what you used in (1) (and your base knowledge that $a(n)=o(n)+e(n)$) to rewrite the formula you found in (2) and express $e(n)$ in terms of only the sequence $a$?

*Finally, add the formulas from (1) and (3) together; this should give you your expression for $a(n)$.  Once you have this, if you need more help with the characteristic equation, I'd suggest either editing your question to reflect the updated knowledge or asking a new one to cover that specific part of the Q.

A: Remark: I read the question incorrectly. This post enumerates the number of sequences in which no two consecutive entries are the same.
If you have a valid sequence of length $n-1$, how can you add a number to the end to extend it to a valid sequence of length $n$?
Since the smaller sequence is assumed to be valid, you know illegal configurations in it (i.e. no consecutive entries with the same number). All that's left is to add an element to the end. We have 7 choices for this, since we cannot choose whatever number is on the end of the shorter sequence. So, we get the recursion
$$
a(n) = 7a(n-1),
$$
with initial condition $a(1) = 8$.
Think about the first few terms of $a(n)$: 8, $8 \cdot 7$, $8 \cdot 7^2$, $8 \cdot 7^3$, $\dots$.
From this, we can conclude that
$$
a(n) = 8 \cdot 7^{n-1}.
$$
A: To begin with, the recurrence relation that you give is incorrect. Now, consider a valid string of length $n$:
$$b_1b_2\ldots b_{n-1}b_n.$$
There are two cases:
If $b_n$ is odd: then any legal string $b_1b_2\ldots b_{n-1}$ can precede $b_n$. Since There are $a(n-1)$ of these strings  the amount of valid strings of length $n$ with $b_n$ odd is $a(n-1)\cdot 4$.
If $b_n$ is even: then $b_{n-1}$ is odd and $b_n$ is even. Any legal string of length $n-2$ can precede $b_{n-1}b_n$. Since there are $a(n-2)$ of this these strings, the number of valid strings with length $n$ with the last digit even is $a(n-2)\cdot 4\cdot 4$.
Since the total amount of valid strings of length $n$ is the sum of the two quantities above, we get $$a(n)=4a(n-1)+16a(n-2).$$
For the initial conditions note that $a(1)=8$ and $a(2)=48$.
Secondly, given a recurrence relation
$$
a(n+k)+c_1a(n+k-1)+\ldots+c_ka(n)=f(n),\; k>1
$$
of order $k$, with $c_i$ constants, you can find the characteristic equation of the associated homogeneous recurrence relation: $$a(n+k)+c_1a(n+k-1)+\ldots+c_ka(n)=0,$$
namely $$x^{k}+\sum_{i=1}^k c_ix^{k-i}=0.$$
This can be useful to you http://applied-discrete-structures.wiki.uml.edu/Chapter+8 .
