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

%\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{3, Tue.}                    % !! start the paper


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

\begin{problem}
Use induction to prove that the equation below holds for all $n \geq
1$.

\begin{eqnarray*}
1^3 + 2^3 + \ldots + n^3 & = & (1 + 2 + \ldots + n)^2 
\end{eqnarray*}

\solution{We proceed by induction.  Let $P(n)$ be the proposition
that:

\begin{eqnarray*}
1^3 + 2^3 + \ldots + n^3 & = & \left(\frac{n(n+1)}{2}\right)^2
\end{eqnarray*}

This is equivalent to the equation in the claim, since $1 + 2 + \ldots
+ n = n (n + 1) / 2$.  First, we must show that $P(1)$ is true.  This
is immediate, since:

\begin{eqnarray*}
1^3 & = & \left(\frac{1 (1+1)}{2}\right)^2
\end{eqnarray*}

\noindent Next, we must show that $P(n)$ implies $P(n + 1)$ for all $n
\geq 1$.  Assuming that $P(n)$ is true, we can reason as follows:

\begin{eqnarray*}
1^3 + 2^3 + \ldots + n^3 + (n + 1)^3
    & = & \left(\frac{n(n+1)}{2}\right)^2 + (n + 1)^3 \\
    & = & \left(\frac{(n + 1)(n+2)}{2}\right)^2
\end{eqnarray*}

\noindent The first step uses the assumption $P(n)$, and the second
uses only algebra.  This shows that $P(n + 1)$ is true.  Therefore,
$P(n)$ is true for all $n \geq 1$ by induction.}

\end{problem}

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

\newpage

\begin{problem}
Let $S_n$ be the sum of all fractions where the numerator is 1 and the
denominator is the product of a nonempty subset of the integers $1, 2,
\ldots, n$.  For example:

\begin{eqnarray*}
S_3 & = & \frac{1}{1} + \frac{1}{2} + \frac{1}{3} + \frac{1}{1 \cdot 2} + 
          \frac{1}{1 \cdot 3} + \frac{1}{2 \cdot 3} +
          \frac{1}{1 \cdot 2 \cdot 3}
\end{eqnarray*}

Use induction to prove that $S_n = n$ for all $n \geq 1$.

\solution{We use induction.  Let $P(n)$ be the propositon that $S_n =
n$.  First, we must show that $P(1)$ is true.  This follows, since:

\begin{eqnarray*}
S_1
    & = & \frac{1}{1} \\
    & = & 1
\end{eqnarray*}

Next, we must show that $P(n)$ implies $P(n + 1)$ for all $n \geq 1$.
To that end, assume that $P(n)$ is true.  Then we can reason as follows:

\begin{eqnarray*}
S_{n + 1}
    & = & S_n + \frac{1}{n + 1} \cdot S_n + \frac{1}{n + 1} \\
    & = & n + \frac{1}{n + 1} \cdot n + \frac{1}{n + 1} \\
    & = & n + 1
\end{eqnarray*}

For the first step, observe that every fraction in $S_{n+1}$ either
does not have $n + 1$ in the denominator (and thus is also in $S_n$),
has $n + 1$ and at least one other number in the denominator (and thus
is counted by the second term), or has only $n + 1$ in the denominator
(and thus is equal to the last term).  The second step uses the
assumption $P(n)$ and the third step is algebra.  This shows that $P(n
+ 1)$ is true.  By induction, $P(n)$ is true for all $n \geq 1$.  }

\end{problem}

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

\instatements{
\newpage
\vspace{1in}
\centerline{\resizebox{7in}{!}{\includegraphics{grid.eps}}}
}

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

\newpage

\begin{problem}
Prove that a $2^n \times 2^n$ courtyard with a $1 \times 1$ statue in
the middle can be covered with $L$-shaped tiles.
\end{problem}

\solution{
A proof of this theorem is present in Rosen on pages 247-248.
}

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

\instatements{
\newpage
\centerline{\resizebox{7in}{!}{\includegraphics{grid.eps}}}
}

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

\end{document}
