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

\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}
    }

\newcommand{\bea}{\begin{enumerate}[label=(\alph*)]}
\newcommand{\bei}{\begin{enumerate}[label=(\roman*)]}
\newcommand{\ee}{\end{enumerate}}

\renewcommand{\implies}{\Rightarrow} % shorter implies arrow


\newcommand{\mz}[1]{{\color{magenta} #1}} % mz comments to self


\title{MAT 108 PS04}
\author{Melissa Zhang}
\date{Due Monday, April 27, 2026 at 9:00 pm on Gradescope}

\begin{document}

\maketitle


\section*{Instructions}

There are three goals for this problem set:
\begin{itemize}
    \item Maintain good mathematical writing form and best practices for proof-writing.
    \item Practice constructing and working with recursively defined sequences.
    \item Build familiarity with set notation and basic set operations.
\end{itemize}


\noindent Here are some reminders about best practices:
\begin{itemize}
    \item You absolutely must write in full, connected English sentences. Whenever possible, do not start a sentence with mathematical symbols. Do not use symbols like $\implies$, $\forall$, $\exists$, $\therefore$, etc.\ (except when explicitly discussing statements about logic). 
    \item Your solution must be \emph{neat}. You \textbf{will} be graded on style, which includes  mathematical style and professionalism. 
    \item It is your responsibility to mark where your solutions for each problem begins on Gradescope so that the TA and reader can properly grade your solutions. 
\end{itemize}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\exercise
(This exercise will not be graded.) 
Read Chapter 4. In particular:
\bea
\item Skim over and note the propositions that allow us to work with summation and product notation. I will assume you know how to work with this notation.
\item Carefully read over the induction proofs, e.g.\ for the binomial theorem. Would you be able to reproduce them without referencing the book?
\ee


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\exercise

\emph{This exercise is challenging---don't get discouraged. Hints are provided below.}

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.
\]
%
{Without appealing to Proposition 4.29}, prove Proposition 4.30:
\begin{proposition}
    For all $k, m \in \N$ ($m \geq 2$), 
    \[ f_{m+k} = f_{m-1} f_k + f_m f_{k+1}.\]
\end{proposition}

%
\noindent Here are some hints:
\begin{itemize}
    \item First decide the statements your induction argument intends to prove. 
    What variable are you inducting on? 
    \item 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.
    \item Within my solution, I prove the following two equations hold (with appropriate restrictions on the range of values for $k$ and $m$):
        \begin{equation}
        \label{eq:m+1}
            f_{(m+1) + k} = f_mf_k + f_{m+1}f_{k+1}
        \end{equation}
        \begin{equation}
        \label{eq:k+1}
            f_{m +(k+1)} = f_{m-1}f_{k+1} + f_m f_{k+2}.
        \end{equation}
\end{itemize}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\exercise

\begin{theorem}[Theorem 5.15, DeMorgan's Laws]
Given two subsets $A,B \subseteq X$, 
\begin{enumerate}
    \item[(i)] $(A \cap B)^c = A^c \cup B^c$ \quad and
    \item[(ii)] $(A \cup B)^c = A^c \cap B^c$.
\end{enumerate}
\end{theorem}

Below is an example proof of (i). Notice that in order to prove a set equality, we prove double inclusion. You can draw a Venn diagram to help you conceptualize the equality, but remember that the picture is not a sufficient proof; a proper proof in this course requires explicit justification.

\begin{proof}[Proof of (i)]

We first show that $(A \cap B)^c \subseteq A^c \cup B^c$.
Suppose $x \in (A \cap B)^c$, meaning that $x \not\in A \cap B$, i.e.\ $x$ is not in both $A$ and $B$. 
Then $x$ is either not in $A$ or not in $B$, so $x \in A^c$ or $x \in B^c$, i.e.\ $x \in A^c \cup B^c$. 

Conversely, suppose $x \in A^c \cup B^c$, so that $x \in A^c$ or $x \in B^c$, meaning $x \not\in A$ or $x \not\in B$. Of the four possiblities ($x \in$ or $\not \in A$, together with the information of whether $x \in$ or $\not\in B$), only $x \in A \cap B$ cannot be true. Therefore $x \in (A \cap B)^c$.
\end{proof}

\begin{remark}
    In English, `i.e.' stands for `id est' (from Latin), meaning `that is'. So, correct usage would usually place a comma after. However, in my experience, mathematicians tend to skip the comma, since we use the term so often, usually to rephrase a technical statement in a different way. 

    The same is true for `e.g.', which means `for example'. As long as you use these Latin abbreviations in the right context (do not confuse `i.e.' with `e.g.'), I don't care whether you use a comma or not.
\end{remark}


\bea
\item Prove part (ii) of DeMorgan's Laws.
\item Let $A_1, A_2, \ldots, A_n$ (for $n \in \N$) be subsets of $X$. Write down \textbf{recursive} definitions for the sets
\[
    \bigcup_{i=1}^n A_i
    \qquad
    \text{and}
    \qquad
    \bigcap_{i=1}^n A_i. 
\]
\item Write down \textbf{and prove} a version of DeMorgan's Laws for $\bigcup_{i=1}^n A_i$ and $\bigcap_{i=1}^n A_i$. 
\ee



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\exercise 
Let $A,B,C,D$ be sets. Decide whether each of the following statements is true or false; in each case, either prove the statement or give a counterexample.

(As you saw on the previous problem set, a \textit{counterexample} to a statement is an example that proves the statement is false.)

\begin{enumerate}[label=(\alph*)]
    \item $A - (B \cup C) = (A - B) \cup (A-C)$
    \item $(A \times B) \cup (C \times D) = (A \cup C) \times (B\cup D)$
    \item $(A \times B) \cap (C \times D) = (A \cap C) \times (B\cap D)$
\end{enumerate}




\end{document}