Bob and Laura have bought an apartment, and are going to carpet the floor in the kitchen. The kitchen has size $2 \times n$, where $n$ is a positive integer. In how many ways can Bob and Laura complete it using carpet pieces of two types: of size $1 \times 2$ and of size $2 \times 2$? Solve by recursion.
Can anybody please help with this question, and possibly explain how to solve it?
Let $a_n$ be the number of ways to carpet a $2\times n$ kitchen. Think of the kitchen as a strip of length $n$ running from left to right. The righthand end of the strip can be carpeted in any one of three different ways: it can be a $2\times 2$ piece, it can be a pair of $1\times 2$ pieces oriented parallel to the strip, or it can be a single $1\times 2$ piece oriented crosswise to the strip. The first two possibilities are extensions of a carpeting of a $2\times(n-2)$ kitchen; the third is an extension of a carpeting of a $2\times(n-1)$ kitchen. That is, each of the $a_{n-2}$ carpetings of a $2\times(n-2)$ kitchen can be extended to $2$ different carpetings of a $2\times n$ kitchen, and each of the $a_{n-1}$ carpetings of a $2\times(n-1)$ kitchen can be extended to one carpeting of a $2\times n$ kitchen. Moreover, every carpeting an a $2\times n$ kitchen arises uniquely in one of these three ways.
You should now be able to write down a recurrence expressing $a_n$ in terms of $a_{n-1}$ and $a_{n-2}$. It will be a homogeneous recurrence with constant coefficients, and you should have some techniques for solving such recurrences. I’ll stop here for now; if you get the recurrence but can’t solve it, leave a comment indicating where you’re stuck.