\problemdata     
{S01-PS5-6}           
{recurrences, plug-and-chug, induction}              
{S98-PS5, S01-PS5} 		
{S01 Karger}


\begin{problem}


Suppose that $n$ ovals are drawn in a plane
so that every pair of ovals intersects at either 0 or 2 points.
Let $x_n$ be the maximum number of regions that can be formed by such
a configuration of ovals.  We can express $x_n$ using the
recurrence below.

\begin{eqnarray*}
x_1 & = & 2 \\
x_{n+1} & = & x_n + 2n
\end{eqnarray*}

The region outside of any oval ``counts''; for example, one oval
defines two regions, because the oval has an inside region and an
outside region.

\begin{problemparts}

\problempart Solve this recurrence using the plug and chug method.

\solution {
First, we repeatedly apply the recurrence equation.

\begin{eqnarray*}
x_n & = & x_{n-1} + 2(n-1) \\
    & = & x_{n-2} + 2(n-2) + 2(n-1) \\
    & = & x_{n-3} + 2(n-3) + 2(n-2) + 2(n-1)
\end{eqnarray*}

We can now guess a general form and check it by applying the
recurrence equation one more time.

\begin{eqnarray*}
x_n & = &   x_{n-i} + 2(n-i) + \ldots + 2(n-2) + 2(n-1) \\
x_n
  & = & x_{n-i-1} + 2(n-i-1) + 2(n-i) + \ldots + 2(n-2) + 2(n-1) \\
  & = & x_{n-(i+1)} + 2(n-(i+1)) + 2(n-i) + \ldots + 2(n-2) + 2(n-1)
\end{eqnarray*}

Setting $i = n-1$, gives an expression for $x_n$.

\begin{eqnarray*}
x_n & = &   x_{n-i} + 2(n-i) + \ldots + 2(n-2) + 2(n-1) \\
    & = &   x_1 + 2 + 4 + \ldots + 2(n-2) + 2(n-1) \\
    & = &   2 + 2 + 4 + \ldots + 2(n-2) + 2(n-1) \\
    & = &   2 + 2 \sum_{j=1}^{n-1} j
\end{eqnarray*}

Now we get the closed form $x_n = n(n-1) + 2$ from the formula for the
sum of an arithmetic series.
}

\problempart Describe how to arrange $n$ ovals so as to form $x_n$ regions.
No proof of correctness is required.

\solution {

Make all the ovals circles of the same size.  Place the
second circle slightly right of the first, the third slightly right of
the second, and so forth.}

\end{problemparts}
\end{problem}
