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).
Suppose you have a tiling of length $n+2$. This can be built from:
Let $T_n$ be the number of different ways of tiling a $1\times n$ space. Then for $n\ge1$
$$T_{n+2}=T_{n+1}T_1+T_n=3T_{n+1}+T_n \tag{1}$$
and for the "base" cases: $T_1=3,\:T_2=10$. Then by (1)
$$\begin{array}{l} T_3=33 \\ T_4=109 \\ T_5=360 \\ T_6=1189 \end{array}$$
So the hallway must be at least six units long for 1000+ different tiling possibilities.
The recursion is Fibonacci-like and can be written in matrix form as:
$$\begin{bmatrix}T_{n+2}\\T_{n+1}\end{bmatrix}=\begin{bmatrix}3 & 1\\1 & 0\end{bmatrix}\begin{bmatrix}T_{n+1}\\T_{n}\end{bmatrix}$$
from which the characteristic equation is $(3-\lambda)(-\lambda)-1\times1=0 \implies \lambda^2-3\lambda-1=0$ which has solutions $\lambda=\frac{3\pm\sqrt{13}}{2}$
So we seek a formula for $T_n$ of the form $T_n=a\left(\frac{3+\sqrt{13}}{2}\right)^n+b\left(\frac{3-\sqrt{13}}{2}\right)^n$. Substituting for some values of $T_n$, e.g. $T_3,T_4$ to be safe, you can solve to get
$$T_n=\frac{1}{\sqrt{13}}\left\{\left(\frac{3+\sqrt{13}}{2}\right)^{n+1}-\left(\frac{3-\sqrt{13}}{2}\right)^{n+1}\right\}$$
It turns out that this formula works for $n=1,2$ as well even though the recursion didn't cover these cases. The formula can be proven by induction.
Appendix - Obtaining a Closed-Form Solution
In the formula $T_n=a\left(\frac{3+\sqrt{13}}{2}\right)^n+b\left(\frac{3-\sqrt{13}}{2}\right)^n$ let $a=a_1+a_2\sqrt{13},\:b=b_1+b_2\sqrt{13}$ (with $a_1,a_2,b_1,b_2$ all rational numbers). Then from $T_1=3,T_2=10$ we get:
$$\begin{align} T_1&=(a_1+a_2\sqrt{13})\left(\frac{3+\sqrt{13}}{2}\right)^1+(b_1+b_2\sqrt{13})\left(\frac{3-\sqrt{13}}{2}\right)^1&=3 \\ T_2&=(a_1+a_2\sqrt{13})\left(\frac{3+\sqrt{13}}{2}\right)^2+(b_1+b_2\sqrt{13})\left(\frac{3-\sqrt{13}}{2}\right)^2&=10 \end{align}$$
and from this (by equating rational multiples of $1,\sqrt{13}$) we obtain four simultaneous equations:
$$\begin{array}{rccccccccc} T_1[1]: & 3a_1 &+ &13a_2 &+ &3b_1 &- &13b_2 &= &6 \\ T_1[\sqrt{13}]: & a_1 &+ &3a_2 &- &b_1 &+ &3b_2 &= &0 \\ T_2[1]: & 11a_1 &+ &39a_2 &+ &11b_1 &- &39b_2 &= &20 \\ T_1[\sqrt{13}]: & 3a_1 &+ &11a_2 &- &3b_1 &+ &11b_2 &= &0 \\ \end{array}$$
with solution $a_1=b_1=\frac{1}{2},\:a_2=\frac{3}{26},b_2=-\frac{3}{26}$. So with a little manipulation
$$\begin{align} T_n&=\tfrac{1}{2}(1+\tfrac{3}{13}\sqrt{13})\left(\frac{3+\sqrt{13}}{2}\right)^n + \tfrac{1}{2}(1-\tfrac{3}{13}\sqrt{13})\left(\frac{3-\sqrt{13}}{2}\right)^n \\[2ex] &=\frac{1}{\sqrt{13}}\left(\frac{\sqrt{13}+3}{2}\right)\left(\frac{3+\sqrt{13}}{2}\right)^n + \frac{1}{\sqrt{13}}\left(\frac{\sqrt{13}-3}{2}\right)\left(\frac{3-\sqrt{13}}{2}\right)^n \\[2ex] &=\frac{1}{\sqrt{13}}\left\{\left(\frac{3+\sqrt{13}}{2}\right)^{n+1}-\left(\frac{3-\sqrt{13}}{2}\right)^{n+1}\right\} \end{align}$$