recurrence initial conditions

Question

I'm working on a homework assignment involving recursion and I'm having trouble finding an easy way to determine the initial conditions. Heres the problem:

We want to tile ann×1 strip with tiles of three types: 1×1 tiles that are dark-blue, light-blue,and red; 2×1 green tiles, and 3×1 sky-blue tiles. Now give a formula with initial conditions for the number of tilings, considering that blue tiles cannot be next to each other.

I can understand that the recurrence equation is:

$B_n = B_{n-1}+3B_{n-2}+2B_{n-3}+B_{n-4}+B_{n-5}$

And I've found initial conditions for

$B_0=1$ $B_1 = 3$ $B_2 = 6$ $B_3 = 17$

However, I found these but actually writing down all the possible combinations of tiles, but $B_4$ is a huge possible list. Is there some method of combinatorics or permutations I can use to find the initial conditions for $B_4$?

Answer 1

Wouldn't $B_3$ be $18$ and not $17$?

Answer 2

Let $a_n$ and $b_n$ the number of $n$-tilings that start with red or green, and blue, respectively. Also, let $c_n$ (your $B_n$) be the total number of $n$-tilings. Then $a_0=a_1=b_0=c_0=1$, $b_1=b_2=2$, $c_1=3$, and, by conditioning on the next tile, we see that \begin{align} a_n &= c_{n-1} + c_{n-2} &&\text{for $n \ge 2$}\\ b_n &= 2 a_{n-1} + a_{n-3} &&\text{for $n \ge 3$}\\ c_n &= a_n+b_n-[n=0] &&\text{for $n \ge 0$} \end{align} Hence \begin{align} c_n &= c_{n-1} + c_{n-2}+2 a_{n-1} + a_{n-3}\\ &=c_{n-1} + c_{n-2}+2 (c_{n-2} + c_{n-3}) + (c_{n-4} + c_{n-5})\\ &=c_{n-1} + 3c_{n-2}+2 c_{n-3} + c_{n-4} + c_{n-5}, \end{align} as you had claimed.

---

We can also obtain generating functions as follows. Let $A(z)=\sum_{n=0}^\infty a_n z^n$, $B(z)=\sum_{n=0}^\infty b_n z^n$, and $C(z)=\sum_{n=0}^\infty c_n z^n$. Then the recurrence relations imply \begin{align} A(z)-1 - z &=z (C(z)-1) + z^2 C(z) \\ B(z)-1 -2 z-2 z^2 &= 2z (A(z)-1-z) + z^3 A(z) \\ C(z) &= A(z)+B(z)-1 \end{align} Solving for $A(z)$, $B(z)$, and $C(z)$ yields \begin{align} A(z) &= \frac{1}{1 - z - 3 z^2 - 2 z^3 - z^4 - z^5}\\ B(z) &= \frac{1 + z - 3 z^2 - z^3 - z^4 - z^5}{1 - z - 3 z^2 - 2 z^3 - z^4 - z^5}\\ C(z) &= \frac{1 + 2 z + z^3}{1 - z - 3 z^2 - 2 z^3 - z^4 - z^5} \end{align} Notice that the (common) denominator implies that each sequence satisfies the order-5 recurrence $$f_n - f_{n-1} - 3 f_{n-2} - 2 f_{n-3} - f_{n-4} - f_{n-5} = 0,$$ as before. Expanding the series for $C(z)$ yields $$1 + 3 z + 6 z^2 + 18 z^3 + 43 z^4 + 113 z^5 + 287 z^6 + 736 z^7 + 1884 z^8 + 4822 z^9 + 12346 z^{10} + \dots .$$ In particular, $c_3 = 18$, which you could also have obtained directly from the recurrence relations as follows: \begin{align} a_2 &= c_1 + c_0 = 3 + 1 = 4\\ c_2 &= a_2 + b_2 = 4 + 2 = 6\\ a_3 &= c_2 + c_1 = 6 + 3 = 9\\ b_3 &= 2a_2 + a_0 = 2\cdot 4 + 1 = 9\\ c_3 &= a_3+b_3=9+9 = 18 \end{align}