\newcommand{\ig}[1]{}

\documentclass[12pt,letterpaper]{article}

\usepackage{epsfig}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{amsthm}
\usepackage{fullpage}
\usepackage{url}

\title{Week 12 Recitation}
\author{Robert Woodward}

\begin{document}
\maketitle

\begin{itemize}
\item Questions about lecture / homework so far?

\item Questions from refresher sheet...

\item
Rosen 4.1, Problem 51, Page 281.

A knight on a chessboard can move
\begin{itemize}
\item One space horizontally (in either direction) and two spaces
  vertically (in either direction) or
\item Two spaces horizontally (in either direction) and one space
  vertically (in either direction).
\end{itemize}
Suppose that we have an infinite chessboard, made up of all squares
$(i,j)$ where $i$ and $j$ are nonnegative integers. Use mathematical
induction to show that a knight starting at $(0,0)$ can visit every
square using a finite sequence of moves. [\emph{Hint}: Use induction
on the variable $n = i+j$.]

We want to prove that a knight can visit every square on
the chessboard, using induction on the \emph{city block distance} of
the knight to a square.
\ig{Given that $n=i+j$ for a square in position $(i,j)$, the statement to
prove is the following:
\begin{equation}
\forall n, \mathrm{a\; knight\; can\; visit\; all squares\;} n
\end{equation}}
We complete the following four steps:
\begin{enumerate}
\item
\emph{State the propositional predicate:}
\begin{center}
$P(n)$: A knight can reach all squares $(i,j)$ where $i + j \leq n$.
\end{center}
Notice here that the propositional predicate is defined for $n$ and
is not prefixe by the quantifier $\forall n$.
\item
\emph{Basis Step:} We must form and verify the basis case.

First, we propose the following basis case:
\begin{center}
  $P(2)$: $\forall i,j \in \mathbb{N}$ and $(i + j \leq 2)$, a knight
  can reach square $(i,j)$.
\end{center}
Notice that the basis case corresponds to a knight being able to reach several 
squares, all those where $(i + j \leq 2)$.  

Second, we need to verify that $P(2)$ holds.  We have 6 squares with $i+j \leq 2$:
\begin{enumerate}
\item $(0,0)$: This state is reachable because this is where we start.
\item $(0,1)$: The knight moves from (0,0) to (1,2) to (2,0) to (0,1).
\begin{center}
\includegraphics[scale=0.3]{recitation12_knight}
\end{center}
\item $(1,0)$: The knight moves from (0,0) to (2,1)  to(0,2) to (1,0).
\item $(2,0)$: The knight reached this square on its way to $(0,1)$.
\item $(0,2)$: The knight reached this square on its way to $(1,0)$.
\item $(1,1)$: The knight moves from (0,0) to (1,2) to (0,1) to (2,2) to (0,3)
to (1,1).
\end{enumerate}

\item
\emph{State the Inductive Hypothesis:}  We assume that $P(k)$ holds for all $k \geq 2$: 
\begin{center}
$P(k)$: A knight can reach all squares $(i,j)$ where $i + j \leq k$.
\end{center}

\item \emph{Inductive Step:} We show that the conditional statement
  $P(k) \rightarrow P(k+1)$ is true.  That is, we prove that $P(k+1)$
  must hold assuming that $P(k)$ holds.  Consider the statement
  $P(k)$:
\begin{center}
$P(k)$: A knight can reach all squares $(i,j)$ where $i + j \leq k$.
\end{center}

We want to show that a knight can reach all squares $(i', j')$ where
$i' + j' \leq k + 1$.  Because $k + 1 \geq 3$, at least one of $i'$
and $j'$ can be chosen at least 2.  WLOG, assume $i' \geq 2$, then by
the inductive hypothesis, there is a sequence of moves ending at
$(i'-2, j'+1)$, because $i' - 2 + j' + 1 = i' + j' - 1 = k$.  From
such a square, it is just one move to the square $(i',j')$ Therefore,
$P(k+1)$ holds, so we have shown that $P(k) \rightarrow P(k+1)$.

In conclusion, the statement holds by the Principle of
Mathematical Induction.  \hfill{$\Box$}

\end{enumerate}

\item
Rosen 4.1, Problem 5, Page 280. (Similar to homework problem Rosen 4.1.4) 

Using the Principle of Mathematical Induction, we will prove that
\[\forall n \in \mathbb{N}, 1^2 + 3^2 + 5^2 + \ldots + (2n+1)^2 = (n+1)(2n+1)(2n+3)/3.\]

We complete the following four steps:
\begin{enumerate}
\item
\emph{State the propositional predicate:} 
\[P(n): 1^2 + 3^2 + 5^2 + \ldots + (2n+1)^2 = (n+1)(2n+1)(2n+3)/3.\]

\item
\emph{Basis Step:} We verify that $P(1)$ is true.

We must form the basis step. First, we can write out what $P(1)$
is. \[P(1):  1^2 + 3^2 = (1+1)(2 \times 1 + 1)(2 \times 1 + 3)/3.\]
Second, we need to verify that this holds: $1 + 9 = (2)(2 + 1)(2+3)/3
\Rightarrow 10 = 2*3*5 \Rightarrow 10 = 10$.


\item
\emph{State the Inductive Hypothesis:}  We assume that $P(k)$ holds for all $k \geq 1$: 
\[P(k): 1^2 + 3^2 + 5^2 + \ldots + (2k+1)^2 = (k+1)(2k+1)(2k+3)/3.\]

\item 
\emph{Inductive Step:} We show that the conditional statement 
$P(k) \rightarrow P(k+1)$ is true for all positive integers $k$.  That
is, we prove that $P(k+1)$ must hold assuming that $P(k)$ holds for
all positive integers $k$.  Consider the statement $P(k)$:
\[1^2 + 3^2 + \ldots + (2k+1)^2 = (k+1)(2k+1)(2k+3)/3.\]
Adding the term $(2k+3)^2$ on both sides of the equality, we get:
\begin{eqnarray*}
1^2 + 3^2 + \ldots + (2k+1)^2 + (2k+3)^3 & = & (k+1)(2k+1)(2k+3)/3 + (2k+3)^2 \\
& = & (2k+3)[(k+1)(2k+1)/3 + (2k+3)] \\
& = & (2k+3)[(2k^2 + 3k + 1)/3 + (6k + 9)/3] \\
& = & (2k+3)[(2k^2 + 9k + 10)/3] \\
& = & (2k+3)(2k+5)(k+2)/3 \\
& = & ([k+1]+1)(2[k+1]+1)(2[k+1]+3)/3
\end{eqnarray*}
Therefore, $P(k+1)$ holds, so we have shown that $P(k) \rightarrow
P(k+1)$.  In conclusion, the statement holds by the Principle of
Mathematical Induction.  \hfill{$\Box$}

\end{enumerate}

\item
Rosen 4.1, Problem 33, page 280.  (Similar to homework problem Rosen 4.1.32)

Prove that 5 divides $n^5 - n$ whenever $n$ is a nonnegative integer.

We complete the following four steps:
\begin{enumerate}
\item
\emph{State the propositional predicate:} 
\[P(n): 5 | (n^5 - n).\]

\item
\emph{Basis Step:} We verify that $P(1)$ is true.

We must form the basis step. First, we can write out what $P(0)$
is.
\[P(0): 5 | (0^5 - 0).\]
Second, we need to verify that this holds: $0^5 - 0 = 0
\Rightarrow$ 0 is divisible by 5.

\item
\emph{State the Inductive Hypothesis:}  We assume that $P(k)$ holds for all $k \geq 0$:
\[P(k): 5 | (k^5 - k).\]

\item 
\emph{Inductive Step:} We show that the conditional statement 
$P(k) \rightarrow P(k+1)$ is true for all positive integers $k$.  That
is, we prove that $P(k+1)$ must hold assuming that $P(k)$ holds for
all positive integers $k$.  Consider the statement $P(k)$:
\[5 | (k^5 - k).\]
Therefore, $\exists u$ such that $k^5 - k = 5u$.

Note that:
\begin{eqnarray*}
(k+1)^5 - (k+1) & = & k^5 + 5k^4 + 10k^3 + 10k^2 + 5k + 1 - (k+1)\\
 & = & (k^5 + 1 - k - 1) + (5k^4 + 10k^3 + 10k^2 + 5k) \\
 & = & (k^5 - k) + 5(k^4 + 2k^3 + 2k^2 + k)
\end{eqnarray*}

Using our inductive hypothesis:
$$(k+1)^5 = 5u + 5(k^4 + 2k^3 + 2k^2 + k)$$
Therefore, $(k+1)^5$ is divisible by 5.

Therefore, $P(k+1)$ holds, so we have shown that $P(k) \rightarrow
P(k+1)$.  In conclusion, the statement holds by the Principle of
Mathematical Induction.  \hfill{$\Box$}
\end{enumerate}

\item
Rosen 4.2, Problem 3, page 291. (Similar to homework problem Rosen 4.2.4)

Using the Second Principle of Mathematical Induction (or \emph{Strong} Induction), we will prove that:
\begin{center}
$\forall n \geq 8$, we can form $n$ cents using just 3-cent stamps and 5-cent stamps.
\end{center}

We complete the following four steps:
\begin{enumerate}
\item
\emph{State the propositional predicate:}
\begin{center}
$P(n):$ $n$ cents can be formed using just 3-cent stamps and 5-cent stamps.
\end{center}

\item
\emph{Basis Step:} We verify that $P(8)$ holds.
$P(8):$ one 5-cent stamp and one 3-cent stamp.

\item
\emph{State the Inductive Hypothesis:} We assume that $P(j)$ holds for all $8 \leq j \leq k$.

\item
\emph{Inductive Step:} We show that the conditional statement $[P(1) \land P(2) \land \ldots \land P(k)] \rightarrow P(k+1)$.

By the inductive hypothesis, $P(k-2)$ must hold.  Therefore, $P(k+1)$ must hold because it requires the same amount of coins as $P(k-2)$, plus~1 more~3-cent stamp.
Or, $P(k+1): P(k-2)$ and one more~3-cent stamp.
Therefore, $P(k+1)$ holds, so we have shown that $[P(1) \land P(2) \land \ldots \land P(k)] \rightarrow P(k+1)$.  In conclusion, the statement holds by the Second Principle of
Mathematical Induction.  \hfill{$\Box$}
\end{enumerate}

\item (Last 10 minutes) Quiz

\end{itemize}

\end{document}