\documentclass[a4paper,12pt]{article}
%\usepackage[DIV=12]{typearea}
\usepackage[hscale=0.8,vscale=0.9,centering]{geometry}

%\usepackage[utf8]{inputenc}
%\usepackage[T1]{fontenc}
%\usepackage{pstricks}

\usepackage{hfoldsty}
\usepackage[neverdecrease]{paralist}
\usepackage{amsmath,amsthm,amssymb,upgreek}

\newcommand{\N}{\mathbb N}
\newcommand{\Z}{\mathbb Z}
\newcommand{\divides}{\mid}
\renewcommand{\theequation}{\fnsymbol{equation}}

\theoremstyle{definition}
\newtheorem{problem}{Problem}
\newtheorem*{bonus}{Bonus}
\theoremstyle{remark}

%\newtheorem*{solution}{Solution}
\usepackage{verbatim}
\let\solution=\comment
\let\endsolution=\endcomment

\pagestyle{empty}

\begin{document}

\thispagestyle{empty} 
\mbox{}

\mbox{}

\noindent\begin{picture}(0,0)
  \put(0,60){\sf Ad - Soyad:}
  \put(0,30){\sf \"O\u grenci Numaras\i:}
\end{picture}%
{\Large MSGS\"U, MAT 221, S\i nav}\hspace{\stretch{1}} 
\renewcommand{\arraystretch}{1.5}
\raisebox{-2.5cm}[0cm][0cm]{\begin{tabular}[b]{|c|p{1cm}|}\hline 
       1&\\
\hline 2&\\
\hline 3&\\
\hline 4&\\
\hline 5&\\
%\hline B&\\
\hline $\Sigma$&\\ \hline
\end{tabular}}

10 Kas\i m 2014, Saat 13:00

\vspace{1ex}

\parbox{12cm}{\textbf{\"O\u gretmen}: David Pierce}

\vspace{1ex}

\parbox{12cm}{\textbf{Y\"onergeler}: S\i navda 4 sayfada 5 soru var.
%Notlandıran için çözümlerinizin nasıl okunacağı açık olmalı. 
\emph{Sadece 4 soruyu cevaplay\i n.}
L\"utfen dikkat ederek yaz\i n.  \.Ingilizceyi veya T\"urk\c ceyi
kullanabilirsiniz.} 

\mbox{}

\noindent As in class, $\N$ is the set $\{1,2,3,\dots\}$ 
of \textbf{natural numbers,}
and $x'$ is the \textbf{successor} of $x$, so $1'=2$, $2'=3$, and so on.
\begin{comment}
  

It satisfies the \textbf{Peano Axioms:}
\begin{inparaenum}[(1)]
  \item
It has an element $1$, and
\item
there is operation $x\mapsto x'$ on $\N$,
where $x'$ is the \textbf{successor} of $x$, and
\item
$1$ is not a successor, 
\item
the operation of succession is injective,
and 
\item
the structure $(\N,1,{}')$ allows for proofs by \textbf{induction.}
\end{inparaenum}


\end{comment}
We also let $\upomega=\{0\}\cup\N$ and $0'=1$.


\begin{problem}
For a given value of $n$ in $\N$,
let $\bar x$ denote the congruence-class of $x$ \emph{modulo} $n$,
and let $\Z_n=\{\bar x\colon x\in\N\}=\{\bar 1,\dots,\bar n\}$.
If $\overline{x'}=\overline{y'}$, then $\bar x=\bar y$.
Therefore we can define
%\begin{equation*}
$\bar x\;'=\overline{x'}$.
%\end{equation*}
The structure $(\Z_n,\bar 1,{}')$ allows proofs by induction.
We have shown
that addition and multiplication on $\Z_n$ can be defined recursively by
\begin{align*}
  \bar x+\bar 1&=\bar x\;',&\bar x+\bar y\;'&=(\bar x+\bar y)\;',\\
  \bar x\cdot\bar 1&=\bar x,&\bar x\cdot\bar y\;'&=\bar x\cdot\bar y+\bar x.
\end{align*}
\begin{enumerate}[(a)]
\item 
If $n=6$, show that there is an operation on $\Z_n$ given by
\begin{align}\label{*}
  \bar x^{\bar 1}&=\bar x,&\bar x^{\bar y'}&=\bar x^{\bar y}\cdot\bar x.
\end{align}
It is enough to fill out the table
$
\begin{array}{|*8{c|}}\hline
\multicolumn{2}{|c|}{}&\multicolumn{6}{c|}{y}\\\cline{3-8}
\multicolumn{2}{|c|}{\raisebox{1.5ex}[0pt]{$\bar x^{\bar y}$}}&1&2&3&4&5&6\\\hline
&1&&&&&&\\\cline{2-8}
&2&&&&&&\\\cline{2-8}
&3&&&&&&\\\cline{2-8}
\raisebox{1.5ex}[0pt]{$x$}&4&&&&&&\\\cline{2-8}
&5&&&&&&\\\cline{2-8}
&6&\phantom{xxx}&\phantom{xxx}&\phantom{xxx}&\phantom{xxx}&\phantom{xxx}&\phantom{xxx}\\\hline
\end{array}\;$.
\item
If $n=3$, show that there is \emph{no} operation on $\Z_n$ as in \eqref{*}.
\end{enumerate}
\end{problem}

\begin{solution}\mbox{}
  \begin{enumerate}[(a)]
  \item 
$\begin{array}{|*8{c|}}\hline
\multicolumn{2}{|c|}{}&\multicolumn{6}{c|}{y}\\\cline{3-8}
\multicolumn{2}{|c|}{\raisebox{1.5ex}[0pt]{$\bar x^{\bar y}$}}&1&2&3&4&5&6\\\hline
&1&1&1&1&1&1&1\\\cline{2-8}
&2&2&4&2&4&2&4\\\cline{2-8}
&3&3&3&3&3&3&3\\\cline{2-8}
\raisebox{1.5ex}[0pt]{$x$}&4&4&4&4&4&4&4\\\cline{2-8}
&5&5&2&5&2&5&2\\\cline{2-8}
&6&6&6&6&6&6&6\\\hline
\end{array}$
\item
Using \eqref{*}, we obtain
$\bar 2^{\bar 1}=\bar 2$, $\bar 2^{\bar 2}=\bar 4=\bar 1$,
$\bar 2^{\bar 3}=\bar 2$, so $\bar 2^{\bar 4}=\bar 1$,
so $\bar 2^{\bar 1}\neq\bar 2^{\bar 4}$,
although $\bar 1=\bar 4$.
  \end{enumerate}
\end{solution}

\newpage

\begin{problem}
  Using only the recursive definition of addition on $\N$ and induction,
prove that addition is associative.
\end{problem}

\begin{solution}
  By definition of addition,
  \begin{equation*}
    x+(y+1)=x+y'=(x+y)'=(x+y)+1.
  \end{equation*}
Suppose $x+(y+z)=(x+y)+z$.  Then
\begin{equation*}
  x+(y+z')=x+(y+z)'=(x+(y+z))'=((x+y)+z)'=(x+y)+z'.
\end{equation*}
\end{solution}

\vfill
\vfill

\begin{problem}
We know $2\cdot\displaystyle\sum_{k=1}^nk=n\cdot(n+1)$.  
For all $n$ in $\N$, prove
%\begin{equation*}
$\left(\displaystyle\sum_{k=1}^nk\right)^2=  \displaystyle\sum_{k=1}^nk^3$.
%\end{equation*}
\end{problem}

\begin{solution}
  The claim is obvious when $n=1$.
Suppose it is true when $n=m$.  Then
\begin{multline*}
\left(\sum_{k=1}^{m+1}k\right)^2
=\left(\sum_{k=1}^mk\right)^2+2\cdot\sum_{k=1}^mk\cdot(n+1)+(n+1)^2\\
=\sum_{k=1}^nk^3+n\cdot(n+1)^2+(n+1)^2
=\sum_{k=1}^nk^3+(n+1)^3
=\sum_{k=1}^{n+1}k^3.
\end{multline*}
\end{solution}
\vfill
\vfill
\vfill

\newpage
\begin{problem}
We can define the so-called binomial coefficients recursively by
  \begin{align*}
  \binom 00&=1,&\binom 0{k+1}&=0,&
\binom{n+1}0&=1,&\binom{n+1}{k+1}&=\binom nk+\binom n{k+1}.
\end{align*}
Using only this definition, and induction,
show that, for all $n$ in $\upomega$,
%\begin{equation*}
  $\displaystyle\sum_{k=0}^n\binom nk=2^n$.
%\end{equation*}
\end{problem}

\begin{solution}
  The claim is obvious when $n=0$.
Suppose it is true when $n=m$.  Then
\begin{align*}
  \sum_{k=0}^{m+1}\binom{m+1}k
&=\binom{m+1}0+\sum_{k=1}^m\binom{m+1}k+\binom{m+1}{m+1}\\
&=1+\sum_{k=1}^m\left(\binom mk+\binom m{k-1}\right)+1\\
&=1+\sum_{k=0}^m\binom mk+\sum_{k=0}^{m-1}\binom mk+1\\
&=\sum_{k=0}^m\binom mk+\sum_{k=0}^m\binom mk\\
&=2\cdot 2^m=2^{m+1}.
\end{align*}
\end{solution}
\vfill

\newpage


\begin{problem}
Let $d$ be the greatest common divisor of $385$ and $168$.
  \begin{enumerate}[(a)]
  \item 
Find $d$.
\item
Find a solution from $\N$ of one of the equations
\begin{align*}
  385x&=168y+d,&
168x&=365y+d.
\end{align*}
  \end{enumerate}
\end{problem}

\begin{solution}\mbox{}
  \begin{enumerate}[(a)]
  \item 
Since
\begin{align*}
   385&=168\cdot2+49\\
168&=49\cdot3+21\\
49&=21\cdot2+7
\end{align*}
and $7\divides 21$, we conclude $\gcd(385,168)=7$.
\item
From the previous computations,
\begin{align*}
  7
&=49-21\cdot2\\
&=49-(168-49\cdot3)\cdot2\\
&=49\cdot7-168\cdot2\\
&=(385-168\cdot2)\cdot7-168\cdot2\\
&=385\cdot7-168\cdot16.
\end{align*}
Thus $385\cdot7=168\cdot16+7$.
  \end{enumerate}
\end{solution}
\vfill
\end{document}