Domino tiling on a 3 by N rectangle
The question is how to tile $3×N$ rectangle with $1×2$ domino.
I know exactly how to get the stuff below.(Assume that there is a g(x) which is an rectangle with one square on the latest row) This link asked the same question, you can't look at it if you don't understand what I mean
$$f(0) = g(0) = 1$$
$$f(n) = f(n-1) + 2g(n-1)$$
$$g(n) = f(n) + g(n-1)$$
But how can I transfer these equations into $$f(n) = 4f(n-1) - f(n-2)?$$
$\endgroup$1 Answer
$\begingroup$$$f_{n+1}=f_n+2g_n$$ and $$f_n=f_{n-1}+2g_{n-1}.$$ Thus, $$f_{n+1}-f_n=f_n-f_{n-1}+2f_n$$ or $$f_n=4f_{n-1}-f_{n-2}$$ and we are done!
$\endgroup$
