\documentclass[11pt]{article}
\usepackage[utf8]{inputenc}

\usepackage[margin=1in]{geometry}
\usepackage{enumitem}
\usepackage{amsmath, amssymb, amsthm}
\usepackage{xcolor}

% THEOREM ENVIRONMENTS
\theoremstyle{definition}
\newtheorem*{theorem}{{Theorem}}
\newtheorem*{lemma}{{Lemma}}
\newtheorem*{proposition}{{Proposition}}
\newtheorem*{definition}{{Definition}}
\newtheorem*{corollary}{{Corollary}}
\newtheorem*{example}{{Example}}
\newtheorem*{remark}{{Remark}}
\newtheorem*{claim}{{Claim}}
\newtheorem*{question}{{Question}}

\theoremstyle{plain}
\newtheorem*{reminder}{{\textit{Reminder}}}
\newtheorem*{hint}{{\textit{Hint}}}

% ENVIRONMENTS FOR CITING BOOK STATEMENTS
\newcommand{\prop}[1]{\paragraph{Proposition #1}}
\newcommand{\axm}[1]{\paragraph{Axiom #1}}
\newcommand{\thm}[1]{\paragraph{Theorem #1}}


% COMMANDS
\newcommand{\solution}{{\color{blue} \textsc{\ \\ Solution.\ \ }}}
\newcommand{\Z}{\mathbb{Z}} % the integers
\newcommand{\N}{\mathbb{N}} % natural numbers
\newcommand{\divides}{\ \vert \ }
\newcommand{\st}{ \ : \ } % such that

\newcommand{\exheading}[1]{\section*{Exercise #1}}
\newcounter{exnum}
% \setcounter{exnum}{1} % default 0 start
\newcommand{\exercise}{
    \stepcounter{exnum} 
    \exheading{\theexnum}
    }



%%%%
\title{MAT 108: Problem Set 3}
\author{(ADD NAME)}
\date{Due 1/31/23 at 11:59 pm on Canvas}

\begin{document}

\maketitle


\paragraph{Reminders:}
\begin{itemize}
%\item Put your name at the top!
\item Your homework submission must be typed up in full sentences, with proper mathematical formatting. 
\item Midterm Exam 1 is Wednesday, 2/1 next week. This problem set contains both regular ``graded" exercises as well as review problems for the exam. The review problems will only be graded once for completion.
\item You will receive feedback on PS2 by next Tuesday, 1/31. PS2 revisions are due Friday, 2/3 at 11:59 pm.
\end{itemize}


\paragraph{Another reminder} As with many math classes, success comes with practice. To study for the upcoming exam, I would recommend trying to prove the propositions in the textbook (only some of them were on your homework) rather than memorizing facts.  






%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\exercise 
% de morgan
\textit{(Graded, 10 points)}
Prove that $(A \cup B)^c = A^c \cap B^c$. (This is part (b) of Theorem 5.15 (De Morgan's Laws).)

\solution


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\exercise 
\textit{(Graded, 15 points)}
Let $A_1, A_2, A_3, \ldots$ be a sequence of sets. 


\begin{enumerate}[label=(\alph*)]
    \item Develop recursive definitions for 
        \[
            \bigcup_{j=1}^k A_j
            \qquad
            \text{and}
            \qquad
            \bigcap_{j=1}^k A_j.
        \]
    \item Write down and prove an analogue for Theorem 5.15 (a) for these unions and intersections.
    \item Write down and prove an analogue for Theorem 5.15 (b) for these unions and intersections.
\end{enumerate}

\solution


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\exercise 
\textit{(Graded, 10 points)}
Prove that if $a^2(b^2-2b)$ is odd, then $a$ and $b$ are (both) odd. (\emph{Hint:} Try proving the contrapositive of the statement instead.)

\solution



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\exercise 
% fibonacci proposition and induction
\textit{(Graded, 10 points)}
The Fibonacci numbers $(f_j)_{j=1}^\infty$ are defined by $f_1:= 1$, $f_2:= 1$, and the recurrence relation 
\[
    f_n = f_{n-1} + f_{n-2} \qquad \text{for }n \geq 3.
\]
%
Prove that for all $k, m \in \N$ ($m \geq 2$), 
    \[ f_{m+k} = f_{m-1} f_k + f_m f_{k+1}.\]
%
(\emph{Hint:} First decide the statements your induction argument intends to prove. 
What variable are you inducting on? 
Then, remember that the recurrence relation for Fibonacci numbers is an available and relevant tool.
You may wish to take a look at the paragraph about \emph{strong induction} in the textbook.)

\solution



\vspace{.5cm}
\hrule




%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\exercise 
\emph{(Graded once for completion, 10 points)}
Let $a_1, a_2, \ldots, a_n \in \Z$. Prove that if $\prod_{i=1}^n a_i = 0$, then for some $i$, $a_i = 0$. 

\solution



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\exercise 
\emph{(Graded once for completion, 5 points)}
Show that for all $k \in \N$, $k^4 - 6k^3 + 11 k^2 - 6k$ is divisible by $4$. 

\solution









\end{document}