\documentclass[12pt,twoside]{article}

\usepackage{psfig}

\input{macros-course}
\def\cent{{\not\!\mathrm{c}}}

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

\typein[\answer]{Include solutions? (y/n) }
\def\yes{y}
\ifx\answer\yes
  \typeout{}
  \typeout{Solutions *INCLUDED*.} 
  \newcommand{\solution}[1]{\bigskip \textbf{Solution:}\\ #1\bigskip\newpage}
  \usepackage[dark,first,bottom]{draftcopy}
  \draftcopyName{Solutions}{155}
\else 
  \typeout{}
  \typeout{Solutions *NOT INCLUDED*.} 
  \newcommand{\solution}[1]{\vfill\mbox{}\newpage}
%  \newcommand{\solution}[1]{}
\fi
\typeout{}

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

\begin{document}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\newcommand{\tutref}{tut2}
\newcommand{\tutnum}{2}
\newcommand{\tutdate}{February 11, 2000}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\handout{\tutref}{Mini-Quiz \tutnum}{\tutdate}

\begin{enumerate}
\item Write your name:

\bigskip

\item (Rosen, Sec. 1.5, Ex. 21) Let $A$ and $B$ be subsets of a
  universal set $U$.  Show that $A \subseteq B$ if and only if
  $\overline{B} \subseteq \overline{A}$.

\vspace{2in}

\item (Rosen, Sec. 1.6, Ex. 15) Determine whether each of the
  following functions is a bijection from $\reals$ to $\reals$.
%
\begin{enumerate}\itemsep 0\baselineskip
\item $f(x) = 2 x + 1$
\item $f(x) = x^2 + 1$
\item $f(x) = x^3$
\end{enumerate}

\vspace{2in}

\end{enumerate}

\newpage

\thispagestyle{empty}

\mbox{}

\setcounter{page}{0}

\newpage

\handout{\tutref}{Tutorial \tutnum~Problems}{\tutdate}

\begin{problems}

  \problem  

  \textbf{False Proofs}


  \bparts

    \ppart Consider the following recursive definition of the set $F$
    of full binary trees:
    
    \begin{enumerate}\itemsep 0\baselineskip
    \item A single node is in $F$.
      
    \item If $t$ and $t'$ are in $F$, then the structure formed from
      $t$, $t'$, and a single new node, with an arrow labeled
      ``left'' from the new node to $t$ and another arrow labeled
      ``right'' from the new node to $t'$, is also in $F$.
    \end{enumerate}

    The recursive definition of the set $F$ of full binary trees is
    similar to the one for binary trees, except that we only allow the
    recursive definition step that includes both a left and a right
    child.


    Find the flaw in the following proof.  Define the \emph{height} of
    a binary tree to be 0 for a single node, otherwise one more than
    the larger of its two children's heights.

    \begin{claim*}
      Any height-$n$ binary tree has exactly $2^n-1$ nodes.
    \end{claim*}
    \begin{proof}
      By induction.  The base case is clear.  For the inductive step,
      assume it is true for height-$n$ binary trees.  Putting two of
      them together under a new node gives a height $n+1$ binary tree
      which has $2*(2^n-1)+1=2^{n+1}-1$ nodes.  This proves the
      inductive step.
    \end{proof}


    \solution{%
      The basic problem here is that we are building \emph{some}
      height $n+1$ binary tree, but we are not showing the theorem for
      \emph{all} height $n+1$ binary trees.  There are height $n+1$
      trees that are \emph{not} assembled from two height $n$ trees:
      for example, I could have a height $n$ left subtree and a height
      zero right subtree.

      This general flaw, of building some but not all of the possible
      ``bigger instances,'' is known as \emph{buildup error}.
      }
  
\ppart 
% false induction
% spring 00, Victor Luchangco


\begin{claim*}
  For $n \in \nats, n\geq 1$, any $2n \times 2n$ square grid can be
  tiled by L-shaped tiles such that any particular square is left
  untiled.
\end{claim*}

\begin{proof}
  The proof is by strong induction on $n$.  Let $P(n)$ be the
  predicate: ``Any $2n \times 2n$ square grid can be tiled by L-shaped
  tiles such that any particular square is left untiled''.
  \begin{description}\itemsep 0\baselineskip
  \item[Base Case:] \mbox{} \\ %
    The base case, for $n = 1$, is very simple, just use one tile.
  \item[Inductive Step:] \mbox{} \\ %
    Assume that the claim is true for all square grids smaller than
    $2n$, and we prove it for the $2n \times 2n$ square grid.  This
    follows the proof of the $2^n \times 2^n$ case: Given a $2n \times
    2n$ square grid, with one square designated to be left untiled, we
    construct a tiling (using L-shaped tiles) for all the other
    squares, as follows: Divide the square grid up into four
    quadrants, each $n \times n$.  By the inductive hypothesis (since
    $n < 2n$ for all $n \geq 1$), we can tile each of these quadrants
    (with the L-shaped tiles) completely, except for one square of our
    choice.  For the quadrant with the square to be left untiled,
    choose that square.  For the others, choose the squares at the
    corner where the quadrants meet.  This forms an L-shaped space at
    the center of the $2n \times 2n$ square grid, which can be filled
    by a single L-shaped tile.  Thus, the entire $2n \times 2n$ square
    grid is tiled, except for the square designated.
  \end{description}
\end{proof}

Point out any logical errors in this proof (that is, not simply places
where some steps were skipped, but where there is actually an error,
though you are free to point out places where more steps should have
been included for clarity).  Then, either construct a correct proof,
or show that the claim is false.

\solution{%
  The error in the proof is that we erroneously invoke the induction
  hypothesis.  The inductive hypothesis states that we can tile all
  square grids of size $2m \times 2m$, for all $m \in \nats, m < n$.
  That is, we can tile all square grids of even size that are smaller
  than the $2n \times 2n$ square grid.  When we invoke the induction
  hypothesis, we use it to claim that we can tile an $n \times n$
  square grid.  The problem occurs when $n$ is odd.

  In fact, the claim is false.  Consider $n = 3$, \ie a $6 \times 6$
  square grid.  The grid contains $36$ squares which is divisible by
  $3$ the number of squares of an L-shaped tile.  Thus, it is not
  possible to tile such a grid so that exactly one particular square
  is left untiled.
  }

\end{problemparts}

\problem
% strong induction
% source: Velleman section 6.4, problem 5

Let $F_n$ be the $n$th Fibonacci number, for all $n \in \mathbb{N}$.
Recall that the Fibonacci numbers are defined recursively as follows:
$F_0 = 0$, $F_1 = 1$, and $F_n = F_{n-1} + F_{n-2}$, for all $n \in
\mathbb{N}, n \geq 2$.

\bparts

\ppart 

Prove that for all $n \in \mathbb{N}$, $\sum_{i = 0}^{n} F_i =
F_{n + 2} - 1$.

\ppart

Find a formula for $\sum_{i = 0}^{n} F_{2 i}$ and prove that the
formula is correct.

\eparts

\solution{%
  \bparts

  \ppart

  Let $P(n): \sum_{i = 0}^{n} F_i = F_{n + 2} - 1$.

  \ppart

  Let $P(n): \sum_{i = 0}^{n} F_{2 i} = F_{2n+1} - 1$.


  \eparts
  }

\problem
% structural induction

\mbox{}

\bparts

\ppart

Give the structural inductive definition of the set $F$ of full
binary trees.

\ppart

Define the function $\ms{numleaves}(t)$, for $t \in F$, giving the
number of ``leaves'' of the full binary tree $t$; that is,
$\ms{numleaves}(t)$, for $t \in F$, gives the number of nodes in $t$
that do not have children.  Your definition should be recursive, based
on the recursive definition of the set $F$.

\ppart

Define the function $\ms{numinternal}(t)$, for $t \in F$, giving the
number of ``internal'' nodes of the full binary tree $t$; that is,
$\ms{numinternal}(t)$, for $t \in F$, gives the number of nodes in $t$
that have children.  Your definition should be recursive, based on the
recursive definition of the set $F$.

\ppart

Prove by structural induction that for any full binary tree $t$ in
$F$, $\ms{numleaves}(t) = 1 + \ms{numinternal}(t)$.

\eparts

\solution{%
  \bparts

  \ppart \emph{Carl: I am not sure whether this is what Nancy and
    David wanted as an answer here since we give the student's the
    recursive definition in problem 1a.}

  Recall from lecture that we let $\ms{makeboth}(t,t')$, for $t, t'
  \in F$, denote the full binary tree made up of attaching the full
  binary trees $t$ and $t'$ respectively to a node, as done in the
  recursive definition of $F$.

  \begin{tabbing}
    XXX\=XXX\=XXX\=XXX\kill
    $\forall t \in F (P(t))$ \\
    1. (Base) $P(n)$, where $n$ is the single-node tree. \\
    2. (Inductive step) 
    $\forall t,t' \in F, (P(t) \wedge P(t') \Rightarrow P(\ms{makeboth}(t,t')))$ \\
    3. QED
  \end{tabbing}
  
  \ppart

   We define the function $\ms{numleaves}(t)$, for $t \in F$, as
   follows:

   $\ms{numleaves}(\text{single node}) = 1$

   $\ms{numleaves}(\ms{makeboth}(t,t')) 
   = \ms{numleaves}(t) + \ms{numleaves}(t')$

  \ppart

   We define the function $\ms{numinternal}(t)$, for $t \in F$, as
   follows:

   $\ms{numinternal}(\text{single node}) = 0$

   $\ms{numinternal}(\ms{makeboth}(t,t')) = 
   \ms{numinternal}(t) + \ms{numinternal}(t') + 1$

   \ppart

   This part is shown by structural induction on the recursion step.

   Let $P(t): \ms{numleaves}(t) = 1 + \ms{numinternal}(t)$.

   Use the structural inductive definition of part (a) to show the
   property is true.

  \eparts
  }

\end{problems}

\end{document}

\endinput

  \problem \mbox{} \\ 

  \vspace*{-\baselineskip}

  \begin{claim*}
    If every vertex in a graph is adjacent to another vertex, then the
    graph is connected.
  \end{claim*}
  
  \begin{proof}
    The proof is by induction.  Let $P(n)$ be the predicate: ``If
    every vertex in an $n$-vertex graph is adjacent to another vertex,
    then the graph is connected''.  In the base case, $P(1)$ is
    trivially true because there is only one vertex.

    In the inductive step, we assume $P(n)$ to prove $P(n+1)$.  Start
    with an $n$-vertex graph $G$; this is connected by the induction
    hypothesis.  Now add a vertex $v$ to construct an $n+1$-vertex
    graph $G'$.  By assumption $v$ is connected to one of the vertices
    of $G$; call this particular vertex $u$.

    Now we must show that for every pair of distinct vertices $x_1$
    and $x_2$, there is a path between them.  If both $x_1$ and $x_2$
    are among the vertices of $G$, then there is a path between them
    by the induction hypothesis.  Otherwise, one of the vertices is
    $v$ (say $x_1$) and the other (say $x_2$) is among the vertices of
    $G'$.  These are connected by the path from $x_1$ to $u$ to $x_2$.
  \end{proof}

  \solution{%
    The error is in the early statement ``Start with an $n$-vertex
    graph; this is connected by induction.''  The induction hypothesis
    does not say that every $n$-vertex graph is connected, but only,
    ``{\em if every vertex in an $n$-vertex graph is adjacent to
      another vertex,} then the graph is connected''.

    The core problem here is called \emph{buildup error} and is a
    common source of mistakes in inductive proofs.

    Buildup error occurs when the induction hypothesis $P(n)$ is
    itself an implication of the form $A(n) \Rightarrow B(n)$.  In
    this instance, $A(n)$ is the statement, ``every vertex in an
    $n$-vertex graph is adjacent to another vertex'' and $B(n)$ is the
    statement, ``the graph is connected''.

    In the inductive step of a correct proof, we assume $A(n)
    \Rightarrow B(n)$ in order to prove $A(n+1) \Rightarrow B(n+1)$.
    In an erroneous proof, we assume $B(n)$ in order to prove $A(n+1)
    \Rightarrow B(n+1)$.  This is precisely what happened; we assumed,
    ``the graph is connected'' rather than, ``if every vertex in an
    $n$-vertex graph is adjacent to another vertex, then the graph is
    connected''.  }

\problem

\emph{The Towers of Hanoi.}

There are three poles.  On the first pole there is a stack of rings of
increasing size, with the smallest ring on top of the stack.  The
second and third poles are empty.  The challenge is to move the entire
stack of rings to the second pole, while obeying the following rules:
\begin{itemize}
\item ~~Rings may only be moved one at a time from one pole to another.
\item ~~A ring may only be moved if it is on the top of a stack.
\item ~~A ring may only be placed on top of a larger ring.
\end{itemize}

Suppose there are $n\ge 1$ rings initially stacked on the first pole
and rings are only moved according to these rules.

\bparts

\ppart Prove that no matter how many moves are made, the rings stacked
on each pole, if any, increase in size from the top.

\ppart Prove that there is a way to move all the rings to the second
pole in $2^n-1$ moves.


\ppart Prove that the number of moves necessary to move all $n$ rings
from the first pole to the second is \emph{at least} $2^n-1$.

\eparts

\solution{%
  \bparts \ppart
  \begin{proof}
    The proof is by induction on the number of moves~---~not the
    number of rings.

    Let $P(k)$ be the predicate: ``After $k$ moves, the rings stacked
    on each pole increase in size from the top.''  The base case
    $P(0)$ follows because initially, that is, after zero moves, the
    rings are in increasing order.

    Now assume $P(k)$, namely, that they are in order on every pole
    after $k$ steps.  Suppose on the $k+1$st move ring $R$ is moved
    from pole $i$ to pole $j\neq i$.  Then the rings left on pole $i$,
    if any, are still in order.  Also, the ring that was on top of
    pole $j$, if any, must be larger than $R$ according to the rules,
    so the rings on pole $j$ increase in size starting from ring $R$
    on top.  Of course the rings on the remaining pole, if any, are
    unchanged, and so remain in increasing order.  Hence all poles
    have rings in increasing order from the top after $k+1$ moves,
    that is, $P(k+1)$ holds.
  \end{proof}

  \ppart
  \begin{proof}
    The proof is by induction on the number of rings $n$.  However, in
    order to simplify the proof, we strengthen the induction
    predicate.  In particular, we allow there to be $n$ \emph{or more}
    rings initially stacked in increasing order on \emph{any} given
    pole~---~not necessarily the ``first'' pole.

    Let $P(n)$ be the predicate: ``For $i \in \set{1,2,3}$, suppose
    there are $n \geq 1$ or more rings stacked on pole $i$ in
    increasing order from the top.  Suppose also that the rings, if
    any, on top of the other two poles are larger than the top $n$
    rings stacked on pole $i$.  Then, the top $n$ rings stacked on
    pole $i$ can be moved to any other pole in $2^n-1$ legal steps.''

    Notice that it follows as a special case of $P(n)$, that $n$ rings
    stacked in order on pole 1 can be moved to pole 2 in $2^n-1$ legal
    steps, as required.

    Now we prove $P(n)$ by induction on the number of rings $n$.
    Without loss of generality, let $i$ denote the pole on which the
    $n$ rings are stacked initially, $j$ denote the pole on which we
    must move the $n$ rings initially stacked on pole $i$, and $k$
    denote the remaining pole.
    \begin{description}\itemsep 0ex
    \item[Base Case:] \mbox{} \\ %
      $P(1)$ is true if the ring on top of pole $j$, if any, is larger
      than the ring on pole $i$, then the single ring on pole $i$ can
      be moved in $2^1-1 =1$ legal step onto pole $j$.
    \item[Inductive Step:] \mbox{} \\ %
      Assume $P(n)$ holds for some integer $n \ge 1$.
      
      Now, we must prove that $P(n+1)$ holds.  We assume that there
      are $n+1$ rings stacked in increasing order on pole $i$ and that
      the rings on the other two poles are larger than the top $n+1$
      rings stacked on pole $i$.  By the induction hypothesis, we can
      move the top $n$ rings from pole $i$ to pole $k$ in $2^n-1$
      moves.  Subsequently, it is legal to move the top ring on pole
      $i$, which is the $n+1$th ring initially stacked on pole $i$,
      from pole $i$ to pole $j$.  Finally, by the induction hypothesis
      we can move the top $n$ rings stacked on pole $k$ to pole $j$ in
      $2^n-1$ more steps.  Concluding, we have succeeded to move the
      top $n+1$ rings from pole $i$ to pole $j$ in a total of $(2^n-1)
      + 1 + (2^n-1) = 2^{n+1}-1$ legal moves; that is, we have shown
      that $P(n+1)$ is true.
  \end{description}
  \end{proof}

  \ppart
  \begin{proof}
    The solution to this part is similar to the solution to part (b).
    The key is in realizing that when the $n+1$st largest ring on pole
    $i$ is first moved to pole $j$, the $n$ rings stacked initially on
    top of pole $i$ must, by part~(a), appear in increasing order on
    pole $k$.  Thus, by the induction hypothesis at least $2^n-1$
    moves must have occurred already.  Similarly, at least another
    $2^n-1$ moves are needed after the $n+1$st ring is placed on pole
    $j$ in order to move the $n$ rings from pole $k$ to pole $j$.
  \end{proof}
  \eparts }


