Tilings of n-board

Question

Apparently it is equivalent to talk about a tiling of an n-board with squares and dominoes and a tiling of an (n+1)-board with odd length tiles (of any odd length).

Can someone explain to me how this is true?

Answer 1

Let $a_n$ be the number of ways to tile a $1\times n$ board with squares and dominoes. Obviously, $a_1=1$ and $a_2=2$. For any $n$, you can either cover the first cell with a square or a domino, so $a_n=a_{n-1}+a_{n-2}$.

Let $b_n$ be the number of ways to tile a $1\times (n+1)$ board with tiles of odd length. Again, $b_1=1$ and $b_2=2$. For any $n$, you can cover the first cell by tile of length $1$ or $3$ or $5$, etc., so $$b_n=b_{n-1}+b_{n-3}+b_{n-5}+\dots$$ We can show by induction that $b_n=b_{n-1}+b_{n-2}$. The base cases can be checked easily. For the inductive step, assume that it is true for $n$, and we will show it for $n+2$. We have $$b_{n+2}=b_{n+1}+(b_{n-1}+b_{n-3}+\dots)=b_{n+1}+b_n,$$ which is what we need.

Answer 2

There is a bijection between the two tilings. If you start with squares and dominoes on an $n$-board, add one more square at the right hand end and then glue each domino to whatever is to its right. Conversely, if you start with odd-length tiles on an $(n+1)$-board, chop each $(2k+1)$-tile into $k$ dominoes followed by a square; this necessarily leaves a square at the right hand end, so delete it.