RO-TST 2008 Problem 19

Let $\mathcal{P}$ be a square and let $n$ be a nonzero positive integer for which we denote by $f(n)$ the maximum number of elements of a partition of $\mathcal{P}$ into rectangles such that each line which is parallel to some side of $\mathcal{P}$ intersects at most $n$ interiors (of rectangles). Prove that $$3 \cdot 2^{n-1} - 2 \le f(n) \le 3^n - 2.$$