How many tilings are there?

Question

In the $n$-cell below, we are to tile it completely with cells of the form $\boxdot$ and $\boxtimes \hspace{-0.45 mm}\boxtimes$. How many tilings are possible for a $12$-cell?

Let $H_n$ denote the number of such tilings for an $n$-cell. It is easy to see that $H_0 = 1, H_1 = 1, H_2 = 2, H_3 = 3,$ and $H_4 = 5$. These seem to correspond to the fibonacci recursion of $_{n+1} = S_{n}+S_{n-1}$, but how do I prove that this recursion is indeed $H_{n+1} = H_{n}+H_{n-1}$? This is equivalent to saying, "the number of tilings for an $n+1$-cell is equal to the number of tilings for an $n$-cell plus the number of tilings for an $n-1$-cell." Why is this true?

Answer 1

Hint Let us figure out $H_{n+1}$. If the last tile is $\boxdot$, by erasing this we get a tiling of $n$ by the same tilings. There are $H_n$ such tilings, and by adding $\boxdot$ at the end we get a tiling of $n+1$.

If the last tiling is $\boxtimes \hspace{-0.45 mm}\boxtimes$ by erasing it we get a tiling of $n-1$. Also, any of the $H_{n-1}$ such tiling creates by adding $\boxtimes \hspace{-0.45 mm}\boxtimes$ a tiling of $n+1$.

It is easy to check that this process creates all tilings and each tiling exactly once, therefore $$H_{n+1}=H_n+H_{n-1}$$

Answer 2

It is possible to find a direct formula for $H_n$ in terms of $n$, then show that this is equivalent to the Fibonacci numbers, without using the recursion.

---

If $n$ is even, the number of tiles of the second type ($\,\boxtimes \hspace{-0.45 mm}\boxtimes\,$) can be between $0$ and $n/2$, inclusive. If there are $k$ tiles of the second type, then there are $n-2k$ tiles of the first type, and $n-k$ total tiles in the tiling.

This means that the number of tilings of an $n$-cell with $n$ even and $k$ tiles of the second type is $$\binom{n-k}{k}$$

If we sum this over all the possible values of $k$, we find that the number of tilings of an $n$-cell with $n$ even is

$$H_n = \displaystyle\sum\limits_{k=0}^{n/2} \binom{n-k}{k}$$

For example, if we take $n=12$, this gives

\begin{align} H_{12}&=1 + \binom{11}{1} + \binom{10}{2} + \binom{9}{3} + \binom{8}{4} + \binom{7}{5} + 1\\\\ H_{12}&=1 + 11 + 45 + 84 + 70 + 21 + 1 \\\\ H_{12}&=233 \end{align}

---

If $n$ is odd, the same reasoning applies, but $k$ runs between $0$ and $(n-1)/2$. Therefore, we may write down the a full description of $H_n$:

$$H_n = \begin{cases} \displaystyle\sum_{k=0}^{n/2} \binom{n-k}{k} \qquad \qquad\text{if} \,\, n \equiv 0 \pmod{2}\\\\ \displaystyle\sum_{k=0}^{(n-1)/2} \binom{n-k}{k} \qquad \text{if} \,\, n \equiv 1 \pmod{2} \end{cases}$$

---

Finally, notice that these binomial coefficients form the "shallow diagonals" of Pascal's triangle. It is known that the sums of these shallow diagonals are equal to the Fibonacci numbers:

Our calculation of $H_{12}$ above is the diagonal summing to $233$.

---

While this does not answer your specific question about the recursion, I think it is an interesting alternative way to make the connection between your problem and the Fibonacci numbers.