Find the recurrence relation and initial conditions for the number of ways to tile a road of length $n$ cm, using blue, red and green tiles such that the length of each blue tile is 2 cm, green one is 1 cm, red one is 3 cm, and green & blue tiles must not be adjacent.
Hey all. So I defined $a_n$- The requested solution. $b_n$- number of ways such that the first tile is not blue. $c_n$- number of ways such that the first tile is not green. I would like to find the recurrence relation using these definitions, but am quite clueless on how to continue from here. Thanks in advance :)
Let $a_n$ denote the number of ways to tile a road of length $n$ cm. If $r_n$, $b_n$ and $g_n$ denotes the number of ways to tile the road of length $n$ cm starting with a red, blue and green tile respectively, then $$a_n=r_n+b_n+g_n.$$ Now if tiling starts with a red tile, then the remaining tiling is such that it is of length $n-3$ and no blue or green tiles are adjacent. So $$r_n=a_{n-3}.$$
If tiling starts with a green tile, then the second tile cannot be a blue tile so the remaining tiling is of length $n-1$ that starts either with a red or a green tile and therefore $$g_n=r_{n-1}+g_{n-1}=a_{n-4}+g_{n-1}=a_{n-4}+a_{n-5}+g_{n-2}.$$
If tiling starts with a blue tile, then the second tile cannot be a green tile so the remaining tiling is of length $n-2$ that starts either with a red or a blue tile and therefore $$b_n=r_{n-2}+b_{n-2}=a_{n-5}+b_{n-2}.$$ Hence $$a_n=a_{n-3}+a_{n-4}+2a_{n-5}+b_{n-2}+g_{n-2}=a_{n-3}+a_{n-4}+2a_{n-5}+a_{n-2}-r_{n-2}=a_{n-3}+a_{n-4}+2a_{n-5}+a_{n-2}-a_{n-5}=a_{n-2}+a_{n-3}+a_{n-4}+a_{n-5}.$$