        \problemdata       % Takes 5 *mandatory* arguments
        {bintrees-ind}           % latex-friendly label for the prob.
        {Induction} %topic(s) of the problem content.
        {}               % Source (if known)
        {F01 q2-4, F99 final} %Usage (list ones you are aware of).
        {}        % Last revision info (author, date).

\begin{problem}
A \emph{full binary tree} with its {\it vertices} and
{\it leaves} is defined as follows:

\begin{itemize}

\item A simple graph with one vertex is a full binary tree.  The vertex is
called the \emph{root} of the tree.  In this case, the \emph{set of
leaves} of the tree is the set whose sole member is the root, and the
\emph{set of vertices} is the same as the set of leaves.

\item If $B_1$ and $B_2$ are full binary trees such that the sets of
vertices of $B_1$ and $B_2$ are disjoint, then a simple graph consisting
of a new vertex with edges from the new vertex to the roots of $B_1$ and
$B_2$ is also a full binary tree, $B$.  The \emph{root of $B$} is the new
vertex.  The set of \emph{vertices of $B$} is the union of the set of
vertices of $B_1$ and the set of vertices of $B_2$ along with the new
vertex.  The set of \emph{leaves of $B$} is the union of the set of leaves
of $B_1$ and the set of leaves of $B_2$.

\end{itemize}

For example, two full binary trees are shown in the following Figure.
\begin{figure}[htb]
\begin{center}
\includegraphics[width=4.5in,height=3.5in]{figures/q2-trees}
\end{center}
\caption{Full binary trees}
\label{fig:trees}
\end{figure}

You will be asked to prove by structural induction that for all full
binary trees, $B$,
\begin{equation}\label{lv}
\card{\text{leaves}(B)} = \frac{\card{\text{vertices}(B)}+1}{2}.
\end{equation}
Let the induction hypothesis, $P(B)$, be equation~(\ref{lv}).

\begin{problemparts}

\problempart\pts{7} Prove the base case(s) of your induction hypothesis.

\solution{
\textbf{Base case} $P(\text{single root})$: there is 1 leaf, 1 vertex and
indeed $1=(1+1)/2$.}


\problempart\pts{8} Carefully state what must be proved in the induction step.

\solution{ \textbf{Induction step}: Prove $P(B)$, given that $B$ has a
root $r$ connected to two full binary trees $B_1$, $B_2$ such that that
$P(B_1)$ and $P(B_2)$ are true.  That is, prove that equation~(\ref{lv})
holds assuming that it holds when $B_1$ is substituted for $B$ and when
$B_2$ is substituted for $B$.}

\problempart\pts{15} Complete the proof of the induction step.

\solution{
\begin{eqnarray*}
\card{\text{leaves}(B)} & = & \card{\text{leaves}(B_1) \union \text{leaves}(B_2)}\\
 & = & \card{\text{leaves}(B_1)} + \card{\text{leaves}(B_2)} \qquad \text{because
       vertices of $B_1$ and $B_2$ are disjoint}\\
 & = & \frac{\card{\text{vertices}(B_1)}+1}{2} +
       \frac{\card{\text{vertices}(B_2)}+1}{2} \qquad\text{by induction hypothesis}\\
 &= & \frac{(1+ \card{\text{vertices}(B_1)}+
                \card{\text{vertices}(B_2)}) + 1}{2}\\
 & = & \frac{\card{ \set{r} \union \text{vertices}(B_1) \union
             \text{vertices}(B_2)} + 1}{2} \qquad \text{disjointness again}\\
 & = & \frac{\card{\text{vertices}(B)} + 1}{2}
\end{eqnarray*}

We took off one point for not mentioning disjointness.  Five students got
99 instead of a perfect 100 on the quiz because of this quibble.}

\end{problemparts}


\end{problem}
