\documentstyle[12pt,twoside]{article}
\input{macros-course}

\begin{document}
\psol{2}{February 18th, 1999}

\begin{problems}
\problem 
Use mathematical induction to prove that 3 divides $n^3 + 2n$ whenever 
$n$ is a nonnegative integer.

\noindent
{\bf Solution:}

\noindent
We are proving a predicate $P(n)=\mbox{``$3\,|\,(n^3+2n)$''}$ for
$n\geq{0}$.

\medskip
\noindent 
%
{\em Base case:} $P(0)$ is true because $3\,|\,(0^3+2*0)=0$.  As a reminder,
we say $n\,|\,m$, i.e. that $n$ divides $m$, if $\exists {k\in{\sf
Z}}$ s.t. $m=kn$.

\medskip
\noindent 
%
{\em Inductive case:} Let $n$ be some nonnegative integer.  Assume $P(n)$,
i.e.  that $3\,|\,(n^3+2n)$.  It follows that there is some integer
$k$ s.t. $n^3+2n=3k$.  We prove $P(n+1)$, i.e. that $3$ divides
$(n+1)^3+2(n+1)$ as follows:
$$(n+1)^3+2(n+1)=(n^3+2n)+3(n^2+3n+1)=3k+3(n^2+3n+1)=3k'$$
where $k'=k+(n^2+3n+1)$, and consequently, 
since $k'$ is an integer, $3$ divides $(n+1)^3+2(n+1)$.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%Problem 4
\problem 
Prove using mathematical induction that for all integers $n \geq 1$,
it is the case that $2^{n - 1} \leq 2^n - 1$.

\noindent
{\bf Solution:}

\noindent
We are proving a predicate $P(n)=\mbox{``$2^{n - 1} \leq 2^n - 1$''}$ for
$n\geq{1}$.

\medskip
\noindent 
%
{\em Base case:} $P(1)$ is true because $2^0=1\leq{1}=2^1-1$.

\medskip
\noindent 
%
{\em Inductive case:} Let $n$ be some integer $n\geq{1}$.  Assume
$P(n)$, i.e. that $2^{n - 1} \leq 2^n - 1$.  We prove $P(n+1)$,
i.e. that $2^n \leq 2^{n+1} - 1$ as follows:
$$2^{n}=2^{n-1}*2\leq(2^n-1)*2=2^{n+1}-2\leq{}2^{n+1}-1$$


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%Problem 5
\problem The famous Towers of Hanoi problem. There are three poles. On
one of the poles there is a stack of rings, largest at the bottom,
smallest at the top.  You have to move the rings from one pole
to another,
%pole $r$, $r \in \{1,2,3 \}$ to pole $s$, $s \in \{1,2,3 \}$
so that the rings are in the
same order on the new pole, while observing the following rules:
\begin{itemize}
\item
Only one ring may be moved at a time. 
\item At no time may a larger ring be on top of a smaller ring. 
\end{itemize}
Prove by induction that the Towers of Hanoi Problem can always be
solved.  


\noindent
{\bf Solution:}

\noindent
It is important to formalize the inductive hypothesis in the right way.
We are proving a predicate $P(n)=$``For any poles $P_1,P_2$, a Hanoi
tower of height $n$ can be moved from $P_1$ to $P_2$ according to
the rules above.'', for any $n\geq{1}$

\medskip
\noindent 
%
{\em Base case:} $P(1)$ is true because a single ring can be moved
from one pole to another in accordance with the rules.

\medskip
\noindent 
%
{\em Inductive case:} Let $n$ be some nonnegative integer.  Assume
$P(n)$.  We prove $P(n+1)$ as follows: Assume that a Hanoi tower $T$
of height $n+1$ has to be moved from pole $P_1$ to $P_2$.  Think about
the top $n$ rings of $T$ (all rings except the base ring $R$) as a
``subtower'' $T'$.  Since $T'$ is a Hanoi tower of height $n$, from
the inductive assumption $P(n)$, we know that we can move it according
to the Hanoi-Tower game rules from $P_1$ to $P_3$ (the ring $R$ on the
bottom of pole $P_1$ does not trouble us since it is bigger than all
rings of $T'$).  When such move of $T'$ from $P_1$ to $P_3$ is done,
we move $R$ from $P_1$ to $P_2$, and then we use the $P(n)$ assumption
again to argue that there are some Hanoi-Tower game moves which allow
$T'$ to be moved from $P_3$ to $P_2$, on top of $R$.  In this way, the
whole tower $T$ was moved from $P_1$ to $P_2$, and so $P(n+1)$ is
true.


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

%Problem 6
\problem 
Which amounts of money can be formed using coins of denominations
11\$ and 13\$?  Prove your answer using a form of mathematical induction.

\noindent
{\bf Solution:}

\noindent
It is true that there for every ``big enough'' integer $n$, there
exists nonnegative integers $a,b$ s.t. $n=a*11+b*13$.  The following
could serve as an intuition for why this should be true: 

\noindent
Assume that some number $n$ can be represented as
\[
n=a*11+b*13
\]
for some nonnegative integers $a,b$.  Note that since $gcd(11,13)=1$,
then 
\[
1=k_1*11-m_1*13
\]
for some positive integers $k_1,m_1$.  It is also true that
\[
1=-k_2*11+m_2*13
\]
for some other positive integers $k_2,m_2$.  Therefore, if
$n=a*11+b*13$ is big enough, then, if $b\geq{m_1}$ then
\[
n+1=(a*11+b*13) + (k_1*11-m_1*13) = (a+k_1)*11 + (b-m_1)*13
\]
or, if $a\geq{k_2}$ then
\[
n+1=(a*11+b*13) + (-k_2*11-m_2*13) = (a-k_2)*11 + (b+m_2)*13
\]
If neither $a\geq{k_2}$ nor $b\geq{m_1}$ then $n=a*11+b*13$ is smaller
than $k_2*11+m_1*13$, and we will call such $n$ ``not big enough''.

First then, we have to find the $k_1,k_2,m_1,m_2$ above.  By doing gcd
computation, we get
\begin{eqnarray*}
6*11-5*13&=&1\\
-7*11+6*13&=&1\\
\end{eqnarray*}
In other words, $k_1=6, m_1=5, k_2=7, m_2=6$.  Now we see that we can
rephrase the above arguments into the inductive proof of a predicate
$P(n)=$``$n$ can be represented as $a*11+b*13$ for some nonnegative
integers $a,b$'', for $n\geq{142}$, because
$k_2*11+m_1*13=77+65=142$.

\medskip
\noindent 
%
{\em Base case:} $P(142)$ is true because, as noted above,
$142=7*11+5*13$.

\medskip
\noindent 
%
{\em Inductive case:} Let $n$ be some integer greater or equal to
$142$.  Assume $P(n)$, i.e. that $n=a*11+b*13$ where $a,b$ are some
nonnegative integers.  We prove $P(n+1)$ as follows: First note that
either $a\geq{7}$ or $b\geq{5}$.  Otherwise, as noted above, $n$ would
be smaller than $142$.  In both cases we show that $n+1$ can be
represented as $a'*11+b'*13$ for some nonnegative integers $a',b'$: If
$a\geq{7}$ than $n+1=(a-7)*11+(b+6)*13$.  If $b\geq{5}$ than
$n+1=(a+6)*11+(b-5)*13$.  This completes the proof of $P(n+1)$.



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%Problem 7
\problem 
Use mathematical induction to prove that for a positive integer $m$, 
if $a$ and $b$ are integers with $a \equiv b \pmod{m}$, then 
$a^k \equiv b^k \pmod{m}$
whenever $k$ is a nonnegative integer. 



\noindent
{\bf Solution:}

\noindent
We are proving a predicate $P(k)=$``for all positive integers $m$ and
all integers $a,b$, if $a \equiv b \pmod{m}$, then $a^k \equiv b^k
\pmod{m}$'' for $k\geq{0}$.

\medskip
\noindent 
%
{\em Base case:} $P(0)$ is true because $a^0=b^0=1$ for all $a,b$.

\medskip
\noindent 
%
{\em Inductive case:} Let $k$ be some integer $k\geq{0}$.  Assume
$P(k)$.  We prove $P(k+1)$ as follows: Let $m$ be a positive integer
and let $a,b$ be some integers s.t. $a \equiv b \pmod{m}$.  Then by
assumption $P(k)$ it follows that $a^k \equiv b^k\pmod{m}$.
Therefore we have that $a^{k+1}=a*a^k\equiv b*b^k=b^{k+1}\pmod{m}$,
which proves $P(k+1)$.



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%Problem 9
\problem Let the function $f$ applied to nonnegative integers be
defined by the recursive definition
\[f(x) = \left\{ \begin{array}{ll} 
                     0  & \mbox{if $x=0$} \\
                     2f(x-1) + 2 & \mbox{otherwise}
                  \end{array}
                  \right. \]
Prove by induction that the closed form definition for 
$f$ is $f(n) = 2^{n+1} - 2$. 


\noindent
{\bf Solution:}

\noindent
Here we are proving a predicate $P(n)=$``$f(n)=2^{n+1}-2$'' for
$n\geq{0}$.
\medskip
\noindent 
%
{\em Base case:} $P(0)$ is true because $f(0)=0=2^{0+1}-2$

\medskip
\noindent 
%
{\em Inductive case:} Let $n$ be some integer $n\geq{0}$.  Assume
$P(n)$.  Then $P(n+1)$ is true as well, because we have that
\[
f(n+1)=2f(n)+2=2(2^{n+1}-2)+2=2^{n+2}-2
\]
The first equality follows from the inductive definition of $f(\cdot)$
since $n+1\neq{0}$.  The second equality follows from the inductive
assumption $P(n)$.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%problem 11
\problem 
Use induction to prove that if 
$A_1, A_2, \ldots A_n$ and 
$B_1, B_2, \ldots B_n$ are sets such that 
$A_k \subseteq B_k$ for all $k \in \{1,2,\ldots,n\}$
then 
$$
(A_1 \cap A_2 \cap \ldots \cap A_n)  \subseteq 
(B_1 \cap B_2 \cap \ldots \cap B_n). 
$$


\noindent
{\bf Solution:}

\noindent
Here the predicate is $P(n)=$``If $A_1, A_2, \ldots A_n$ and $B_1,
B_2, \ldots B_n$ are sets such that $A_k \subseteq B_k$ for all $k \in
\{1,2,\ldots,n\}$ then $ (A_1 \cap A_2 \cap \ldots \cap A_n) \subseteq (B_1
\cap B_2 \cap \ldots \cap B_n)$''.  We are proving it for $n\geq{1}$:

\medskip
\noindent 
%
{\em Base case:} $P(1)$ is true because it is the following tautology:
``If $A_1\subseteq B_1$ then $A_1\subseteq B_1$''.

\medskip
\noindent 
%
{\em Inductive case:} Let $n$ be some integer $n\geq{1}$.  Assume
$P(n)$.  Let's prove $P(n+1)$. Say we have two groups of $n+1$ sets
$A_1, A_2, \ldots A_{n+1}$ and $B_1, B_2, \ldots B_{n+1}$ s.t. $A_k
\subseteq B_k$ for all $k \in \{1,2,\ldots,n+1\}$.  Now we have to
show that
$$
(A_1 \cap A_2 \cap \ldots \cap A_{n+1}) \subseteq (B_1 \cap B_2 \cap \ldots
\cap B_{n+1}).
$$
Assume that $x\in(A_1 \cap A_2 \cap \ldots \cap A_{n+1})$.  Therefore
$x\in(A_1\cap A_2 \cap \ldots \cap A_{n})$ and $x\in{A_{n+1}}$.  By
inductive hypothesis $P(n)$, since $A_k \subseteq B_k$ for all $k \in
\{1,2,\ldots,n\}$, we have that $(A_1\cap A_2 \cap \ldots \cap
A_{n})\subseteq (B_1 \cap B_2 \cap \ldots \cap B_{n})$, and therefore
$x\in(B_1 \cap B_2 \cap \ldots \cap B_{n})$.  Since
$x\in{A_{n+1}}\subseteq{B_{n+1}}$ then $x\in(B_1 \cap B_2 \cap \ldots
\cap B_{n})\cap B_{n+1}= B_1 \cap B_2 \cap \ldots
\cap B_{n+1}$, which completes the proof of $P(n+1)$.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%problem 12
%\problem In Section 3.3 of the textbook there is a definition of
%strings and the concatenation operation on them.  For a string $w$ the
%notation $w^R$ is used to denote the reverse of string $w$. For
%example $1234^R$ is the string $4321$.  Prove by induction that for
%any concatenated strings $wv$, $(wv)^R=v^Rw^R$.

% Alternative 12
\problem In Section 3.3 of Rosen, there is a definition of
strings and the concatenation operation on them.  The
notation $w^R$ is used to denote the reverse of string $w$.  For
example $1234^R$ is the string $4321$.  
\begin{enumerate}
\item
Give a recursive definition of a reverse operation $w^R$ on strings.
\item
Prove by induction that for any concatenated strings $wv$,
$(wv)^R=v^Rw^R$.
\end{enumerate}


\noindent
{\bf Solution:}

\begin{enumerate}
\item
\noindent
The recursive definition of the reverse operation might look as
follows:
\begin{eqnarray*}
\lambda^R &=& \lambda\\
(wx)^R &=& x(w^R) \mbox{ \,\,\,\,if\,\,\, $w\in\Sigma^*$ and $x\in\Sigma$}
\end{eqnarray*}
The definition would be equivalent if the second line was $(xw)^R =
(w^R)x$.

\item
\noindent 
One way to prove it by induction is to prove the following predicate
$P(n)=$``For any $w,v\in\Sigma^*$, where $|v|=n$, $(wv)^R=v^Rw^R$'',
for $n\geq{0}$.

\noindent
{\em Base case:} $P(0)$ is true because if $|v|=0$ then $v=\lambda$,
and for every $w$, $(w\lambda)^R=w^R=\lambda{}w^R=\lambda^Rw^R$, where
the last equation follows from the base case of the recursive
definition of the reverse operation above.

\medskip
\noindent 
%
{\em Inductive case:} Pick $n\geq{0}$ and assume $P(n)$ is true.
Let's prove $P(n+1)$.  Pick $w,v\in\Sigma^*$ s.t. $|v|=n+1$.  By the
definition of length, it must be that $v=ux$ where $u\in\Sigma^*$ and
$x\in\Sigma$.  Furthermore, $|u|=n$.  Therefore, 
\begin{eqnarray*}
(wv)^R&=&(w(ux))^R
\\
&=&((wu)x)^R \mbox{ \,\,\,\,\, (because concatenation is associative)}
\\
&=&x(wu)^R \mbox{ \,\,\,\,\,\,\,\,\, (by the inductive definition
of reverse operation)}
\\
&=&x(u^Rw^R)\mbox{ \,\,\,\,\, (by the inductive assumption $P(n)$, since
$|u|=n$)}
\\
&=&(xu^R)w^R\mbox{ \,\,\,\,\, (again, by associativity of concatenation)}
\\
&=&(ux)^Rw^R\mbox{ \,\,\,\,\, (by the inductive definition
of reverse operation)}
\\
&=& v^Rw^R
\end{eqnarray*}
which proves $P(n+1)$.
\end{enumerate}

\end{problems}

\end{document}






