0
$\begingroup$

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?

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

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} }$

$\endgroup$
1
  • $\begingroup$ 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). $\endgroup$ – almagest Jan 13 '20 at 20:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.