XIX OM - III - Problem 1

What is the largest number of regions into which a plane can be divided by $ n $ pairs of parallel lines?
Let $ f(n) $ denote the greatest number of regions into which $ n $ pairs of parallel lines can divide the plane.
Consider $ k + 1 $ pairs of parallel lines on the plane.
Suppose that $ (p_1, q_1), (p_1, q_2),\ldots (p_k,q_k) $ divide the plane into $ l $ regions, and that the line $ p_{k+1} $ intersects the lines of these $ k $ pairs at $ r $ points, and the line $ q_{k+1} $ at $ s $ points. Then $ 0 \leq r \leq 2k $, $ 0 \leq s \leq 2k $, with the equalities $ r = 2k $, $ s = 2k $ holding precisely when both the line $ p_{k+1} $ and the line $ q_{k+1} $ intersect each of the lines $ p_1, q_1, p_2, q_2, \ldots, p_k,q_k $ but do not pass through any of the intersection points of these lines.
These $ r $ points divide the line $ p_{k+1} $ into $ r+1 $ segments. Each of these segments is either a line segment or a ray, and when $ r = 0 $ - the entire line, lies in one of the $ l $ regions into which the lines $ p_1, q_1, p_2, q_2, \ldots, p_k, q_k $ divide the plane (with each segment lying in a different region) and splits it into two regions. The lines $ p_1, q_1, p_2, q_2,\ldots,p_k, q_k $ and $ p_{k+1} $ thus divide the plane into $ l + r + 1 $ regions. Similarly, the $ s $ points on the line $ q_{k+1} $ divide this line into $ s + 1 $ segments, each of which splits one of the previous $ l + r + 1 $ regions into two regions. All the lines $ p_1, q_1, p_2, q_2, \ldots, p_k, q_k, p_{k+1}, q_{k + 1} $ thus divide the plane into $ l + r + s + 2 $ regions.
This number is greatest when the values of $ l $, $ r $, and $ s $ are greatest, i.e., when $ l=f(k) $, $ r = 2k $, $ s = 2k $. Therefore,






Indeed, $ f(1) = 3 $; from formula (1) we obtain the subsequent values $ f(2) = 3 + 4 + 2=9 $, $ f(3) = 9 + 8 + 2= 19 $, etc.
The value of $ f(n) $ for any natural number $ n $ can be calculated by substituting into (1) $ k = 1, 2, \ldots, n - 1 $ and adding the resulting equations






From this we obtain






and after simplification










