Inductive definition for number of ways to tile a $2$ by $n$ grid?

Question

Inductive definition for number of way to tile a 2xn grid?

I have attempted to formulate an inductive definition, thinking that every extra column we add, adds an extra n-1 ways to tile the grid. Therefore I came up with: $u_{n+1}=u_n+(n-1)$. However, this is not a second order recurrence relation, so I am not sure about the answer they are looking for. Any ideas? (I am not asking about actually solving the recurrence relation, just formulating it, hopefully I will then be able to solve it on my own!)

Answer 1

To derive a recurrence for $u_n$, consider the only two possible ways to cover column $n$:

• One vertical domino
• Two horizontal dominoes that cover columns $n-1$ and $n$

In each case, removing the covered columns reduces to a smaller problem with the same structure as the original problem.