I am trying to do this question but don't know where to go from here: The question: For $n\ge1$ let $t_n$ be the number of ways to tile the squares of a 2xn checkerboard using 1x2(which can be rotated to be 2x1 tiles) and 2x2 tiles, if the 1x2 tiles come in 5 different colors and the 2x2 tiles in 4 different colors. Find and solve a recurrence relation for $t_n$.
I think I first part of 1x2 tiles to be : $t_n=3t_{n-1} +9t_{n-2}$
Is that part right? and how do i go from here
Hint: We can clearly see that $T_0 = 1, T_1 = 5, T_2 = 54$, so your relation is wrong.
Hint: The recurrance relation is $T_n = 5 T_{n-1} + 29 T_{n-2}$. Why?