\documentclass[11pt]{article}
\usepackage{calc,fancyhdr,lastpage}
\usepackage[hmargin=.75in,vmargin=1in,
            footskip=.5in,headsep=.5in-\headheight]{geometry}
\usepackage{amsmath,amssymb}

% Page layout.
\flushbottom  % stretch text to fill up page
\reversemarginpar  % margin notes on the left

% Common symbols and macros.
\input{macros-236}

% Symbols and macros specific to this homework.
\newcommand*{\cent}{\mathord{\not\!c\,}}
\newcommand*{\B}{\mathbf{B}}

% Headings.
\pagestyle{fancy}
\let\headrule\empty
\let\footrule\empty
\lhead{{\bfseries CSC\,236\,H1F}}
\chead{{\bfseries\large Homework Exercise \#\,2}}
\rhead{{\bfseries Fall 2009}}
\lfoot{{Dept.\ of Computer Science,
    University of Toronto (St.~George Campus)}}
\cfoot{{}}
\rfoot{{Page \thepage\ of \pageref{LastPage}}}


\begin{document}

\vspace*{-5ex}

\noindent
\strong{Worth:}  2\%
\hfill
\strong{Due:}  By 6pm on Wednesday 23 September

\vspace{2.5ex}% when not using \begin{enumerate} immediately

\noindent
For each question, please write up detailed answers carefully.
Make sure that you use notation and terminology correctly, and
that you explain and justify what you are doing.
Marks \strong{will} be deducted for
incorrect or ambiguous use of notation and terminology, and for
making incorrect, unjustified, ambiguous, or vague claims
in your solutions.

{}  In particular,
keep in mind that the main point of this exercise is
to get you to practice writing proofs by induction.
This means that you will be marked mostly on
the structure of your proofs and how they were written up---in other words,
having the right idea but writing it up poorly will be worth less than
having the wrong idea but writing it up well\ldots
\begin{enumerate}


\item
    For each statement below,
    give \altemph{two} different inductive proof structures
    that could be used to prove the statement.
    Fill in as much of each proof structure as possible,
    without making any assumption about predicate $P$.
    \begin{enumerate}

    \item
        For all \altemph{even} integers $x \in \Z$, $P(x)$.

    \item
        For all $n$ that are powers of $10$, $P(n)$.
        (Recall that $n$ is a power of $10$ iff $\exists k, n = 10^k$.)

    \item
        For all $S$ that are finite sets of integers, $P(S)$.

    \end{enumerate}


\item
    Let $\B$ be the set of strings consisting of
    properly nested brackets, defined recursively as follows:
    \begin{points}
    \item  $\emptystr \in \B$,
    \item  if $x, y \in \B$, then
           $[x] \in \B$ and $xy \in \B$,
    \item  nothing else belongs to $\B$.
    \end{points}
    Prove that $\forall s \in \B$,
    the number of left brackets ``$[$'' in $s$ equals
    the number of right brackets ``$]$'' in $s$.

    \textbf{Food for thought:}
    How might you go about proving that
    an illegal string of brackets (such as ``$]\,]$'' or ``$]\,[$'')
    does \emph{not} belong to $\B$?


\end{enumerate}

\end{document}