So I am having some trouble understanding how one is to come up with the recursive definition to the following problem...
We are given a rectangle of width $2$ and length $n$. Suppose we have dominoes of size $2\times 1$. What is the number of different ways we can cover the $2\times n$ rectangle?
The solution is suppose to be $a(n) = a(n-1) + a(n-2)$ but I'm not understanding exactly how they have arrived at that. I can plug values in and see that it does indeed work but what the intuition is behind that is what confuses me.
Thanks in advance!
In a corner, you have two possibilities to place a domino, either vertical
which leaves you with an $(n-1)×2$ rectangle to tile, or horizontally
which forces a horizontal domino below
and leaves you with an $(n-2)×2$ rectangle.