IMO 1972 LL ROM33

A rectangle ABCD is given whose sides have lengths 3 and

imolonglistmathematicsolympiad

IMO 1972 LL ROM33

Origin: ROM

Problem

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) = \sqrt 3[( \sqrt 3 + 1)(2 + \sqrt 3)n + ( \sqrt 3 −1)(2 − \sqrt 3)n].