Tiles Combinatorics I have the following question:
Let there be a road of length $n$.
there are 3 types of tiles: of lengths 1,2,3.
We'll define  $a(n)$ as the number of roads of $n$ tiles where a tile of length 1 and a tile of length 2 can not be adjacent.
I need to find a recurrence relation for $a(n)$.
I've manually calculated $a(n)$ for $0\leq n \leq6$ and I got $a(0)=1, a(1)=1, a(2)=2, a(3)=2, a(4)=4, a(5)=6, a(6)=9$, but I can't find the general relation.
Thanks for the help.
 A: If the first tile is a $3$, we can count the tilings of the remainder by $a(n-3)$.
If the first tile is a $1$, then either (1) the tiling is all $1$'s, or (2) the tiling continues with some quantity of $1$'s, then a $3$, then any valid tiling of the remainder.  Hence we get $1+a(n-4)+a(n-5)+a(n-6)+\cdots$.
If the first tile is a $2$, then either (1) the tiling is all $2$'s, or (2) the tiling continues with some quantity of $2$'s, then a $3$, then any valid tiling of the remainder.  Hence we get $\delta(n)+a(n-5)+a(n-7)+a(n-9)+\cdots$. (where $\delta(n)$ is $1$ if $n$ is even, and $0$ otherwise).
Hence, the desired recurrence relation is found by adding these three: 
$$a(n)=1+\delta(n)+a(n-3)+a(n-4)+2a(n-5)+a(n-6)+2a(n-7)+a(n-8)+\cdots$$
Luckily we can simplify this.  We have $\delta(n)=\delta(n-2)$.  We write
$$a(n-2)=1+\delta(n-2)+a(n-5)+a(n-6)+2a(n-7)+a(n-8)+2a(n-9)+\cdots$$
Subtracting, lots of stuff cancels, and we get $$a(n)-a(n-2)=a(n-3)+a(n-4)+a(n-5)$$
Rearranging, we get the lovely fifth-order recurrence $$\color{red}{a(n)=a(n-2)+a(n-3)+a(n-4)+a(n-5)}$$
I wish I knew a combinatorial way of getting that recurrence directly, rather than algebraically by subtracting sums.
A: disclaimer This is too long to be a comment and can be viewed as a partial answer; as I can't finish it yet, but it may help someone else, I provide with what I have so far.
Let me define 3 sequences with easier to find recurrence relations:
$u(n) $ gives the number of roads of length $n $ that end with a tile of length $1$;
$d(n) $ gives the number of roads of length $n $ that end with a tile of length $2$;
$t(n) $ gives the number of roads of length $n $ that end with a tile of length  $3$.
All those roads are restricted to the condition imposed by the OP: no 1-tile is adjacent to a 2-tile.
The following should be immediate:
$$a(n) = u(n) + d(n) + t(n)\\
u(n) = u(n-1) + t(n-1)\\
d(n) = d(n-2) + t(n-2)\\
t(n) = u(n-3) + d(n-3) + t(n-3) $$
Also we have that $u,d,t$ are $0$ if $n <0$ and $u(0) = d(0) = t(0) = 1$ just so the relations work fine from the get go.
