\problemdata                                                             
        {False proofs-2} % latex-friendly label for the prob.
        {Induction; False Proofs} % The topic(s) of the problem content.  
        {?} % Source (if known)                                          
        {S01 Tutorial 2, 1} % Usage (list ones you are aware of). 
        {Tina Wang, S02} % Last revision info (author, date).   
                                                                         
                                                                         
\begin{problem}           
The following theorems are false, but where exactly are the bugs in        
the proofs?                                                                
                                                                           
\begin{problemparts}

\problempart 
$\forall x \in \mathbb{R} \ \forall n \in \mathbb{N} \ x^n=1$.             
                                                                           
                                                                           
\begin{proof}                                                              
The proof by strong induction on $n$.  Let $P(n)$ be the proposition       
that $x^n = 1$ for all real $x$.  In the base case, $P(0)$ holds           
because $x^n = x^0 = 1$ by definition of ``zero-th power'' of a real       
number.                                                                    
                                                                           
In the inductive step, for some $n \geq 0$ we may assume that $x^k = 1$    
for all real $x$ and for all integers $0 \leq k \leq n$                    
                                                                           
                                                                            
We must show that $x^{n+1}=1$.  By the induction hypothesis with $k=n$ and  
again with $k=1$, we have $x^n=1$ and $x^1=1$.  So,                         
\[                                                                          
x^{n+1} = x^n \cdot x^1 = 1 \cdot 1 = 1.                                    
\]                                                                          
\end{proof}                                                                 
                                                                            
\solution{                                                                  
The proof of the induction step is not correct when $n=0$.  In this         
case, $k=1$ does not satisfy $0 \leq k \leq n$.  Therefore we cannot        
assume by strong induction that $x^1 = 1$, which is false anyway when       
$x \neq 1$.}                                                                
                                                                            
\problempart

Let $p$, $n$, and $x_1, x_2,\ldots, x_n$ be positive integers.  If $p        
\mid x_1 x_2 \cdots x_n$, then $p \mid x_i$ for some $1 \leq i \leq          
n$.                                                                          
                                                                             
                                                                             
\begin{proof}                                                                
The proof by strong induction on $n$.  Let $P(n)$ be the proposition         
that if $p$ divides the product $x_1 x_2 \cdots x_n$, then $p$ divides       
$x_i$ for some $1 \leq i \leq n$.                                            
                                                                             
\emph{Base case}. $P(1)$ is trivial: if $p$ divides the length one product   
$x_1$, then $p$ divides $x_1$.                                               
                                                                             
In the inductive step, assume $P(1), \ldots, P(n)$ to prove $P(n+1)$.        
                                                                             
So suppose that $p \mid x_1x_2\cdots x_{n+1}$.  Let $y_n = x_n               
x_{n+1}$, so $x_1x_2\cdots x_{n+1} = x_1x_2\cdots x_{n-1}y_n$.  Since        
the right side of this equality is a product of $n$ terms, we have by        
induction that $p$ divides one of them.  If $p \mid x_i$ for some $i <       
n$, then we have the desired $i$.  Otherwise $p \mid y_n$.  But since      
$y_n$ is a product of the two terms $x_n, x_{n+1}$, we have by strong      
induction that $p$ divides one of them.  So in this case $p \mid x_i$      
for some $i = n$ or $i = n+1$.                                             
\end{proof}                                                                
                                                                           
\solution{                                                                 
The statement ``we have by strong induction that $p$ divides one of them'' 
is the place where the proof breaks down: it appeals to strong induction   
to justify applying the induction hypothesis for $2=k\leq n$.  But the     
base case was $n=1$, so we can't assume $2 \leq n$.  Note that the         
reasoning above is fine for every $n\geq 2$, so the whole proof would be   
fine if we had an argument to prove the claim for $n+1=2$.  But of course  
we can't prove it for $n+1=2$ because it isn't true: let $p=6, x_1 =2, x_2 
=3$.  Even though the reasoning is fine for every $n\geq 2$, the fact that 
it failed for $n=1$ let us deduce a patently false result.}                
                                                                           
                                                                           
                                                                           
\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 A false proof about 2n by 2n tilings. 

\begin{claim*}                                                              
  For $n \in \naturals, n \geq 1$, any $2n \cdot 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{                                                                  
\medskip                                                                    
  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 \naturals, 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}
                                 


