<s>[INST] recurrence initial conditions 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$?
 [/INST] 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}
</s>