Let's say you have three different kinds of tiles. All one unit in length. We'll call them Red(R), Green(G), and Blue(B). Create a recursive formula to tile an n unit long walkway where the only condition is that you can't have two reds or three green tiles next to each other.
I tried this problem by thinking about it from the end of the sequence.
Define $R_n$ be the number of ways that you can have a length $n$ walkway with red at the end.
Define $G_n$ be the number of ways that you can have a length $n$ walkway with green at the end.
Define $B_n$ be the number of ways that you can have a length $n$ walkway with blue at the end.
Define $W_n$ be the number of ways that you can have a length $n$ walkway.
$$R_n = B_{n-1} + G_{n-1}$$
$$G_n = B_{n-1} + R_{n-1} + B_{n-2}+R_{n-2}$$
$$B_n = W{n-1}$$
However, when you put this together, you have an extra $R_{n-2}$ that I can't figure out how to put in terms of $W$. Where am I going wrong?
$W_n = 2W_{n-1} + W_{n-2} + W_{n-3} + R_{n-2}$