\documentclass[12pt]{amsart} % Document type

% There is a lengthy top section...
% Copy and paste this into a new .tex file.
% Begin typing at the bottom of this document.

%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%
%
% Various add-ons that allow for greater customization of the document. Not all are necessary.

%\usepackage[T1]{fontenc} % Output encoding (suggested when text contains accented letters)
%\usepackage[utf8]{inputenc} % Input encoding (important when writing in foreign languages)
\usepackage[margin =.5in]{geometry} % Set page dimensions
\usepackage{parskip} % Custom paragraph spacing
\usepackage{changepage} % Change page layout
\usepackage{setspace} % Allow for double-spacing using \doublespace
\usepackage{multicol} % Allows multiple columns on a page
\usepackage{mathtools,amssymb,amsfonts,amsthm} % Variety of useful things for math
\usepackage{euscript,mathrsfs,bbm} % Some additional fonts
\usepackage{color} % Color
\usepackage[usenames,dvipsnames,svgnames,table]{xcolor} % Extra colors

\usepackage{comment} % Customizable comment environments
\usepackage{newverbs} % Customizable verbatim environments
\usepackage{enumitem} % Customizable enumerate environments
\usepackage{tabularx} % Greater flexibility with tables
\usepackage{multirow} % Table elements span multiple rows

\usepackage{graphicx} % For inserting images
\usepackage{wrapfig} % Wrap text around figures
\usepackage{url} % For inserting urls
\usepackage[linktoc=all,colorlinks=true,linkcolor=blue,urlcolor=Purple,citecolor=cyan]{hyperref} % Internal and external links
\usepackage[all]{hypcap} % Image captions (requires hyperref)
\usepackage{pdfpages} % Insert pdfs
\usepackage{tikz} % For drawing pictures
    \usetikzlibrary{petri}
    \usetikzlibrary{trees}
%\usepackage[all]{xy} % Matrix-like diagrams
\raggedbottom
\allowdisplaybreaks

%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%
%
% Custom comment environments and various editing macros
% Comments can be turned off using \excludecomment{ }

\specialcomment{lecturenotes}{}{}\excludecomment{lecturenotes}
\specialcomment{answers}{ \textsc{Answer: }}{}
\specialcomment{remarks}{

\vspace{2mm}\noindent
\begin{adjustwidth}{5mm}{0mm}
\begingroup\color{blue}
}
{
\endgroup
\end{adjustwidth}

\vspace{2mm}
}
\specialcomment{inremarks}{\begingroup\color{blue}}{\endgroup}
\newcommand{\ctypo}[1]{\colorbox{yellow}{#1}\hspace{-1mm}}
\newcommand{\ctex}[1]{\colorbox{Gold}{#1}}
\newcommand{\period}{\colorbox{cyan!50}{.}}
\newcommand{\comma}{\colorbox{cyan!50}{,}}

\newverbcommand{\cverb}{\small\color{purple}}{}
\newverbcommand{\everb}{\small\color{blue}}{}

%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%
%
% Custom column types for tabularx

\newcolumntype{L}[1]{>{\hsize=#1\hsize\raggedright\arraybackslash}X}
\newcolumntype{R}[1]{>{\hsize=#1\hsize\raggedleft\arraybackslash}X}
\newcolumntype{C}[1]{>{\hsize=#1\hsize\centering\arraybackslash}X}

%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%
%
% Custom spacing commands

\begingroup
    \makeatletter
    \@for\theoremstyle:=definition,remark,plain\do{%
        \expandafter\g@addto@macro\csname th@\theoremstyle\endcsname{%
            \addtolength\thm@preskip\parskip
            }%
        }
\endgroup

\newcommand{\sss}{\vspace{2 mm}\noindent}
\newcommand{\lss}{\vspace{5 mm}\noindent}
\newcommand{\lls}{\vspace{7 mm}\noindent}
\newcommand{\ds}{\displaystyle}
\newcommand{\HR}{\vspace{5pt}\hrule height 1pt \vspace{5pt}}
\newcommand{\atext}[1]{\text{\quad #1\quad}}
%\newcommand\Tstrut{\rule{0pt}{2.6ex}}         % = `top' strut
%\newcommand\Bstrut{\rule[-1ex]{0pt}{0pt}}   % = `bottom' strut

%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%
%
% Shortcuts for commonly used symbols

\newcommand{\ca}{\mathcal}
\newcommand{\fr}{\mathfrak}
\newcommand{\eucal}{\EuScript}
\newcommand{\scr}{\mathscr}
\newcommand{\bbf}{\mathbb{F}}
\newcommand{\bbn}{\mathbb{N}}
\newcommand{\bbr}{\mathbb{R}}
\newcommand{\bbq}{\mathbb{Q}}
\newcommand{\bbc}{\mathbb{C}}
\newcommand{\bbz}{\mathbb{Z}}
\newcommand{\bbp}{\mathbb{P}}
\newcommand{\bfa}{\mathbf{a}}
\newcommand{\bfb}{\mathbf{b}}
\newcommand{\bfc}{\mathbf{c}}
\newcommand{\bfu}{\mathbf{u}}
\newcommand{\bfv}{\mathbf{v}}
\newcommand{\bfx}{\mathbf{x}}
\newcommand{\ring}{\ca O}

\newcommand{\inv}{^{-1}}
\newcommand{\into}{\hookrightarrow}
\newcommand{\onto}{\twoheadrightarrow}
\newcommand{\isom}{\overset{\sim}{\to}}
\renewcommand{\iff}{\Leftrightarrow}
\renewcommand{\implies}{\Rightarrow}
\renewcommand{\impliedby}{\Leftarrow}
\newcommand{\contradiction}{\Rightarrow\Leftarrow}

%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%
%
% Shortcuts for matrices and vectors

\newcommand{\bmat}[1]{\begin{bmatrix}#1\end{bmatrix}}
\newcommand{\pmat}[1]{\begin{pmatrix}#1\end{pmatrix}}
\newcommand{\vmat}[1]{\begin{vmatrix}#1\end{vmatrix}}
\newcommand{\floor}[1]{\lfloor #1 \rfloor}
\newcommand{\Floor}[1]{\left\lfloor #1 \right\rfloor}
\newcommand{\vect}[1]{\langle #1 \rangle}

%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%
%
% Custom function names

\newcommand{\Ad}{\operatorname{Ad}}
\newcommand{\ad}{\operatorname{ad}}
\newcommand{\disc}{\operatorname{disc}}
\newcommand{\domain}{\operatorname{domain}}
\newcommand{\Id}{\operatorname{Id}}
\newcommand{\im}{\operatorname{im}}
\newcommand{\ind}{\operatorname{ind}}
\newcommand{\nul}{\operatorname{Nul}}
\newcommand{\nullity}{\operatorname{nullity}}
\newcommand{\ord}{\operatorname{ord}}
\newcommand{\proj}{\operatorname{proj}}
\newcommand{\rank}{\operatorname{rank}}
\newcommand{\red}{\operatorname{red}}
\newcommand{\bbref}{\operatorname{rref}}
\newcommand{\tr}{\operatorname{tr}}
\newcommand{\trunc}{\operatorname{Trunc}}
\newcommand{\vspan}{\operatorname{span}}

%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%
%
% Environment styles

\newtheorem{thm}{Theorem}[section]
\newtheorem{prop}[thm]{Proposition}
\newtheorem{cor}[thm]{Corollary}
\newtheorem{lem}[thm]{Lemma}
\newtheorem*{prop*}{Proposition}
\newtheorem*{cor*}{Corollary}
\newtheorem*{lem*}{Lemma}
\newtheorem*{thm*}{Theorem}

\theoremstyle{definition}
\newtheorem{conj}[thm]{Conjecture}
\newtheorem{defn}[thm]{Definition}
\newtheorem{claim}[thm]{Claim}
\newtheorem{example}[thm]{Example}
\newtheorem*{conj*}{Conjecture}
\newtheorem*{defn*}{Definition}
\newtheorem*{rd}{Read from the text}
\newenvironment{answer}{\noindent\textsc{Answer:}}{\hfill $\square$}

\newcounter{homework}
\newtheorem{hw}[homework]{Homework}
\newcounter{exercise}[homework]
\newtheorem{exer}[exercise]{Exercise}
\renewcommand{\theexercise}{\arabic{homework}.\arabic{exercise}}

\theoremstyle{remark}
\newtheorem{remark}[thm]{Remark}
\newtheorem*{remark*}{Remark}
\newtheorem{notation}[thm]{Notation}

\renewcommand{\theexercise}{\arabic{exercise}}

\title{Math 2001 \\ Proofs by induction}

\begin{document}
\maketitle

Some of the problems from yesterday's sheet are included on this one.

\subsection*{Arithmetic}

\begin{enumerate}[label={\arabic*.)}]
\setlength{\itemsep}{2mm}
\item Prove that $\ds\sum_{i=1}^n i = \frac{n(n+1)}{2}$ for every integer $n \ge 1$.

\item Prove that $\ds\sum_{i=0}^n 2^i = 2^{n+1}-1$ for every integer $n \ge 0$.

\item Let $a_1, a_2, a_3, \dotsc$ be a sequence of integers where $a_1 = 3$, $a_2 = 1$, and $a_n = a_{n-1}+a_{n-2}$ for each integer $n \ge 4$. Prove that $1 \le \ds\frac{a_n}{a_{n-1}} \le 2$ for each $n \ge 4$.
\end{enumerate}

\subsection*{Sets}

\begin{enumerate}[label={\arabic*.)}]
\setcounter{enumi}{3}
\item Suppose that $A_1, A_2, A_3, A_4, \ldots$ is an infinite sequence of non-empty, nested sets. That is,
\begin{align*}
A_1 \supseteq A_2 \supseteq A_3 \supseteq \cdots
\end{align*}
and each $A_i$ is non-empty. 
\begin{enumerate}
\item Prove that $\bigcap_{i=1}^N A_i$ is non-empty for every $N \in \bbn$. 

\item Is the set $\bigcap_{i=1}^\infty A_i$ empty or non-empty? 

If possible, give an example where $\bigcap_{i=1}^\infty A_i$ is empty. 

If possible, give an example where $\bigcap_{i=1}^\infty A_i$ is non-empty.
\end{enumerate}

\item 
\begin{enumerate}
\item Prove the finite versions of de Morgan's laws by induction.
\begin{multicols}{2}
\begin{enumerate}
\item $\ds \overline{\bigcap_{1 \le i \le N} A_i} = \bigcup_{1 \le i \le N} \overline A_i$.
\item $\ds \overline{\bigcup_{1 \le i \le N} A_i} = \bigcap_{1 \le i \le N} \overline{A_i}$.
\end{enumerate}
\end{multicols}

\vspace{-4mm}
\item Let $A_1, A_2, A_3, \ldots$ be an infinite sequence of sets. Explain why induction cannot be used to prove the next two statements. 
\begin{multicols}{2}
\begin{enumerate}
\item $\ds \overline{\bigcap_{i \in \bbn} A_i} = \bigcup_{i \in \bbn} \overline A_i$.
\item $\ds \overline{\bigcup_{i \in \bbn} A_i} = \bigcap_{i \in \bbn} \overline{A_i}$.
\end{enumerate}
\end{multicols}

\vspace{-4mm}
Prove these ``infinite" versions of de Morgan's laws using a method other than induction. In fact, these statements are true for arbitrary unions and intersections. Your proofs for (i) and (ii) should also work for (iii) and (iv). (You don't need to write the proofs twice.)

\begin{multicols}{2}
\begin{enumerate}
\setcounter{enumiii}{2}
\item $\ds \overline{\bigcap_{\lambda \in \Lambda} A_i} = \bigcup_{\lambda \in \Lambda} \overline A_i$
\item $\ds \overline{\bigcup_{\lambda \in \Lambda} A_i} = \bigcap_{\lambda \in \Lambda} \overline{A_i}$.
\end{enumerate}
\end{multicols}
\end{enumerate}
\end{enumerate}

\subsection*{Topology.}

\begin{enumerate}[label={\arabic*.)}]
\setcounter{enumi}{5}
\item 
\begin{enumerate}
\item Prove that a finite intersection of open sets is open. That is, prove that $\bigcap_{i=1}^N A_i$ is open if each $A_i$ is open (and $N \in \bbn$). (c.f. Proof 13)

\item Give an example of an infinite intersection of open sets that is not open. (Hint: Proof ??)

\item Prove that a finite union of closed sets is closed. That is, prove that $\bigcup_{i=1}^N A_i$ is closed if each $A_i$ is closed. (Hint: de Morgan's laws.)

\item Give an example of a infinite intersection of closed sets that is not closed.
\end{enumerate}

\item 
\begin{enumerate}
\item Prove that a union of arbitrarily many open sets is open. That is, prove that $\bigcup_{\lambda \in \Lambda} A_\lambda$ is open if each $A_\lambda$ is open.

\item Prove that the intersection of arbitrarily many closed sets is closed.
\end{enumerate}

\end{enumerate}

\subsection*{Functions}

\begin{enumerate}[label={\arabic*.)}]
\setcounter{enumi}{7}
\item Let $f \colon A \to A$ be a bijection. Prove that $f^n\colon A \to A$ is a bijection. [Hint: functions worksheet.]

Here, $f^n$ denotes the $n$-fold composition of $f$ with itself. That is, $f^2(x) = f(f(x))$, $f^3(x) = f(f(f(x)))$, etc. In general, $f^{n+1}(x) = f(f^n(x))$.

\item Let $f \colon \bbr \to \bbr$ be a function with the property that $|f(b) - f(a)| < \frac{1}{2}|b-a|$ for all $a,b \in \bbr$. Prove that $|f^n(b) - f^n(a)| < \frac{1}{2^n}|b-a|$ for all $a,b \in \bbr$.
\end{enumerate}

\subsection*{Critique the following proof}

\begin{thm*}
All horses are the same color. 
\end{thm*}

\vspace{-5mm}
\begin{spacing}{1.5}
\begin{proof}
We prove the result by induction by showing that in every collection of $n$ horses, all the horses have the same color. 

For the base case, let $n=1$. If there is only one horse, then there is only one color (e.g. blue). Thus in every set of $1$ horses, every horse in that set has the same color as all other horses in that set.

For the induction step, suppose there is an $n$ for which in every collection of $n$ horses, all the horses have the same color. Select any $n$ of the horses on Earth, then as we now have $n$ horses, all of these horses have the same color. For simplicity, let's say that they are all blue. Remove one horse from this collection (leaving $n-1$ blue horses) and add to this set any horse on Earth that was not previously selected. We now have a new set of $n$ horses, and therefore they all have the same color. In particular, the newly selected horse is blue as it has the same color as the other $n-1$ horses, which we already know to be blue. Bring back the blue horse that we initially removed, and we now have $n+1$ blue horses. This completes the induction step.

Finally, as the number of horses on Earth is finite, we can induct up to that number and conclude that all horses are the same color. 
\end{proof}
\end{spacing}
\end{document}