# Tiling Matrix Question

How many ways can you tile a $$2\times2n$$ board completely with $$1\times2$$ and $$2\times1$$ tiles? Your answer should be an explicit formula, found by deriving a matrix equation, diagonalizing the matrix, and raising it to power.

This question is for my math class, and frankly, I have no idea where to start. Could someone give me some starting help?

• Induction seems like a good place to start. – Math1000 Jan 13 '20 at 19:20
• Try recursive formulation. – K.K.McDonald Jan 13 '20 at 19:21
• @Math1000 would this allow me to derive a matrix equation? – power_of_epi Jan 13 '20 at 19:49
• See OEIS A001519. – RobPratt Jan 13 '20 at 22:08

Assume $$T(2n)$$ is the number of ways you can tile $$2\times 2n$$ grid. we have $$T(2)=2$$. Now for the $$T(2(n+1))=T(2n+2)$$ the number of ways can be obtained with this rationale:

The number of ways we can tile new $$2\times(2n+2)$$ grid is dependant on how we tile the last $$2\times 2$$ appended tiles. If we put $$2$$ horizontal $$1\times 2$$ tiles in new added $$2\times2$$ square, we have all the $$T(2n)$$ ways, but if we put a single vertical $$2\times 1$$ tile in there, then we have $$T(2n+1)$$ ways for tiling the rest of grid. These are the only possible tiling options (only ways of partitioning the new tiling) and thus $$T(2n+2)=T(2n)+T(2n+1)$$. We need another initial condition to solve it so we count the ways for a $$2\times 3$$ grid as $$T(3)=3$$ and we solve the recursion.

The solution of linear difference equation with constant coefficient are of the form $$f[n]=z^n$$ (this is a well known theorem from z-transform and discrete Fourier transform and digital signal processing systems). Thus we have $$T(n)=z^n$$.

$$T(2n+2)=T(2n)+T(2n+1) \Rightarrow z^{2n+2}=z^{2n}+z^{2n+1} \Rightarrow z^2-z-1=0$$

Which gives us the roots $$z_{1,2}=\frac{1 \pm \sqrt{5}}{2}$$. Now we have to find the unknown coefficients $$A,B$$ with initial conditions (we have two roots and thus two unknown coefficient for each root must be considered, the solution is of the form $$T(n)=A\left( \frac{1-\sqrt{5}}{2} \right)^n+B\left( \frac{1+\sqrt{5}}{2} \right)^n$$)

$$T(1)=1,T(2)=2 \Rightarrow \begin{cases} \frac{1-\sqrt{5}}{2}A+\frac{1+\sqrt{5}}{2}B=1 \\ \left(\frac{1-\sqrt{5}}{2}\right)^2 A-\left(\frac{1+\sqrt{5}}{2}\right)^2 B=2 \end{cases} \Rightarrow A=\frac{5-\sqrt{5}}{10},B=\frac{5+\sqrt{5}}{10}$$

And thus the solution is $$T(n)=\left(\frac{5-\sqrt{5}}{10}\right)\left( \frac{1-\sqrt{5}}{2} \right)^n+\left(\frac{5+\sqrt{5}}{10}\right)\left( \frac{1+\sqrt{5}}{2} \right)^n$$

We can solve this equation in the matrix form too. Again consider the equations $$T(2n+2)=T(2n)+T(2n+1)$$, this is for an even entry $$2n$$, for an arbitrary number $$n$$ we have $$T(n+2)=T(n)+T(n+1)$$ or equivalently $$T(n+1)=T(n)+T(n-1)$$. We can define $$u_m^k=[T(n),T(n-1),\cdots,T(n-m+1)]^T$$. Then we can write

$$u_m^k= \begin{bmatrix} 1 &1 &0 &0&\cdots &0 &0 \\ 0 &1 &1 &0&\cdots &0 &0 \\ 0 &0 &1 &1&\cdots &0 &0 \\ \vdots &\vdots &\vdots &\vdots &\ddots &\vdots &\vdots \\ 0 &0 &0 &0 &\cdots &1 &1 \\ 0 &0 &0 &0 &\cdots &1 &0 \\ \end{bmatrix} u_m^{k-1} = A_m u_m^{k-1}$$ For example for $$m=2$$ we have

$$u_2^k = \begin{bmatrix} 1 &1\\ 1 &0 \end{bmatrix} u_2^{k-1}$$

With this equation we can get the next terms of series ($$T(n+1)$$) by multiplying the current known terms (all previous terms up to $$T(n)$$) by $$A_m$$. We know that $$u_1^2 = [1 \;\; 0]^T$$ (consider $$T(0)=0$$). Thus we have to compute $$u_m^n=A_m^n u_m^1$$. The only thing left is computing $$A_m^n$$. First notice that the matrix $$A_m$$ is full rank and has $$m-2$$ eigenvalues equal to $$1$$ (i.e. $$\lambda_2 \cdots \lambda_{m-1}=1$$) and two eigenvalues equal to $$\lambda_1 = \frac{1+\sqrt{5}}{2}, \lambda_m = \frac{1-\sqrt{5}}{2}$$ because the characteristic polynomial is $$(\lambda-1)^{m-2}(\lambda^2-\lambda-1)$$. The eigenvectors may or may not exist (for $$m=2,3$$ i know for sure eigenvectors exist and matrix is diagonalizable, if eigenvalue decomposition is not possible, we can use Jordan canonical form to represent the matrix and calculate the $$n$$-th power). In order to avoid complexity, we go with $$m=2$$. In this case we have

$$A_2 = \begin{bmatrix} 1 &1\\ 1 &0 \end{bmatrix}^n= \begin{bmatrix} \frac{1+\sqrt{5}}{2} &\frac{1-\sqrt{5}}{2}\\ 1 &1 \end{bmatrix} \begin{bmatrix} \frac{1+\sqrt{5}}{2} &0\\ 0 &\frac{1-\sqrt{5}}{2} \end{bmatrix} \begin{bmatrix} \frac{1+\sqrt{5}}{2} &\frac{1-\sqrt{5}}{2}\\ 1 &1 \end{bmatrix}^{-1} = U\Lambda U^{-1}$$

and thus

$$A_2^n=U\Lambda^n U^{-1}= \begin{bmatrix} \frac{1+\sqrt{5}}{2} &\frac{1-\sqrt{5}}{2}\\ 1 &1 \end{bmatrix} \begin{bmatrix} \left(\frac{1+\sqrt{5}}{2}\right)^n &0\\ 0 &\left(\frac{1-\sqrt{5}}{2}\right)^n \end{bmatrix} \left( \frac{1}{\frac{1+\sqrt{5}}{2} - \frac{1-\sqrt{5}}{2}} \right)\begin{bmatrix} 1 &-\frac{1-\sqrt{5}}{2} \\ -1 & \frac{1+\sqrt{5}}{2} \end{bmatrix}$$

and the $$n$$'th term can be calculated as $$A_2^n \times [1 \;\; 0]^T$$

Which after multiplication gives us $$T(n)= \frac{\left(\frac{1+\sqrt{5}}{2}\right)^n-\left(\frac{1-\sqrt{5}}{2}\right)^n}{\frac{1+\sqrt{5}}{2}-\frac{1-\sqrt{5}}{2}}=\frac{(1+\sqrt{5})^n-(1-\sqrt{5})^n}{2^n \sqrt{5} }$$

• Yes, it is easy to get the Fibonacci numbers using a recurrence relation. But the OP appears to be asking for a proof using linear algebra (presumably a simplified version of that in Mathematical Miniatures which gives a formula for the number of ways of tiling an $m\times n$ board with dominoes). – almagest Jan 13 '20 at 20:39