\begin{problems}
\problem Suppose $S(n)$ is a predicate on natural numbers, $n$, and
suppose
\[
\forall k \in \nats\; S(k) \implies S(k+2).
\]
Explain which of the following is possible:
\bparts
\ppart $\forall n \ge 0\; S(n)$
\ppart $\bar{S(0)} \land \forall n \ge 1\; S(n)$
\ppart $\forall n \ge 0\; \bar{S(n)}$
\ppart $(\forall n \le 100\; S(n)) \land (\forall n > 100\; \bar{S(n)})$
\ppart $(\forall n \le 100\; \bar{S(n)}) \land (\forall n > 100\; S(n))$
\eparts

\solnospace{
\begin{enumerate}

\item The formula in this case specifies that $S$ is always true.  So
$S(k+2)$ is always true, and therefore $S(k) \implies S(k+2)$ is always
true.  So this case is possible.

\item This time $S$ is false at 0, but true everywhere else.  So $S(k)
\implies S(k+2)$ still always holds because $S(k+2)$ is still always true.
So this case is possible.

\item Now $S$ is always false.  So $S(k) \implies S(k+2)$ is always true
because $S(k)$ is false.  So this case is possible.

\item In this case, $S$ is true for $n$ up to 100 and false from 101 on.
So $S(99)$ is true, but $S(101)$ is false.  That means that $S(k) \not
\implies S(k+2)$ for $k = 99$.  This case is impossible.

\item In this final case, $S$ is false for $n$ up to 100 and true from 101
on.  So $S(k) \implies S(k+2)$ for $k \le 100$ because $S(k)$ is false,
and $S(k) \implies S(k+2)$ for $k \ge 99$ because $S(k+2)$ is true.  So
this case is possible.

\end{enumerate} 
}

\problem Rosen, Exercise 3.2.63

\solnospace{%page 96 (63)

This problem is very similar to Example $12$; the only difficulty is in
visualizing what's happening in three dimensions.  The basis step $(n=1)$
is trivial, since one tile coincides with the solid to be tiled.  To make
this read a little easier, let us call a $1 \times 1 \times 1$ cube a
``cubie,'' and let us call the object we are tiling with, namely the $2
\times 2 \times 2$ cube with one cubie removed, a tile.  For the inductive
step, assume the inductive hypothesis, that the $2^n \times 2^n \times
2^n$ cube with one cubie removed can be covered with tiles, and suppose
that a $2^{n+1} \times 2^{n+1} \times 2^{n+1}$ cube with one cubie removed
is given.  We must show how to cover it with tiles.  Think of this large
object as split into eight octants, by planes parallel to the faces.  The
missing cubie occurs in one of these octants.  Now position one tile with
its center at the center of the large object, so that the missing cubie in
the tile lies in the octant in which the large object is missing its
cubie. This creates eight $2^n \times 2^n \times 2^n$ cubes, each missing
exactly one cubie-one in each octant.  By the inductive hypothesis, we can
fill each of these smaller objects with tiles.  Putting these tilings
together gives us the desired tiling of the $2^{n+1} \times 2^{n+1} \times
2^{n+1}$ cube with one cubie removed, as desired.}

\iffalse \problem Velleman exercise 6.1.10

\solnospace{omitted} \fi

\problem %%Spring99 tutorial 2

The next example of an ordinary induction proof makes use of modular
arithmethic.  Related notation is reviewed below.  In these definitions,
$a$ and $b$ are integers, and $m$ is a positive integer.

\begin{itemize}
\item $a$ \emph{divides} $b$, written $a \divides b$, means that $b$ is a
multiple of $a$; that is, $b = a k$ for some integer $k$.  For example, $7
\divides 21$, since $21 = 7 \cdot k$ where $k = 3$.

\item $a \equiv b \pmod{m}$, read as ``$a$ is congruent to $b$ modulo
$m$,'' means that $a$ and $b$ leave the same remainder when divided by
$m$.  For example, $15 \equiv 9 \pmod{6}$ because 15 and 9 both leave a
remainder of 3 when divided by 6.  Equivalently, $a \equiv b \pmod{m}$
means that $m \mid (a - b)$.

\item $a \bmod m$ (read ``$a$ mod $m$'') is the remainder when $a$ is
divided by $m$.  For example, $15 \bmod 6$ is equal to 3, because 15 divided
by 6 leaves a remainder of 3.  More precisely, $a \bmod m$ is the
unique number $r$ such that $a = mk + r$ where $k$ is an integer and
$0 \leq r < m$.
\end{itemize}

Note that $a \divides b$ and $a \equiv b \pmod{m}$ are propositions, but
that $a \bmod b$ is an integer quantity.  These two different notions
of ``$\bmod$'' are related in the following way:

\begin{equation*}
a \equiv b \pmod{m}  \iff (a \bmod m) = (b \bmod m)
\end{equation*}

Prove by induction:

\begin{theorem*}
If $n$ is an odd positive integer, then $n^2 \equiv 1 \pmod{8}$.
\end{theorem*}

\solnospace{This theorem is a little different in that we are not required to
prove a result for all positive $n$, but rather just for odd positive
$n$.

There are two ways to handle this complication.  One approach is to
reformulate the theorem as follows: if $k$ is a non-negative integer,
then $(2k+1)^2 \equiv 1 \pmod 8$.  This is equivalent to the original
theorem, since the expression $2k+1$ takes on all odd positive values
as $k$ takes on all non-negative values.  Now a proof by ordinary
induction on $k$ works.

A second approach is to use a variant of induction.  Suppose that we
prove proposition $P(1)$ and prove that $P(n)$ implies $P(n+2)$ for
all odd positive integers $n$.  Then we should believe that $P(1),
P(3), P(5), \ldots$ are all true for the same reason that we believe
ordinary induction works.  In effect, we introduce a new axiom just as
credible as the original induction axiom.  We will use this second
approach in the proof.

Introducing new induction-like axioms all the time might not seem like
a good idea.  But all of these little variants on induction can be
proven from the simple, original axiom.  So there is no great harm.
The key point is that there must be a chain of implications extending
from each predicate back to the base case (or cases).

\begin{proof}
The proof is by induction on $n$.  Let $P(n)$ be the proposition that
$n^2 \equiv 1 \pmod{8}$.  In the base case, $P(1)$ is true because
$1^2 \equiv 1 \pmod{8}$.

In the inductive step, for odd $n \geq 1$ assume that $n^2 \equiv 1
\pmod{8}$ to show that $(n+2)^2 \equiv 1 \pmod{8}$.  Since $n$ is an
odd integer, $4n + 4 = 4(n+1) = 8(\frac{n+1}{2}) \equiv 0 \pmod{8}$.
Adding this to the induction hypothesis implies that $n^2 + 4n + 4
\equiv 1 + 0 \pmod{8}$.  Simplifying this congruence gives $(n+2)^2
\equiv 1 \pmod{8}$.  Therefore, $P(n)$ implies $P(n+2)$, and the claim
is proved by induction.
\end{proof}

This proof contains a mystery.  Where did the magic term $4n + 4$ come
from?  Here is the reasoning that one might follow to discover the
inductive step in this proof.  We want to prove that $(n+2)^2 \equiv 1
\pmod{8}$, and we can assume that $n^2 \equiv 1 \pmod{8}$.  To go from
the assumption to the desired result, we need to add a little bit to
the left side, changing $n^2$ to $(n+2)^2$.  The value of this little
bit is $(n+2)^2 - n^2 = 4n + 4$.  We lucked out because, it is not
hard to see that this is always a multiple of 8 when $n$ is odd.
Arranging these observations into a straight line of reasoning gives
the proof.
}

\problem Prove that Ackerman's function (as specified in Rosen before
Exercise 3.3.36) is a uniquely defined total function on $\nats \cross
\nats$. Definition of Ackerman's function:
$$ 
A(m,n)=
\begin{cases}
2n &\text{if $m=0$}\\ 
0 &\text{if $m \geq 1$ and $n=0$}\\
2  &\text{if $m \geq 1$ and $n=1$}\\
A(m-1,A(m,n-1)) &\text{if $m \geq 1$ and $n \geq 2$}
\end{cases}.
$$

\solnospace{
We have to prove that:
\begin{enumerate}

    \item \label{unique} There is a unique proposed definition for all
    pairs $(m,n) \in \mathbb{N} \times \mathbb{N}$.

    \item \label{consis} The proposed definition is consistent (in
    particular there is no circular reference).
\end{enumerate}

\begin{proof}
\ref{unique}:
Let $\left\{
\begin{array}{l}
\mathcal{E}_1 = \{ (m,n) \in \mathbb{N} \times \mathbb{N} \, | \, m = 0 \} \\
\mathcal{E}_2 = \{ (m,n) \in \mathbb{N} \times \mathbb{N} \, | \, m \geq 1$ and $n = 0 \} \\
\mathcal{E}_3 = \{ (m,n) \in \mathbb{N} \times \mathbb{N} \, | \, m \geq 1$ and $n = 1 \} \\
\mathcal{E}_4 = \{ (m,n) \in \mathbb{N} \times \mathbb{N} \, | \, m \geq 1$ and $n \geq 2 \} \\
\end{array}
\right.$

It is easy to see that the four sets above form a partition of $\mathbb{N}
\times \mathbb{N}$.

As there is a unique definition in each of these cases, overall, there is
a unique proposed definition for all pairs $(m,n) \in \mathbb{N} \times
\mathbb{N}$.

\end{proof}

\begin{proof}
\ref{consis} 

The proof uses a double induction, first on $m$, then on $n$.

More precisely, let us prove by induction on $m$ that:\\
$\forall m \in \mathbb{N}, \, \mathcal{P}(m): \; A(m,n)$ is properly defined for all $n \in \mathbb{N}$, and is a natural number.
\begin{itemize}
    \item Basis: $m=0$.\\
        This is the first case in the proposed definition.
        Since $2n$ is a natural number for all $n \in \mathbb{N}$, $\mathcal{P}(0)$ trivially holds.
    \item Inductive step: suppose $\mathcal{P}(m-1)$ holds for some $m \geq 1$,
        and let us prove that $\mathcal{P}(m)$ also holds.\\
        What we need to prove is that:\\
        $\forall n \in \mathbb{N}, \mathcal{Q}(n): \; A(m,n)$ is properly defined, and is a natural number.\\
        We will prove this assertion by induction on $n$.
    \begin{itemize}
        \item Special case: $n'=0$.\\
            This is the second case in the proposed definition.
            Since $0$ is a natural number, $A(m,0)$ is properly defined.
        \item Basis: $n'=1$.
            (We do not use the case $n'=0$ as the basis, since the recursive definition holds for $n' \geq 2$).\\
            This is the third case in the proposed definition.
            Since $2$ is a natural number, $A(m,1)$ is properly defined.
        \item Inductive step: suppose $\mathcal{Q}(n'-1)$ holds for some $n' \geq 2$,
            and let us prove that $\mathcal{Q}(n')$ also holds.\\
            $\mathcal{Q}(n'-1)$ means that $A(m,n'-1)$ is properly defined and is a natural number.\\
            Then we can use $\mathcal{P}(m-1)$ for the particular value $n=A(m,n'-1)$, which yields that
            $A(m,n')=A(m,A(m,n'-1))$ is properly defined and is a natural number.\\
            This is exactly $\mathcal{Q}(n')$.
    \end{itemize}
\end{itemize}

\end{proof}

\subsection{Remarks:}

In our induction hypothesis, we included, along with the required property
that $A(m,n)$ is properly defined, the additiona property that it's value
is a natural number.  Though this additional property was not what had
been asked to prove, we needed it for our proof.  This is another example
of the phenomenon discussed in lecture: using induction, it can be easier
to prove ``harder'' theorem than the one first given original.

\remove{This is a very common mechanism.  Sometimes, when you try to prove the
inductive step for a property $\mathcal{P}$, you figure out that it would
be much easier if an extra property $\mathcal{Q}$ is also true.  In that
case, you can try to incorporate that in the property $\mathcal{P}$ to
prove, and prove the extended property $\mathcal{P} \wedge \mathcal{Q}$ is
true.}
}

\end{problems}
