\documentclass[11pt,twoside]{article}    
\usepackage{latex-macros/course}% !! use the macros 
\usepackage{textcomp} % to get \textcent

%\backwardscompatibility        % !! use for backwards compatibility
%\showsolutions                 % !! use to force solutions & skip query
%\hidesolutions                 % !! use to force no solutions & skip query
\renewcommand{\coursecopyrightnames}{Prof.~Albert~R.~Meyer}

\begin{document} 
\inclassproblems{2, Wed}                    % !! start the paper


\begin{problem}
\bparts

\ppart \label{2a} Prove that a $2^n \times 2^n$ plaza can be tiled using
L-shaped tiles leaving untiled \emph{any} single $1 \times 1$ square
desired.  (Yes, the solution was in the reading, but do you remember it,
and can you explain/write it?)

\solution{This variation of the problem is proved in the text, {\em Rosen
pp. 196--197} and in \href{
http://theory.lcs.mit.edu/classes/6.042/fall02/handouts/lectures/ln2.pdf}
{Week 2 Notes}.}

\ppart If you finish part~(\ref{2a}) fast, you can think about what
happens if the area of the plaza is not a power of two.  For example, can
you characterize exactly which $m \times n$ rectangles can be L-tiled with
a single empty square where?  (We don't know a complete classication of
the L-tilable rectangles.)

\eparts
\end{problem}

\begin{problem}
Pinpoint, and illustrate with a counterexample, \emph{exactly}
where the following proof goes awry.

\begin{falseclm*}
$\forall n\in \naturals\, \forall x \in \reals\ \; x^n=1$.
\end{falseclm*}

\begin{falseproof}
(by induction on $n$)

\textbf{Induction Hypothesis:}
\[
P(n) \eqdef\ \ \forall k \le n\, \forall x \in \reals\ \; x^k=1.
\]

\textbf{Base case} ($n = 0$): $P(0)$ is $\forall x \in \reals\ x^0=1$.
This holds by definition of ``zeroth power'' of a real number.

\textbf{Induction step}: Assuming $P(n)$, we have $x^k=1$ for all $k\leq
n$.  To prove $P(n+1)$ we must show that $x^k=1$ for all $k \le n+1$.
Since the induction hypothesis already handles $k \le n$, we need only
show that $x^{n+1} = 1$.  But applying the induction hypothesis with $k=n$
and $k=1$, we have $x^n=1$ and $x^1=1$.  So,
\[
x^{n+1}=x^nx^1 = 1\times 1=1.
\]
\end{falseproof}

\solution{The argument that $P(n)$ implies $P(n+1)$ is not correct when
$n=0$.

To see why this is so, let $n=0$.  So the hypothesis $P(n)$ becomes
$\forall k \le 0\, x^k =1$.  But since $k$ is a natural-number valued
variable, $k\le 0$ means $k =0$, and so the hypothesis simplifies to
$x^0=1$, which is true.  But in addition to assuming that $x^k=1$ when
$k=n$, the false proof above also requires that $x^k=1$ when $k=1$.  We
can't assume this from the induction hypothesis because it is not true
that $k \le n$ when $k=1$ and $n=0$.}
\end{problem}


\begin{problem}

Prove by induction on the size of finite sets, $A,B$, that
\begin{equation}\label{IE2}
\card{A \union B} = \card{A} + \card{B} - \card{A \intersect B}
\end{equation}

\solution{Equation~(\ref{IE2}) makes no mention of an induction variable
$n$, so to apply induction, we have to reformulate it in terms of $n$.
There are several reasonable ways to do this.  We'll choose
\[
P(n) \eqdef\quad \forall A\ \card{A} = n \implies \forall B\ \card{A
\union B} = \card{A} + \card{B} - \card{A \intersect B}.
\]
Now the conclusion of an induction proof will be $\forall n\ P(n)$.  This
is not quite the same as~(\ref{IE2})---it mentions $n$---but is obviously
equivalent to~(\ref{IE2}).  In other words, all we have to do is prove
$\forall n\ P(n)$.

\begin{proof}(by Induction).   The induction hypothesis, $P(n)$, was
defined above.

We first establish:
\begin{lemma*}
If $A \subseteq B$, then~(\ref{IE2}) holds.
\end{lemma*}
\begin{proof}(of Lemma).  In this case, $A \union B = B$, $A \intersect B =
A$, so equation~(\ref{IE2})
reduces to 
\[
\card{B} = \card{A} + \card{B} - \card{A},
\]
which holds trivially.
\end{proof}

We now proceed with the induction proof.

\textbf{Base case}: $n=0$.  This means $A = \emptyset$.  So surely, $A
\subseteq B$, and equation~(\ref{IE2}) holds by the Lemma.  So $P(0)$ is
true.

\textbf{Induction step}: Assume the induction hypothesis, $P(n)$, holds in
order to prove $P(n+1)$.

So suppose $\card{A} = n+1$.  We want to prove that~(\ref{IE2}) holds for
all finite sets $B$.  To do this we proceed by cases.  Let $B$ be any
given finite set.

Case 1: $A \subseteq B$.  Then~(\ref{IE2}) holds by the Lemma.  (Note: we
didn't even need to assume $P(n)$.)

Case 2: $A \not\subseteq B$.  In this case, there is an $a \in A - B$.  Let
$A' \eqdef A - \set{a}$.  So $\card{A'} = n$, and from $P(n)$, we have
\begin{equation}\label{A'}
\card{A' \union B} = \card{A'} + \card{B} - \card{A' \intersect B}
\end{equation}
Now
\[
A \union B = (A' \union \set{a}) \union  B =  \set{a} \union (A' \union
B),
\]
and since $a \notin (A' \union B)$, we have
\begin{equation}\label{1a}
\card{A \union B} = \card{\set{a} \union (A' \union B)} = 1 + \card{(A' \union B)}.
\end{equation}
Also, $A \intersect B = A' \intersect B$, so from~(\ref{A'}) we have
\begin{equation}\label{A'B}
\card{A' \union B} = n + \card{B} - \card{A \intersect B}.
\end{equation}
Now from~(\ref{1a}),
\begin{eqnarray*}
\card{A \union B} & = & 1 + \card{A' \union B}\\
& = & 1 + n + \card{B} - \card{A \intersect B}\\
& = & \card{A} + \card{B} - \card{A \intersect B}.
\end{eqnarray*}
So we have proved~(\ref{IE2}) in this case also.

Hence~(\ref{IE2}) holds for all $B$, and we have completed the proof of
$P(n+1)$.
\end{proof}
}
\end{problem}

\end{document}
