\problemdata
{induction}
{False proof}
{trees}

\begin{problem}

  \textbf{False Proofs}

\begin{problemparts}
    \problempart 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}.
      }
  
\problempart 
% 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}
\end{problem}
