Tile a 1 x n walkway with 4 different types of tiles... Suppose you are trying to tile a 1 x n walkway with 4 different types of tiles: a red 1 x 1 tile, a blue 1 x 1 tile, a white 1 x 1 tile, and a black 2 x 1 tile 
a. Set up and explain a recurrence relation for the number of different tilings for a sidewalk of length n. 
b. What is the solution of this recurrence relation? 
c. How long must the walkway be in order have more than 1000 different tiling possibilities? 
This is a problem on my test review and I have no idea how to approach it. We did a similar example in class but only using 1x1 tiles that were all the same (no separate tile colors or sizes). Any help/hints would be appreciated. Thanks in advance! 
My initial thought is something along the lines of finding all the ways to use the 1 x 1 tiles then multiplying that by 3 to consider each color variant (don't know how the 2x1 factors in to this though).
 A: Call the number of tilings of length $n$ $t_n$, then to get a tiling of length $n$, you take one of length $n - 1$ and add a red, a white or a blue tile (3 ways); add a black tile to one of length $n - 2$. I.e.:
$\begin{equation*}
  t_{n + 2}
    = 3 t_{n + 1} + t_n
\end{equation*}$
Directly we find $t_0 = 1$, $t_1 = 3$.
Define the generating function:
$\begin{equation*}
  T(z)
    = \sum_{n \ge 0} t_n z^n
\end{equation*}$
Take the recurrence, multiply by $z^n$ and sum over $n \ge 0$, recognize resulting sums:
$\begin{align*}
  \sum_{n \ge 0} t_{n + 2} z^n
    &= 3 \sum_{n \ge 0} t_{n + 1} z^n
         + \sum_{n \ge 0} t_n z^n \\
  \frac{T(z) - t_0 - t_1 z}{z^2}
    &= 3 \frac{A(z) - t_0}{z} + A(z)
\end{align*}$
Solve for $A(z)$, split into partial fractions:
$\begin{align*}
  T(z)
    &= \frac{1}{1 - 3 z - z^2} \\
    &= \frac{2 (\sqrt{13} + 3)}{\sqrt{13}} 
         \cdot \frac{1}{1 + \frac{2}{3 + \sqrt{13}} z}
         + \frac{2 (\sqrt{13} - 3)}{\sqrt{13}} 
              \cdot \frac{1}{1 + \frac{2}{3 - \sqrt{13}} z}
\end{align*}$
Need to extract the coefficients from these geometric series:
$\begin{equation*}
  [z^n] T(z)
    = \frac{2 (\sqrt{13} + 3)}{\sqrt{13}}
         \cdot \left( \frac{2}{3 + \sqrt{13}} \right)^n
        + \frac{2 (\sqrt{13} - 3)}{\sqrt{13}}
             \cdot \left( \frac{2}{3 - \sqrt{13}} \right)^n
\end{equation*}$
Note that:
$\begin{align*}
  \frac{2 (\sqrt{13} + 3)}{\sqrt{13}}
    &= 2.8321 \\
  \frac{2 (\sqrt{13} - 3)}{\sqrt{13}}
    &= 1.1679 \\
  \frac{2}{3 + \sqrt{13}}
    &= 0.30278 \\
  \frac{2}{3 - \sqrt{13}}
    &= 3.3028
\end{align*}$
Note that already by $n = 1$ the first term is less than 1, so a very good approximation is $t_n = 1.1679 \cdot 3.3028^n$. To get $t_n = 1000$, you need:
$\begin{align*}
   1000 &= 1.1679 \cdot 3.3028^n \\
   n    &= 5.65  
\end{align*}$
Thus you need at least length 6.
