Let's consider a partition of a strip $ 3 \times n$ into $1 \times 2$ rectangles and call $a_{n}$ - the number of such partitions. For instance, $a_{0}=1, a_{1}=0, a_{2}=3, a_{3}=0 \ldots$. How to find a recurrence for $a_{n}$?
It's claimed that it's reasonable to consider a strip $2 \times n$ size and the same strip without a top left cell and work with two recurrent relations but i got some troubles with constructing them.
If we consider a $3 \times n$ partition and add $3 \times 2$ to the right side, the recurrence looks like $a_{n+2}=a_{n}+2$. Does it make any sense?
Denote by $a_0(n)$ the number of perfect tilings of an $(3\times n)$-strip, by $a_1(n)$ the number of tilings where one horizontal brick overlaps at the right end, and by $a_2(n)$ the number of tilings where two horizontal bricks overlap at the right end. These numbers satisfy the following recursions: $$\eqalign{a_0(n)&=a_1(n-1)+a_0(n-2)\cr a_1(n)&=2a_0(n-1)+a_2(n-1)\cr a_2(n)&=a_1(n-1)\cr}\tag{1}$$ The first of these arises as follows: You obtain an $a_0(n)$-tiling by closing an $a_1(n-1)$-tiling with a vertical brick, or by adding three horizontal bricks to an $a_0(n-2)$-tiling. The others are similar.
Using the third equation $(1)$ you can eliminate $a_2(n)$ from the second equation, and some further manipulation allows to arrive at a recurrence involving only $a_0(n)$: $$a_0(n)-4 a_0(n-2)+a_0(n-4)=0\ .$$ Now put $a_0(2m)=:b_m$. Then the $b_m$ satisfy $$b_0=1,\qquad b_1=3,\qquad b_m-4b_{m-1}+b_{m-2}=0 \quad(m\geq2)\ .$$ This can be dealt with using the "Master Theorem".