My combinatorics textbook has a problem:
Let there be $a_n$ the number of possible series of length $n$, such that the members of the series belong to the set $\{1,2,3,4,5,6,7,8\}$. The conditions of the series: even numbers cannot be next to each other. For example if $n=5$ the series $(1,1,2,6,3)$ is not permitted because $2$ is next to $6$. $(1,1,2,2,3)$ is not permitted as well because $2$ is next to $2$.
I need to find the recurrence relation. What I've come up so far with is the following: $$a_n=4a_{n-1}+4^2a_{n-2}$$ My thinking is: if the first number is odd (there can be 4 such numbers) then we're fine and we can proceed to solve $n-1$ space. If the first number is even (can be 4 such numbers) then the next has to be odd (4 possible numbers).
Interestingly, other than membership in { 1, 2, 3, 4, 5, 6, 7, 8 }, this recurrence itself generates a sequence with no two consecutive even numbers - for any initial pair ($a_0$,$a_1$) - (I leave the proof to you).