ILL 1972 Problem 33

A rectangle $ABCD$ is given whose sides have lengths $3$ and $2n$ , where $n$ is a natural number. Denote by $U(n)$ the number of ways in which one can cut the rectangle into rectangles of side lengths $1$ and $2$ . $(a)$ Prove that $$U(n + 1)+U(n -1) = 4U(n);$$ $(b)$ Prove that $$U(n) =\frac{1}{2\sqrt{3}}[(\sqrt{3} + 1)(2 +\sqrt{3})^n + (\sqrt{3} - 1)(2 -\sqrt{3})^n].$$