\documentclass{article}

\usepackage{amsmath}
% \usepackage{hyperref}

\usepackage{amssymb}
\usepackage{bm}
%usepackage{amsfonts}%This is to have nice letters
\usepackage{amsthm}
\usepackage{enumerate}
\usepackage{graphicx}
\usepackage{psfrag}
\usepackage{multicol}
%usepackage{showkeys}
\usepackage{color}
\usepackage{url}
% \usepackage{mathabx}

\usepackage{algpseudocode}

\usepackage{mathtools}

\usepackage{xy}
\input xy
\xyoption{all}

\usepackage{tikz-cd}


\setlength{\hoffset}{-0.5in}
\addtolength{\textwidth}{1.0in}
\setlength{\voffset}{-0.5in}
\addtolength{\textheight}{1.0in}

\newcommand{\excise}[1]{}%{$\star$\textsc{#1}$\star$}
\newcommand{\comment}[1]{{$\star$\sf\textbf{#1}$\star$}}

%\numberwithin{section}{part}
%\renewcommand\thepart{\Roman{part}}
% Theorem environments with italic font
\newtheorem*{thm}{Theorem}
\newtheorem*{lemma}{Lemma}
\newtheorem*{claim}{Claim}
\newtheorem*{cor}{Corollary}
\newtheorem*{prop}{Proposition}
\newtheorem*{conj}{Conjecture}
\newtheorem*{question}{Question}
\newtheorem*{prob}{Problem}

\theoremstyle{definition}
\newtheorem*{alg}{Algorithm}
\newtheorem*{example}{Example}
\newtheorem*{remark}{Remark}
\newtheorem*{defn}{Definition}
\newtheorem*{conv}{Convention}
\newtheorem*{obs}{Observation}

\numberwithin{equation}{section}

%For numbered lists with arabic 1. 2. 3. numbering
\renewcommand\labelenumi{\theenumi.}

%For separated lists with consecutive numbering
\newcounter{separated}

\newcommand{\ring}[1]{\ensuremath{\mathbb{#1}}}

%single characters, used in math mode
\renewcommand\>{\rangle}
\newcommand\<{\langle}
\newcommand\0{\mathbf{0}}
\newcommand\CC{\ring{C}}
\newcommand\KK{{\mathcal K}}
\newcommand\MM{{\mathcal M}}
\newcommand\NN{\ring{N}}
\newcommand\OO{{\mathcal O}}
\newcommand\QQ{\ring{Q}}
\newcommand\RR{\ring{R}}
\newcommand\TT{{\mathcal T}}
\newcommand\ZZ{\ring{Z}}
\newcommand\FF{\mathbb{F}}
\newcommand\dd{{\mathbf d}}
\newcommand\kk{\Bbbk}
\newcommand\mm{{\mathfrak m}}
\newcommand\nn{{\mathfrak n}}
\newcommand\pp{{\mathfrak p}}
% \newcommand\qq{{\mathfrak q}}
\newcommand\ww{{\mathbf w}}
\newcommand\xx{{\mathbf x}}
\newcommand\cA{{\mathcal A}}
\newcommand\cB{{\mathcal B}}
\newcommand\cC{{\mathcal C}}
\newcommand\cG{{\mathcal G}}
\newcommand\cP{{\mathcal P}}
\newcommand\cW{{\mathcal W}}
\newcommand\oA{\hspace{.35ex}\ol{\hspace{-.35ex}A\hspace{-.2ex}}\hspace{.2ex}}
\newcommand\oJ{{\hspace{.45ex}\overline{\hspace{-.45ex}J}}}
\newcommand\oQ{\hspace{.15ex}\ol{\hspace{-.15ex}Q\hspace{-.25ex}}\hspace{.25ex}}
\newcommand\ttt{\mathbf{t}}
\renewcommand\aa{{\mathbf a}}
\newcommand\bb{{\mathbf b}}
\newcommand\ee{{\mathbf e}}

\newcommand\free{{\mathcal F}}
\renewcommand\AA{{\mathcal A}}
\newcommand\qq{{\mathsf q}}

%roman font words for math mode
\newcommand\gp{\mathrm{gp}}
\newcommand\emb{\mathrm{emb}}
\newcommand\tor{\mathrm{tor}}
\renewcommand\th{\mathrm{th}}

%math symbols without arguments
\newcommand\app{\mathord\approx}
\newcommand\can{0}
\newcommand\iso{\cong}
\newcommand\nil{\infty}
\newcommand\ott{\ol\ttt{}}
\newcommand\til{\mathord\sim}
\newcommand\too{\longrightarrow}
\newcommand\Iqp{I_q{}^{\hspace{-.7ex}P}}
\newcommand\Irp{I_{\rho,P}}
\newcommand\Isp{I_{\sigma,P}}
\newcommand\Mwp{M_\ww^P}
\newcommand\rqp{\rho_q^{\hspace{.2ex}P}}
\newcommand\Iaug{I_{\mathrm{aug}}}
\newcommand\Irpp{I_{\rho',P'}}
\newcommand\MipI{M_\infty^P(I)}
\newcommand\MrpI{M_\rho^P(I)}
\newcommand\MspI{M_\sigma^P(I)}
\newcommand\MwpI{M_\ww^P(I)}
\newcommand\Qlqp{Q_{\preceq q}^P}
\newcommand\Qlwp{Q_{\preceq w}^P}
\newcommand\WwpI{W_\ww^P(I)}
\newcommand\appq{\begin{array}{@{}c@{}} \\[-4ex]\scriptstyle\app%
					\\[-1.6ex]q\\[-.3ex]\end{array}}
\newcommand\appw{\begin{array}{@{}c@{}} \\[-4ex]\scriptstyle\app%
					\\[-1.6ex]w\\[-.3ex]\end{array}}
\newcommand\into{\hookrightarrow}
\newcommand\onto{\twoheadrightarrow}
\newcommand\rqpP{\rho_q^{\hspace{.2ex}P'}}
\newcommand\rpqP{\rho_{p+q}^{\hspace{.2ex}P}}
\newcommand\spot{{\hbox{\raisebox{1.7pt}{\large\bf .}}\hspace{-.5pt}}}
\newcommand\void{{\{\}}}
%newcommand\defas{:=}
\newcommand\minus{\smallsetminus}
\newcommand\nothing{\varnothing}
\newcommand\appqscript{{\begin{array}{@{}c@{}}%
			\\[-4.8ex]\scriptscriptstyle\app%
			\\[-1.9ex]\scriptstyle q\\[-1ex]%
			\end{array}}}
\renewcommand\iff{\Leftrightarrow}
\renewcommand\implies{\Rightarrow}

%math symbols taking arguments
\def\ol#1{{\overline {#1}}}
\def\wh#1{{\widehat {#1}}}
\def\wt#1{{\widetilde {#1}}}
\newcommand\set[1]{\{#1\}}
\newcommand\abs[1]{|#1|}

%Math operators
\DeclareMathOperator\Hom{Hom} % Hom
\DeclareMathOperator\image{Im} % Hom
% \DeclareMathOperator\Mod{-Mod} % Q-Mod, R-Mod
\DeclareMathOperator\ann{ann} % Annihilator
\DeclareMathOperator\Ass{Ass} % Associated Primes 
\DeclareMathOperator\sat{sat} % saturation of a lattice
\DeclareMathOperator\soc{soc} % socle of a module
\DeclareMathOperator\Hull{Hull} % Hull - localization
\DeclareMathOperator\Spec{Spec} %
\DeclareMathOperator\coker{coker} % cokernel
\DeclareMathOperator\Aut{Aut} % Aut

\DeclareMathOperator\lcm{lcm} % lcm
\DeclareMathOperator\Ap{Ap} % Apery set
\DeclareMathOperator\supp{supp} % support
\DeclareMathOperator\bul{bul} % bullets
\DeclareMathOperator\mbul{mbul} % maximal bullets

\DeclareMathOperator\Char{char} % char

\DeclareMathOperator\Conv{conv} % conv
\DeclareMathOperator\Span{span} % span
\DeclareMathOperator\cone{cone} % cone
\DeclareMathOperator\Pyr{Pyr} % Pyr
\DeclareMathOperator\Bipyr{Bipyr} % Bipyr
\DeclareMathOperator\Ehr{Ehr} % Ehr

\DeclareMathOperator\Set{Set}
\DeclareMathOperator\Bij{Bij}
\DeclareMathOperator\Grp{Grp}
\DeclareMathOperator\Ab{Ab}
\DeclareMathOperator\CRing{CRing}
\DeclareMathOperator\Mod{Mod}
% \DeclareMathOperator\Vec{Vec}
\DeclareMathOperator\Top{Top}
\DeclareMathOperator\Slt{Slt}



% Replaces \atop
\newcommand{\aoverb}[2]{{\genfrac{}{}{0pt}{1}{#1}{#2}}}
%0 = displaystyle               in the 4th argument
%1 = textstyle
%2 = scriptstyle
%3 = scriptscriptstyle
\def\twoline#1#2{\aoverb{\scriptstyle {#1}}{\scriptstyle {#2}}}


\begin{document}

\begin{center}
\textbf{Spring 2022, Math 579:\ Week 0 Problem Set} \\
\textbf{Due:\ Thurday, January 26th, 2023} \\
\textbf{Proof Writing Review}
\end{center}


\bigskip
\noindent
\textbf{Homework problems.}
You must submit \emph{all} homework problems in order to receive full credit.  

\begin{enumerate}[(H1)]

\item 
Fix $n$, and suppose $A, B \subset \{1, 2, \ldots, n\}$.  Prove that $A \cap B = A \cup B$ if and only if $A = B$.  

\item 
Suppose $a_0 = 0$, $a_1 = 1$, and for all $n \ge 2$, $a_n = a_{n-1} + a_{n-2}$.  Use induction to prove 
$$a_n = \frac{1}{\sqrt 5} \, \bigg(\frac{1 + \sqrt 5}{2}\bigg)^n - \frac{1}{\sqrt 5} \, \bigg(\frac{1 - \sqrt 5}{2}\bigg)^n$$
for all $n \ge 0$.  

\item 
Locate and correct the \textbf{error} in the following proof that for any $n \in \ZZ_{\ge 0}$, there exist $q, r \in \ZZ_{\ge 0}$ with $0 \le r \le 5$ such that $n = 6q + r$.  
% in the future, several ideas here
% https://faculty.math.illinois.edu/~hildebr/347.summer19/induction-errors-sol.pdf

\begin{proof}
Let $P(n)$ denote the following statement:
\begin{center}
``There exist $q, r \in \ZZ_{\ge 0}$ with $0 \le r \le 5$ such that $n = 6q + r$.''
\end{center}
We proceed by induction on $n$.  

Base cases:\ suppose $n = 0$, $1$, $2$, $3$, $4$, or $5$.  Choosing $q = 0$ and $r = n$, we see $6q + r = n$.  This proves $P(0)$, $P(1)$, $P(2)$, $P(3)$, $P(4)$, and $P(5)$.  

Inductive step:\ supposing $n \ge 6$ and that $P(n - 6)$ holds (the \emph{inductive hypothesis}), we wish to prove $P(n)$ holds.  Since $P(n - 6)$ holds, 
$$n - 6 = 6q' + r'$$
for some $q', r' \in \ZZ$ with $0 \le r' \le 5$.  Rearranging yields 
$$n = 6(q' + 1) + r',$$
and choosing $q = q' + 1$ and $r = r' + 1$ completes the proof that $P(n)$ holds.  
% \redout{$r = r' + 1$} \makered{$r = r'$} completes the proof.  
\end{proof}
% error: extra +1 in r def

\item 
Determine whether each of the following statements is true or false.  Prove your claims.  

\begin{enumerate}
% \item 
% Suppose $a, b \in \ZZ$.  If $a + b$ and $ab$ are both even, then $a$ and $b$ are both even.  

\item 
The function $f:\RR \to \RR$ given by 
$f(x) = 9x^2 - 6x + 1$
is injective (one-to-one).  

\item 
The function $f:\ZZ \to \RR$ given by 
$f(x) = 9x^2 - 6x + 1$
is injective (one-to-one).  
% f(a) = f(b) implies 0 = 9(a - b)(a + b) - 6(a - b) = (a - b)(9(a + b) - 6) implies a + b = \tfrac{2}{3}

\end{enumerate}

\item 
Let $D = \{(a,b) : a, b \in \ZZ_{\ge 0}\}$.  
Prove that the function $f:D \to \ZZ_{\ge 0}$ given by 
$$f(a,b) = \tfrac{1}{2}(a + b)(a + b + 1) + a$$
is a bijection (that is, $f$ is one-to-one and onto).  

\end{enumerate}

\end{document}

