\documentstyle[12pt,twoside]{article}
\input{macros-course}

\addtolength{\textheight}{.05in}
\begin{document}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{problems}

\problem 
Let $h_n$ equal the number of ways in which the square of a 
1-by-n chessboard can be colored using the colors red, white,
and blue so that no two squares that are colored red are adjacent.
Find and verify a recurrence relation that $h_n$ satisfies.
Then find a closed-form formula for $h_n$.


{\bf Solution:}\\
$h_n = 2 h_{n-1} + 2 h_{n-2}$.


\problem

We wish to determine the number of different ways to divide a convex
polygonal region into triangular regions by drawing diagonals which
do not intersect in the interior.  For notational convenience, we
deal with a convex polygonal region of $n+ 1$ sides which is divided
into $n - 1$ triangular regions by $n- 2$ diagonals.   An example
with $n = 4$ is shown below.


\begin{figure}[htbp]
\centerline{\psfig{figure=divide.eps,height=2.0in}}
\caption{\em Some ways of dividing up a pentagon.}
\label{fig:diagex}
\end{figure}

Let $h_n$ denote the number of ways of dividing a convex polygonal
region with $n + 1$ sides into triangular regions by inserting
diagonals which do not intersect in the interior.  Define $h_1 = 1$.
i.e., think of a line segment as a polygonal
region with 2 sides and no interior.  Define $h_2 = 1$ since
a triangular region has no diagonals and it cannot be further subdivided.
Give a recurrence formula for $n \geq 3$.

{\bf Hint}: Choose a base for $K$.  Choose a triangular region $T$
which has the base as a side.  $T$ divides $K$ into two polygonal
regions.  Sum over the choices for the base

{\bf Solution}:\\


Let $n \geq 3$.  Consier a convex polygonal region $K$ with 
$n + 1 \geq 4$ sides.  We distinguish one side of $K$ and call it
the base.  In each division of $K$ into triangular regions, the base
is a side of one of the triangular regions $T$, and this triangular
region divides the remainder of $K$ into a polygonal region $K_1$
with $k + 1$ sides and a polygonal region $K_2$ with $n - k + 1$
sides, for some $k = 1, 2, \cdots, n-1$.  See the figure below.


\begin{figure}[htbp]
\centerline{\psfig{figure=break.eps,height=2.0in}}
\caption{\em Some ways of dividing up a pentagon.}
\label{fig:break}
\end{figure}

The further subdivision of $K$ can be accomplished by subdividing
$K_1$ and $K_2$ into triangular regions by inserting diagonals of
$K_1$ and $K_2$, respectively which do not intersect in the
interior.  Since $K_1$ has $k + 1$ sides, $K_1$ can be divided
into triangular regions in $h_k$ ways.  Since $K_2$ has $n - k + 1$
sides, $K_2$ can be divided into triangular regions in $h_{n-k}$
ways.  Hence for a particular choice of the triangular region
$T$ containing the base, there are $h_k h_{n-k}$ ways of dividing
$K$ into triangular regions by diagonals that do not intersect
in the interior.  Hence there are a total of
\[ h_n = \sum_{k=1}^{n-1} h_k h_{n-k} \]
ways to divide $K$ in this way.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\end{problems}
\end{document}

