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


\usepackage[utf8]{inputenc}
\title{Math 220.201 Class 11 Solutions}
\begin{document}
\maketitle

\begin{enumerate}
\item [1.] Prove that if $n\ge 2$ is a natural number and $A_1, A_2, \ldots, A_n$ are sets, then
$$\overline{A_1\cup A_2\cup \cdots \cup A_n}=\overline{A_1}\cap \overline{A_2}\cap \cdots \cap \overline{A_n}$$
\vskip 0.2in
\begin{proof} We use induction on $n$.
\begin{itemize}
\item Base case: $n=2$. This is just De Morgan's Law for sets.
\item Inductive step: $P(n)\implies P(n+1)$. Suppose that, for any $n$ sets, the complement of the union is the intersection of their complements. Now suppose we have $n+1$ sets $A_1, A_2, \ldots, A_{n+1}$. Then
$$\begin{aligned}
\overline{A_1\cup A_2\cup \cdots \cup A_n\cup A_{n+1}}&=\overline{(A_1\cup A_2\cup \cdots \cup A_n)\cup A_{n+1}}\\
&=\overline{(A_1\cup A_2\cup \cdots \cup A_n)}\cap \overline{A_{n+1}}\\
&=(\overline{A_1}\cap \overline{A_2}\cap \cdots \cap \overline{A_n}) \cap \overline{A_{n+1}}\\
&=\overline{A_1}\cap \overline{A_2}\cap \cdots \cap \overline{A_n} \cap \overline{A_{n+1}}
\end{aligned}$$
The second step holds by $P(2)$ and the third step holds by $P(n)$.
\end{itemize}
\end{proof}
\vskip 0.2in
\item [2.] Prove that for every integer $n\ge 5$, $2^n>n^2$.
\vskip 0.2in
\begin{proof}
We use induction on $n$.
\begin{itemize}
\item Base case: $n=5$. This is the statement that $2^5>5^2$, i.e. $32>25$.
\item Inductive step: $P(n) \implies P(n+1)$. Suppose that $2^n>n^2$. We want to show that $2^{n+1}>(n+1)^2$. It is sufficient for us to show that $2^{n+1}-2^n > (n+1)^2-n^2$, i.e. to show that $2^n>2n+1$. This is true because
$$2^n>n^2>3n>2n+1$$
The first inequality is by the inductive hypothesis, and the second inequality is because $n>3$, and the third inequality because $n>1$. Therefore, $2^{n+1}>(n+1)^2$ and this completes the induction.
\end{itemize}
\end{proof}
\emph{Note:} In the inductive step, we showed that the left side increases more than the right side. We could have instead proved that $\frac{2^{n+1}}{2^n}>\frac{(n+1)^2}{n^2}$. Simplifying both sides, this becomes $2>\left(1+\frac{1}{n}\right)^2$ - this is true for $n=5$, and it therefore is true for all larger $n$ as well.
\vskip 0.2in
\item [3.] Prove that for every positive odd integer $n$, $5|4^n+1$.
\vskip 0.2in
\begin{proof}
Any odd integer $n$ can be written in the form $n=2k+1$ for some integer $k$. If $n$ is positive, then this means $k\ge 0$. So it is equivalent to prove that for every integer $k\ge 0$, $5|4^{2k+1}+1$. We prove this by induction on $k$.
\begin{itemize}
\item Base Case: $k=0$. $4^1+1=5$ so the divisibility clearly holds.
\item Inductive step: Suppose that $5|4^{2k+1}+1$. We wish to show that $5|4^{2(k+1)+1}+1$, that is, $5|4^{2k+3}+1$. By the inductive hypothesis, $4^{2k+1}\equiv -1\pmod{5}$, and therefore
$$4^{2k+3}=4^{2k+1}\cdot 4^2 \equiv (-1) \cdot 1\pmod{5} \equiv -1\pmod{5}$$
and therefore, $5|4^{2k+3}+1$, which completes the induction.
\end{itemize}
\end{proof}
\vskip 0.2in
\item [4.] Prove that every natural number $n \ge 8$ can be written in the form $n=5a+3b$ where $a, b$ are nonnegative integers.
\vskip 0.2in
\begin{proof} [Proof 1]
Let the described property be denoted by $P(n)$. We will show that $P(8), P(9),$ and $P(10)$ are all true, and then prove that $P(n)\implies P(n+3)$ for all $n\ge 8$. This will separately show that $P(8+3k), P(9+3k),$ and $P(10+3k)$ hold for all nonnegative integers $k$, thereby proving $P(n)$ for all $n\ge 8$.
\begin{itemize}
\item Base case: $n=8, 9, 10$. $8=5(1)+3(1)$, $9=5(0)+3(3)$, $10=5(2)+3(0)$.
\item Inductive step: suppose that $n=5a+3b$ for some nonnegative integers $a, b$. Then $n+3=5a+3(b+1)$. $b+1$ is also a nonnegative integer, so this implies $P(n+3)$. This completes the induction.
\end{itemize}
\end{proof}
\begin{proof}[Proof 2]
Let $P(n)$ denote the property described above, and let $Q(n)=P(n)\land P(n+1)\land P(n+2)$. That is, $Q(n)$ is the property that $n, n+1, n+2$ can all be written in the given form. We will prove $\forall n\ge 8, Q(n)$ by induction on $n$.
\begin{itemize}
\item Base case: $n=8$. $8=5(1)+3(1)$, $9=5(0)+3(3)$, $10=5(2)+3(0)$.
\item Inductive step: Suppose that $Q(n)$ is true: namely, that $n=5a+3b$, $n+1=5c+3d$, $n+2=5e+3f$. We must show that $n+1, n+2,$ and $n+3$ have the required property $P$. By assumption, $n+1=5c+3d$, $n+2=5e+3f$, and $n+3=5a+3(b+1)$. Thus, $Q(n+1)$ is true, which completes the induction.
\end{itemize}
\end{proof}
\vskip 0.2in
\item [5.] Consider the following statement.
\begin{center}
For every integer $k\ge 5$, there exists a natural number $N$ such that for every integer $n\ge N$, $2^n>n^k$.
\end{center}
\begin{enumerate}
\item What is wrong with the following argument disproving the statement?
\begin{proof}
Suppose there is such an $N$. Then for every $k\ge 5$ and every $n\ge N$, we have $2^n>n^k$. This means $\log_n(2^n)>k$. But this doesn't hold when $k\ge \log_n(2^n)$. This is a contradiction!
\end{proof}
\vskip 0.2in
{\bf Solution:} The statement is saying that $N$ can be chosen dependent on $k$, whereas the proof is assuming that $N$ is chosen \emph{independent} of $k$. The reason $N$ is dependent on $k$, is that the part quantifying $N$ is inside the sentence quantified by $k$.
$$\forall k\ge 5, (\exists N\in\mathbb{N}, (\forall n\ge N, (2^n>n^k)))$$

\vskip 0.2in
\item I think there is a better way to name the variables:
\begin{center}
For every integer $k\ge 5$, there exists a natural number $N_k$ such that for every integer $n\ge N_k$, $2^n>n^k$.
\end{center}
Why is this better? {\bf This reminds us that the value of $N$ that is chosen is dependent on what $k$ is.}
\vskip 0.2in
\item Can you prove the statement? (This is challenging and may require multiple steps! Hint: base case $N_k=2^k$.)
\end{enumerate}
\vskip 0.2in
\begin{proof}
For each $k\ge 5$, let $N_k=2^k$. We prove that, for all $n\ge 2^k$, $2^n>n^k$ by induction on $n$.
\begin{itemize}
\item Base case: $n=2^k$. We must check that, for each $k\ge 5$, $2^{(2^k)}>(2^k)^k$. But $(2^k)^k=2^{(k^2)}$. The inequality $2^{(2^k)}>2^{(k^2)}$ for $k\ge 5$ now follows because we proved in Q2 that $2^k>k^2$ for $k\ge 5$.
\item Inductive step: Suppose that $2^n>n^k$. We must show that $2^{n+1}>(n+1)^k$. It is sufficient to show that $\frac{2^{n+1}}{2^n}>\frac{(n+1)^k}{n^k}$, as then we have that
$$2^{n+1}=2^n\cdot \frac{2^{n+1}}{2^n}>2^n\cdot \frac{(n+1)^k}{n^k}=\frac{2^n}{n^k}\cdot (n+1)^k> (n+1)^k$$
So let's show that $\frac{2^{n+1}}{2^n}>\frac{(n+1)^k}{n^k}$. Simplifying both sides, it is equivalent to show that $2>\left(1+\frac{1}{n}\right)^k$. Since $n\ge 2^k$, it is sufficient to show that $2>\left(1+\frac{1}{2^k}\right)^k$. When we expand the binomial product on the right hand side, we get $2^k$ terms: one of them is equal to $1$, and every other term is at most $\frac{1}{2^k}$. Therefore, the right hand side is at most $1+\frac{2^k-1}{2^k}=2-\frac{1}{2^k}$. Therefore, the inequality $2>\left(1+\frac{1}{2^k}\right)^k$ holds, and this proves that the induction holds.
\end{itemize}
\end{proof}

\end{enumerate}
\end{document}