\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 PS03} \author{Melissa Zhang} \date{Due Monday, April 20, 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 Continue developing experience with proofs by induction. \item Practice the basics of logic. \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 in very specific circumstances which we will discuss in class). \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 What's wrong with the following argument? \begin{claim} All cats are the same color. \end{claim} \begin{proof} Let $P(k)$ be the statement that all cats in a set of $k$ cats are the same color. (Base case.) All cats in a set of 1 cat are the same color. (Induction step.) Assume that $P(k)$ is true, i.e.\ all cats in any set of $k$ cats are the same color. Now consider a set of $k+1$ cats, indexed by $1,2,3, \ldots,k,k+1$. By the induction hypothesis, the first $k$ of these cats are the same color, and also, the last $k$ of these cats are the same color. Because the sets of the first $k$ and last $k$ cats overlap, all $k+1$ cats must be the same color. Hence all $k+1$ cats are the same color. Thus by induction, any subset of $k$ cats are the same color. In particular, any two cats must be the same color, so all cats are the same color. \end{proof} \begin{example}[Counterexample to the claim] One of my cats is tabby, and the other is a cow cat: \begin{center} \includegraphics[width=.5\textwidth]{images/my-cats.png} \end{center} \end{example} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \exercise Consider the following sum: \[ S_n := \frac{1}{2} + \frac{1}{4} + \cdots + \frac{1}{2^n} \] \bea \item Conjecture a formula for the sum $S_n$, and write down the statement of your conjecture in the form ``For all $n \in \N$, $P(n)$ is true.'' (What is the statement $P(n)$ in this case?) \item Prove your conjecture. \ee %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \exercise In this exercise, you will prove the validity various modified versions of mathematical induction. \begin{hint} Read the proof of Theorem 2.25 in the book to see how we can use the original meta-theorem to prove a different version of mathematical induction. \end{hint} \bea \item Use the Well-Ordering Principle to prove the following theorem: \begin{theorem} Let $P(k)$ be a statement depending on a variable $k \in \N$. In order to prove the statement \begin{center} ``$P(k)$ is true for all $k \in \N$,'' \end{center} it suffices to prove the following: \bei \item $P(1)$ and $P(2)$ are true and \item for each $n \in \N$, if $P(n)$ and $P(n+1)$ are true, then $P(n+2)$ is true. \ee \end{theorem} \item Let $ m\in \Z$ be a fixed integer. Prove that, in order to prove $P(k)$ is true for all $k \geq m$, it suffices to prove the following: \bei \item $P(m)$ and $P(m+1)$ are true, and \item for each $n \geq m$, if $P(n)$ and $P(n+1)$ are both true, then $P(n+2)$ is also true. \ee \ee %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \exercise Build a truth table to show that the contrapositive to the implication ``$P \implies Q$'' is logically equivalent to ``$P \implies Q$.'' %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \exercise (This exercise will be graded for completion; I will post solutions.) (Project 3.7) Negate the following statements. \bea \item Every cubic polynomial has a real root. \item $G$ is normal and $H$ is regular. \item $\exists ! \ 0$ such that $\forall x$, $x+0 =x$. \item The newspaper article was neither accurate nor entertaining. \item If $\gcd(m,n)$ is odd, then $m$ or $n$ is odd. \item $H/N$ is a normal subgroup of $G/N$ if and only if $H$ is a normal subgroup of $G$. \item For each $\varepsilon >0$, there exists $N \in \N$ such that, for all $n \geq N$, $|a_n - L| < \varepsilon$. \ee %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \exercise (This exercise will be graded for completion; I will post solutions.) Write down the inverse, converse, and contrapositive of the following implications. \bea \item If I have three arms, then the sky is blue. \item If we can find two cats that are the same color, then all cats are the same color. \item I wear boots only when it rains. \ee \end{document}