A difficult question I'm having problems with regarding recurrence relations and recurrence equations.
The question is as follows:
In how many different ways can I cover a 3xn checkberboard with 2x1 domino pieces?
My problem:
the formula I came up with seems to skip $n-1$. I'll show you. Here are the possible ways to start filling the tiles:
$\begin{pmatrix} a & a & ... \\ b & c & ... \\ b & c & ...\end{pmatrix}$
Or
$\begin{pmatrix} a & b & ... \\ a & b & ... \\ c & c & ... \end{pmatrix}$
Or
$\begin{pmatrix} a & a & ... \\ b & b & ... \\ c & c & ...\end{pmatrix}$
Do you see the problem? There is no way to fill just the first column. there is no dependence on n-1. If you were to ask me what is the recurrence equation, I'd say:
$f(n) = 3f(n-2)$
Could that be? That doesn't make sense really.
First of all, there are cases that you haven't covered, such as
$$\begin{pmatrix} a & a & e & e \\ b & c & c & f\\ b & d & d & f\end{pmatrix},$$ so your recursion isn't so simple. See here for more.
As you observed, we can't fill exactly one column with these dominoes, but we can say even more. We can't allow the matrix to have an odd number of columns at all, so in fact, the recursion must skip back to $n-2,$ rather than $n-1.$