If I have some linear recurrence of form
$$f(n) = a_1f(n-1) + a_2f(n-2) + a_3f(n-3) + \cdots + a_kf(n-k)$$
How does this translate to tilings? For example the Fibonacci sequence is the same as asking how many ways you can tile a 1xn board with tiles of length 1 and 2. How does this generalize to any linear recurrence?
Well... sort of. One slight twist is needed, to account for the $a_1,\ldots,a_k$ terms. Let us assume, for the moment, that these are all non-negative integers.
Suppose that you have $a_1$ different colors of tiles of length $1$; $a_2$ different colors of tiles of length $2$; all the way up through $a_k$ different colors of tiles of length $k$. (Assume you have an unlimited supply of every color of every length tile.)
In how many ways can you use these tiles to cover a $1\times n$ board?
The first tile must have some size, $t$; this tile can be in any one of the $a_t$ colors we have in tiles that size. Having placed that tile, we then have to come up with some way to tile the remaining $n-t$ spaces. This is where we get the recurrence $$ f(n)=a_1\,f(n-1)+a_2\,f(n-2)+\cdots+a_k\,f(n-k), $$ as you requested.