\documentclass[12pt,a4paper]{amsart}
%%%%%%%%%%% Here is where you tell LaTeX to use packages. Each
%%%%%%%%%%% package gives you access to different commands and
%%%%%%%%%%% functionality. Most of them are unnecessary for the
%%%%%%%%%%% mathematics in this document.

%%%%%%%%%%% If you hadn't figured out, the % symbol automatically
%%%%%%%%%%% nulls out all subsequent characters on that line. So
%%%%%%%%%%% it's used for commenting code.
\usepackage{hyperref}
\usepackage{tikz}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{amsthm}
\usepackage{framed}
\usepackage{multicol}
\usepackage[OT2,T1]{fontenc}
\usepackage{graphicx}
\usepackage[all]{xy}
\usepackage{color}
\usepackage{mathrsfs}
\usepackage{mathtools}

%%%%%%%%%%% Determining margins and spacing.
\setlength\topmargin{-0.3in}
\addtolength{\oddsidemargin}{-.625in}
	\addtolength{\evensidemargin}{-.625in}
	\addtolength{\textwidth}{1.25in}
\setlength\footskip{1in}

%%%%%%%%%%% I think this command enables `sections'
\numberwithin{equation}{section}

%%%%%%%%%%% This command allows you to label things as `theorem',
%%%%%%%%%%% `conjecture', etc.
\newtheorem{theorem}{Theorem}[section]
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{conjecture}[theorem]{Conjecture}
\newtheorem{question}{Question}[theorem]
\newtheorem{example}{Example}[theorem]

\newcommand{\R}{\mathcal{R}}

\usepackage[utf8]{inputenc}
\title{Math 220.201 Class 16 Questions}
\begin{document}
\maketitle
\begin{enumerate}
\item [1.] {\bf Proofs}
\begin{enumerate}
\item Prove that $5\mid 3^{4n+1}+2$ for any nonnegative integer $n$.
\vskip 0.2in
\begin{proof} [Proof 1]
We prove the result by induction on $n$. The base case ($n=0$) is to show that $5\mid 3^1+2$. This is clear.

Now the inductive step. Suppose that $5\mid 3^{4n+1}+2$. Then there is some integer $k$ such that $3^{4n+1}+2=5k$. Then
$$\begin{aligned}3^{4n+1}=5k-2 &\implies 3^{4n+5}=81(5k-2)=405k-162\\
&\implies 3^{4n+5}+2=405k-160=5(81k-32)
\end{aligned}$$
Therefore, $5\mid 3^{4n+5}+2$, which completes the induction.
\end{proof}

\begin{proof} [Proof 2]
$$3^{4n+1}=3^{4n}\cdot 3^1=81^n\cdot 3 \equiv 1^n\cdot 3\pmod{5} \equiv 3\pmod{5}\equiv -2\pmod{5}$$
Thus $5\mid 3^{4n+1}+2$.
\end{proof}
\vskip 0.2in
\item Prove that there exists a positive integer $N$ with the following property: every odd integer $n\ge N$ can be written in the form $n=3a+5b+7c$ for some positive integers $a, b, c$.
\vskip 0.2in
\begin{proof}
We prove that every odd integer $n\ge 21$ can be written in the form $n=3a+5b+7c$ for some positive integers $a, b, c$. Let $P(n)$ be the property that $n$ can be written in this form. We use induction, showing that $P(21), P(23), P(25)$ are all true as the base case, and showing $P(n)\implies P(n+6)$ as the inductive step.
\begin{itemize}
\item {\bf Base case:}
$$21=3\cdot 3+5\cdot 1+7\cdot 1$$
$$23=3\cdot 2+5\cdot 2+7\cdot 1$$
$$25=3\cdot 1+5\cdot 3+7\cdot 1$$
\item {\bf Inductive Step:} Suppose that $P(n)$ is true, i.e. $n=3a+5b+7c$ where $a, b, c$ are some positive integers. Then $n+6=3(a+2)+5b+7c$. Since $a+2, b, c$ are all positive integers, it follows that $P(n+6)$ is true. This completes the induction.
\end{itemize}
\end{proof}
\vskip 0.2in
\item Prove that if $a$ and $b$ are distinct natural numbers such that $\sqrt{a}$ and $\sqrt{b}$ are both irrational, then $\sqrt{a}+\sqrt{b}$ is also irrational.
\vskip 0.2in
\begin{proof}
Suppose for a contradiction that $\sqrt{a}+\sqrt{b}$ is rational. Then $(\sqrt{a}+\sqrt{b})^2$ is rational. Write $\sqrt{a}+\sqrt{b}=r$. Then
$$\sqrt{a}=r-\sqrt{b}\implies a=(r-\sqrt{b})^2=r^2-2r\sqrt{b}+b$$
$$\implies \sqrt{b}=\frac{r^2+b-a}{2r}$$
Since $\sqrt{a}$ and $\sqrt{b}$ are both positive, $\neq 0$, so this is valid. Thus, $\sqrt{b}$ is rational, which contradicts the assumption that $\sqrt{b}$ was irrational! Therefore, $\sqrt{a}+\sqrt{b}$ is irrational.
\end{proof}
\vskip 0.2in
\item Recall that the Fibonacci sequence is defined by $F_1=1,F_2=1$, and $F_n=F_{n-1}+F_{n-2}$ for $n\ge 3$. Prove that $2^n\ge F_{n+3}$ for $n\ge 3$.
\vskip 0.2in
\begin{proof}
We prove the result by induction on $n$.
\begin{itemize}
\item {\bf Base case:} When $n=3$, we have $2^3=8$ and $F_6=8$. So $2^3\ge F_6$.
\item {\bf Inductive step:} Suppose that $2^n\ge F_{n+3}$ for some $n\ge 3$. Then
$$2^{n+1}=2^n+2^n\ge F_{n+3}+F_{n+3}=F_{n+3}+(F_{n+2}+F_{n+1})$$
Since $F_{n+1}$ is positive,
$$F_{n+3}+F_{n+2}+F_{n+1}>F_{n+3}+F_{n+2}=F_{n+4}$$
Therefore, $2^{n+1}\ge F_{n+4}$.
\end{itemize}
\end{proof}
\vskip 0.2in
\item Let $a_1=1, a_2=2$, and $a_n=\sum\limits_{i=1}^{n-1}(i-1)a_i$ for $n\ge 3$. Prove that $a_n=(n-1)!$ for $n\ge 3$.
\vskip 0.2in
\begin{proof}
We use induction on $n$.
\begin{itemize}
\item {\bf Base case:} When $n=3$, $a_3=0\cdot a_1+1\cdot a_2=2$ which equals $(3-1)!$.
\item {\bf Inductive step:} Suppose that $a_n=(n-1)!$. Then
$$\begin{aligned}
a_{n+1}=\sum\limits_{i=1}^{n}(i-1)a_i&=\left(\sum\limits_{i=1}^{n-1}(i-1)a_i\right)+(n-1)a_n\\
&= a_n+(n-1)a_n\\
&= na_n\\
&= n\cdot (n-1)!\\
&= n!
\end{aligned}$$
\end{itemize}
\end{proof}
\vskip 0.2in
\item Prove that every positive integer can be written in the form $2^ab$ where $a$ is a nonnegative integer and $b$ is an odd integer.
\vskip 0.2in
\begin{proof}
Suppose, for a contradiction, that there are positive integers which cannot be written in the form given. Let $n$ be the smallest such positive integer. Either $n$ is odd or $n$ is even. $n$ cannot be odd, because it if is, then take $a=0$ and $b=n$, and we have $n=2^0\cdot n$ is the form required.
\vskip 0.1in
Therefore, $n$ is even, so there is some integer $m$ such that $n=2m$. Since $n$ is a positive integer, this means $m<n$, and so $m$ can be written in the form $m=2^ab$ where $a$ is nonnegative and $b$ is odd. Then $n=2^{a+1}b$. But this contradicts the assumption that $n$ could not be written in this form!
\vskip 0.1in
Therefore, no such positive integer $n$ exists, and so every integer can be written in this form.
\end{proof}
\vskip 0.2in
\end{enumerate}
\item [2.] {\bf Equivalence Relations}
\begin{enumerate}
\item Let $\R$ be a relation on $\mathbb{Z}$ defined by $x\R y$ iff $x \equiv y\pmod{6}$. Describe the equivalence classes for $\R$.
\vskip 0.2in
{\bf Solution:} There are six equivalence classes:
$$[0]=\{6k: k\in\mathbb{Z}\}$$
$$[1]=\{6k+1: k\in\mathbb{Z}\}$$
$$[2]=\{6k+2: k\in\mathbb{Z}\}$$
$$[3]=\{6k+3: k\in\mathbb{Z}\}$$
$$[4]=\{6k+4: k\in\mathbb{Z}\}$$
$$[5]=\{6k+5: k\in\mathbb{Z}\}$$
\vskip 0.2in
\item Let $\R$ be a relation on $\mathbb{Z}$ defined by $x\R y$ iff $x^3+3x \equiv y^3+3y\pmod{6}$. Describe the equivalence classes for $\R$.
\vskip 0.2in
{\bf Solution:} For an integer $n$, let us consider what are the possibilities for $n^3+3n$ mod 6.
$$n\equiv 0\pmod{6} \implies n^3+3n\equiv 0\pmod{6}$$
$$n\equiv 1\pmod{6} \implies n^3+3n\equiv 4\pmod{6}$$
$$n\equiv 2\pmod{6} \implies n^3+3n=14\equiv 2\pmod{6}$$
$$n\equiv 3\pmod{6} \implies n^3+3n=36\equiv 0\pmod{6}$$
$$n\equiv 4\pmod{6} \implies n^3+3n=76\equiv 4\pmod{6}$$
$$n\equiv 5\pmod{6} \implies n^3+3n=140\equiv 2\pmod{6}$$
Thus, the given relation has three equivalence classes:
\vskip 0.5in
$$\{6k: k\in\mathbb{Z}\}\cup \{6k+3: k\in\mathbb{Z}\}$$
$$\{6k+1: k\in\mathbb{Z}\}\cup \{6k+4: k\in\mathbb{Z}\}$$
$$\{6k+2: k\in\mathbb{Z}\}\cup \{6k+5: k\in\mathbb{Z}\}$$
You could also write these as $\{3k:k\in\mathbb{Z}\}$, $\{3k+1:k\in\mathbb{Z}\}$, $\{3k+2:k\in\mathbb{Z}\}$.
\vskip 0.2in
\item Let $\R$ be a relation on $\mathbb{Z}_6$ defined by $[x]\R [y]$ iff ($[x]=[y]$ or $[x^2]=[y]$). List out the elements of $\R$ as ordered pairs $([x],[y])$. Is $\R$ an equivalence relation?
\vskip 0.2in
{\bf Solution:} We have the elements $([0],[0]), ([1],[1]), ([2],[2]), ([3],[3]),([4],[4]),([5],[5])$ because by definition each $([n],[n])$ is in $\R$. We must also include pairs of the form $([n],[n^2])$. Trying all six possibilities for $[n]$ gives us
$$([0],[0]), ([1],[1]), ([2],[4]), ([3],[3]), ([4],[4]), ([5],[1])$$
So in total,
$$\R=\{([0],[0]), ([1],[1]), ([2],[2]), ([3],[3]),([4],[4]),([5],[5]), ([2],[4]), ([5],[1])\}$$
This is \emph{not} an equivalence relation, as it is not symmetric! I.e. we have pairs $([x],[y])$ with the property that $[x^2]=[y]$ but $[y^2]\neq [x]$ - for example, $([2],[4])$ and $([5],[1])$.
\vskip 0.2in
\end{enumerate}
\item {\bf Hints}
\begin{enumerate}
\item (Proofs a) Proof by induction. There's also a way without induction.
\item (Proofs b) If $n$ is an odd number, then the next odd number is $n+2$, then $n+4$, then $n+6$, and so on. If $n$ can be written in the form $3a+5b+7c$, can you prove that $n+6$ or $n+8$ can be written in this form? What about $n+4$ or $n+2$?
\item (Proofs c) Proof by contradiction.
\item (Proofs d) Proof by induction.
\item (Proofs e) Proof by induction, with base case $n=3$.
\item (Proofs f) You can do this by strong induction, or by minimum counterexample.
\item (Equivalence Classes b) If you take an integer $x$, what are the possibilities for $x^3+3x$ mod 6?
\item (Equivalence Classes c) Remember that $\mathbb{Z}_6$ is just a six-element set. You can think of $\R$ as `descended' from the relation on $\mathbb{Z}$ given by
$$x\R y \iff (x\equiv y\text{ (mod }6)) \vee (x^2\equiv y\text{ (mod }6))$$
\end{enumerate}
\end{enumerate}
\end{document}