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