Rectangle tilling with smaller rectangles

Question

To find the no of ways a rectangle of size 2 $\times $ n can be filled using 1 $\times $ 2 and 2 $\times$ 2 pieces. $$\quad$$ I tried to solve it as a recurrence relation, $a_{2 \times (n+2)} = a_{2 \times n} + 2 $, since when we increase the length from n to n+2 we can fill this gap with either 1, 2 $\times$ 2 rectangle or 2, 1 $\times$ 2 rectangle, however this method does not seems right, Other than this i found that the maximum no of 1 $\times$ 2 rectangles that can be used is n and maximum no of 2 $\times$ 2 rectangle that can be used is n/2, How to solve this.

Answer 1

Hint: The recurrence should be $a_n=a_{n-1}+2a_{n-2}$ since
if one fill the leftmost piece with vertical $1\times 2$ piece, the rest fills arbitrary with $a_{n-1}$ variants, or
one fills the leftmost with 2 horizontal $2\times 1$ pieces or
one $2\times 2$ piece, and the rest arbitrary with $a_{n-2}$ variants.
Now we solve $\lambda^2=\lambda+2$, $\lambda_1=2, \lambda_2=-1$, so we get
$a_n=C_12^n+C_2(-1)^n, a_1=1, a_2=3$ and obtain $C_1,C_2$.