\documentstyle[12pt,twoside]{article}
\input{macros-course}
%\newcommand{\mod} {\mbox{\rm \ mod \/} }

\begin{document}\pset{2}{Feb. 9, 1999 (prob. 4 revised 2/17)}{Thursday, February 18}

{\bf Reading assignment: }Finish reading the {\it Nuts and Bolts of Proofs}.
Read Section 3.2-3, Section 2.4, and pages 137-141 in Section 2.5 of Rosen.
(If anybody has the old 3rd edition of Rosen, the section numbers are 
the same, and it's pages 136-140 instead).

\begin{problems}
%(Taken from Rosen)
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%Problem 1
%\problem 
%Prove by induction that $2 - 2 \cdot 7+2 \cdot 7^2 - \cdots + 2(-7)^n=(1-(-7)^{n+1})/4$
%for all nonnegative integers. 
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%Problem 3
\problem 
Use mathematical induction to prove that 3 divides $n^3 + 2n$ whenever 
$n$ is a nonnegative integer.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%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$.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%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.  
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%Problem 6
\problem Which amounts of money can be formed using coins of denominations
11\$ and 13\$?  Prove by induction that there exists an integer $k$ such
that for all integers $n\geq{k}$, it is possible to find a set of coins of
denominations 11\$ and 13\$ totalling exactly $n$ dollars.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%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. 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%Problem 2 
%\problem Use mathematical induction to prove that $1 + 3 + 5 + \ldots
%+ (2n-1) = n^2$ for all integers $n\geq{1}$. 
%that is a nonnegative integer.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%Problem 8
%\problem 
%Use mathematical induction to prove that for any $a\neq{1}$ and
%any integer $n\geq{1}$, $a^0+a^1+a^2+\ldots+a^{n-1}=(a^n-1)/(a-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$. 
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%Problem 10 % this problem is just a small modification of last terms...
% maybe we shoudl just drop it. 
%\problem
%For what values of $m$ can 
%you tile an $m \times m$ courtyard if you are given tiles that are 
%$3 \times 1$ and $2 \times 2$?  Prove that your answer is
%correct.
%
%({\em Note: $3 \times 1$ tiles can be rotated to form $1 \times 3$ tiles}).
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%problem 11
\problem 
Use induction to prove that if %for  any $n$ sets
$A_1, A_2, \ldots A_n$ and % $n$ sets
$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 A_n)  \subseteq (B_1 \cap B_2 \cap \ldots B_n). 
$$
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%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}


\end{problems}

\end{document}






