I have tried a couple of ways to get started / finish this problem but I cant seem to figure out how to fully explain and determine the value of $x_n$. I have posted my question below with figures to help explain.
I know that recurrence-relation must be used to determine the values but if its possible if you can provide sample examples that relate this question. That would be great
If I let $n \geq 1$ be an integer and use a $2 \times n$ board $D_n$
containing $2n$ cells, each side has a length of 1. T
The brick can be vetical or horizontal containg $2$ cells(explained in the bottom part of the above picture).
The tiling of board ($D_n$) is placed with bricks so that :
1.item the bricks exactly cover $D_n$ and
2.item no two bricks overlap.
So for $n \geq 1$, we let $x_n$ become number of different tilings of the board $D_n$. And I have to Determine the value of $x_n$ but I cant seem to figure it out any help or guideance would be greatly appericated.
Hint: You're probably best off looking at a recurrence relation.
Note that there are only two ways to cover the left-most two squares: either a single vertical brick, or two horizontal bricks. What does this tell you about how you can write $x_n$ in terms of $x_{n-1}$ and $x_{n-2}$?
Note that if you cover those two left ones with a single vertical brick, what's left is to choose any covering of the other $n-1$ columns... and the way to do this is precisely $x_{n-1}$. So, there are $x_{n-1}$ arrangements in which you cover the left two by a vertical brick.
What if you use two horizontal bricks? Then you've knocked out two columns, and need to pick a covering of the remaining $n-2$ columns...