
\section{Strengthening the Hypothesis: Tiling}

Our next proof illustrates some new ideas:
\begin{itemize}
\item Sometimes you need to strengthen inductive hypothesis in order to
  prove it.
\item Sometimes induction helps finding a construction, not just do a
  proof.
\end{itemize}

The new CS building currently under construction (on Vassar Street,
next to the pool) will cost about \$140 million\.  
Money has come from many donors, including Bill Gates\.
Donors get something in return, e.g., something named after them\.
What Bill G. wants is one of the buildings named after him, plus a
statue of himself in the middle of the courtyard\.

The planned courtyard consists of $2^n \times 2^n$ squares, for some
$n \geq 1$\.  (We don't yet know how big $n$ is)\.  The architect,
Frank Gehry, wants to cover most of this with L-shaped tiles, each
covering three squares\.  But one of the four center squares will be
left empty, for the statue\.  Can this be done?  If so, how?
(We want a general solution, for all values of $n$)\.  

Example: $n = 2$
\begin{figure}
\begin{picture}(100,100)

\put(0,0){\line(1,0){100}}
\put(25,25){\line(1,0){50}}
\put(25,75){\line(1,0){50}}
\put(0,100){\line(1,0){100}}

\put(0,50){\line(1,0){25}}
\put(75,50){\line(1,0){25}}

\put(0,0){\line(0,1){100}}
\put(25,25){\line(0,1){50}}
\put(75,25){\line(0,1){50}}
\put(100,0){\line(0,1){100}}

\put(50,50){\line(0,1){25}}
\put(50,50){\line(1,0){25}}

\put(50,0,){\line(0,1){25}}
\put(50,75){\line(0,1){25}}

\put(50,50){\framebox(25,25){B}}

\end{picture}
\caption{A legal tiling of a 4x4 courtyard.  The B marks Bill.}
\end{figure}

Can we prove what we want by induction\?  For $P(n)$, let's try: \\ 
For any $2^n \times 2^n$ courtyard, and any particular central square,
$\exists$ a tiling of the courtyard with exactly that square left
untiled.

\begin{proof}
  {\em (doomed attempt)} In the base case: $n = 1$, we can use just
  one tile\.  In the inductive step, we try to produce a tiling of a
  $2^{n+1} \times 2^{n+1}$ courtyard with one center square blank\.
  We can assume tilings of any $2^n \times 2^n$ courtyard with any
  center square blank\.  We might think of subdividing into four $2^n
  \times 2^n$ sub-courtyards\.  But it doesn't seem to help to be able
  to tile those with centers left open...
\end{proof}

Here we've hit the first case where just trying to prove the statement
directly by induction doesn't work\.
The solution may be surprising: \newl\
Prove a {\em stronger\/} theorem that implies the one we want\. \\
But isn't that harder? 
Actually, strengthening a statement to be proved by induction often
makes the proof {\em easier\/}\.  The reason is that, although we have
to prove a stronger $P(n+1)$, we also can rely on a stronger $P(n)$\.

Here, let's redefine $P(n)$ to be the predicate that says, for {\em every\/}
square in a $2^n \times 2^n$ courtyard, we can tile the rest of the 
courtyard, with that square left blank\.
Stronger\.
But now $P(n) \Rightarrow P(n+1)$ is easier\.
And the theorem we wanted originally is just a special case.

\begin{proof}
  Induction\.  The base, $P(1)$, is as before\.  For the inductive
  step, $n \geq 1$, start with an arbitrary $2^{n+1} \times 2^{n+1}$
  courtyard with an arbitrary square to leave blank\.  Let's try to
  tile this, assuming tilings of any $2^n \times 2^n$ courtyard with
  {\em any\/} square blank\.

  Again, divide the $2^{n+1} \times 2^{n+1}$ courtyard into four $2^n
  \times 2^n$ quadrants\.  One will contain the square that must be
  left blank; it can be tiled by inductive hypothesis\. \\
  Next, put one tile in the center, covering one square in each of the
  other 3 quadrants\.  Now use the inductive hypothesis three more
  times to tile the rest of the 3 quadrants.
\end{proof}

Make sure you understand the logical structure of this proof\.
This proof provides a tiling method, not just existence proof\. 
And it gives a stronger result than we originally were looking for.

This proof not only showed the existence of a tiling---it actually gave a
recipe for {\em producing\/} one\.
For example:  To tile a $2^3 \times 2^3$ square leaving the upper right
corner empty, divide it into 4, put one tile in the center, and
recursively tile the 4 pieces, each with one square missing. (See Figure \ref{tiling2})

\begin{figure}[h]
\begin{center}
\scalebox{0.5}{\includegraphics{figures/tilings}}
\end{center}
\caption{A valid tiling for an 8x8 square leaving the upper right corner empty}\label{tiling2}
\end{figure}




%[[[Diagram]]]

%[[[Anyone want to draw a helpful diagram?]]]

The inductive proof here yields a recursive tiling algorithm.

