\documentclass[11pt]{amsart}
\usepackage{geometry}                % See geometry.pdf to learn the layout options. There are lots.
\geometry{letterpaper}                   % ... or a4paper or a5paper or ... 
\usepackage{amsfonts, amscd, amssymb, amsthm, amsmath, multicol, enumerate}
\usepackage{pdfsync}%leaves makers for tex searching

%%%%% Margins %%%%% 
\setlength{\topmargin}{1in} %top/bot margins
\setlength{\oddsidemargin}{\topmargin} %sidemargins

\setlength{\textheight}{11in} \setlength{\textwidth}{8.5in}
\setlength{\hoffset}{-1in} \setlength{\voffset}{-1in} \setlength{\evensidemargin}{\oddsidemargin} \addtolength{\textheight}{-2 \topmargin}\addtolength{\textwidth}{-2\oddsidemargin}\setlength{\headheight}{0pt} \setlength{\headsep}{20pt} \setlength{\footskip}{20pt}\addtolength{\textheight}{-\footskip} \addtolength{\textheight}{-\headheight} \addtolength{\textheight}{-\headsep}


%%% Environments %%%--------------------------------------------------------- 
\newenvironment{ans}{\medskip \paragraph*{\emph{Answer}.}}{\hfill \break \rule{1.5cm}{0.4pt} \medskip }
\newenvironment{sketch}{\medskip \paragraph*{\emph{Proof sketch}.}}{ \medskip }
\newenvironment{summary}{\medskip \paragraph*{\emph{Summary}.}}{  \hfill \break  \rule{1.5cm}{0.4pt} \medskip }
\newcommand\Ans[1]{\hfill \emph{Answer:} {#1}}

%%%%% Theorems %%%%% 
\theoremstyle{plain}
	\newtheorem{thm}{Theorem}
	\newtheorem{lem}[thm]{Lemma}
	\newtheorem{prop}[thm]{Proposition}
	\newtheorem{cor}[thm]{Corollary}


%%% Pictures %%%--------------------------------------------------------- 
\usepackage{tikz}
\usepackage{pgfplots}
\usepackage[pdftex,bookmarks]{hyperref}
\usetikzlibrary{scopes}
\usepgflibrary{shapes.geometric}
\tikzstyle{V}=[draw, fill =black, circle, inner sep=0pt, minimum size=2pt]
\tikzstyle{bV}=[draw, fill =black, circle, inner sep=0pt, minimum size=4pt]
\tikzstyle{over}=[draw=white,double=black,line width=3pt]

\newcommand\TikZ[1]{\begin{matrix}\begin{tikzpicture}#1\end{tikzpicture}\end{matrix}}



%%% Color  %%%--------------------------------------------------------------
\usepackage{color}
\definecolor{dred}{rgb}{.65, 0, 0.15}
\newcommand{\NOTE}[1]{{\color{blue}#1}}

%%% Alphabets %%%--------------------------------------------------------
\def\cA{\mathcal{A}}\def\cB{\mathcal{B}}\def\cC{\mathcal{C}}\def\cD{\mathcal{D}}\def\cE{\mathcal{E}}\def\cF{\mathcal{F}}\def\cG{\mathcal{G}}\def\cH{\mathcal{H}}\def\cI{\mathcal{I}}\def\cJ{\mathcal{J}}\def\cK{\mathcal{K}}\def\cL{\mathcal{L}}\def\cM{\mathcal{M}}\def\cN{\mathcal{N}}\def\cO{\mathcal{O}}\def\cP{\mathcal{P}}\def\cQ{\mathcal{Q}}\def\cR{\mathcal{R}}\def\cS{\mathcal{S}}\def\cT{\mathcal{T}}\def\cU{\mathcal{U}}\def\cV{\mathcal{V}}\def\cW{\mathcal{W}}\def\cX{\mathcal{X}}\def\cY{\mathcal{Y}}\def\cZ{\mathcal{Z}}

\def\AA{\mathbb{A}} \def\BB{\mathbb{B}} \def\CC{\mathbb{C}} \def\DD{\mathbb{D}} \def\EE{\mathbb{E}} \def\FF{\mathbb{F}} \def\GG{\mathbb{G}} \def\HH{\mathbb{H}} \def\II{\mathbb{I}} \def\JJ{\mathbb{J}} \def\KK{\mathbb{K}} \def\LL{\mathbb{L}} \def\MM{\mathbb{M}} \def\NN{\mathbb{N}} \def\OO{\mathbb{O}} \def\PP{\mathbb{P}} \def\QQ{\mathbb{Q}} \def\RR{\mathbb{R}} \def\SS{\mathbb{S}} \def\TT{\mathbb{T}} \def\UU{\mathbb{U}} \def\VV{\mathbb{V}} \def\WW{\mathbb{W}} \def\XX{\mathbb{X}} \def\YY{\mathbb{Y}} \def\ZZ{\mathbb{Z}}  

\def\ii{\mathbf{i}}\def\jj{\mathbf{j}}\def\kk{\mathbf{k}}\def\uu{\mathbf{u}}\def\vv{\mathbf{v}}\def\ww{\mathbf{w}}

\def\<{\langle} \def\>{\rangle}
\def\half{\hbox{$\frac12$}}
\def\id{\mathrm{id}}
\def\img{\mathrm{img}}
\def\vep{\varepsilon}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\def\HW{8}
\def\DUE{11/6/2018}
\def\NAME{YOUR NAME HERE}
\title[Homework \HW]{Homework \HW\\
Math 308\\
\small Due: \DUE}
\author{}
%\date{}                                           % Activate to display a given date or no date

\begin{document}
%\maketitle %Comment out this line, and uncomment the following for your assignment:
\begin{flushright}
\NAME\\
Math 308\\
Homework \HW\\
\DUE
\end{flushright}


\begin{enumerate}[1.]
\item Show the following using proof by cases.
\begin{enumerate}[(a)]
\item The square of any integer is of the form $3k$ or $3k + 1$ for some $k \in \ZZ$.

%\begin{proof}
%\end{proof}


\item For all $x, y\in\RR$, we have \\ \smallskip
\centerline{$\displaystyle
	|xy| = |x| |y| \qquad \text{ and } \qquad \big| |x| - |y| \big| \leq |x - y|. 
$} 


%\begin{proof}
%\end{proof}


\item For sets $A$ and $B$, we have $A \cup B = (A \cap B) \cup (A - B) \cup (B - A).$

%\begin{proof}
%\end{proof}

\end{enumerate}

\item Prove the following by induction.

\begin{enumerate}[(a)]
\item We have $n^3 + 2n$ is a multiple of 3 for all $n \in \ZZ_{\ge 0}$. 

%\begin{proof}[Proof by induction.]
%\end{proof}

\item We have $\sum_{i = 1}^n 2i-1 = n^2$ for all $n \in \ZZ_{\ge 0}$. 

%\begin{proof}[Proof by induction.]
%\end{proof}

\item \label{problem-d} Suppose $A_1, A_2, \dots A_N$ and $B_1, B_2, \dots, B_N$ are sets such that 
$$A_i \subseteq B_i \qquad \text{ for all } 1 \leq i \leq N.$$
Then
$$\bigcup_{i = 1}^N A_i \subseteq \bigcup_{i = 1}^N B_i.$$
{[Hint: With some problems, you may have to do more than one base case; and you may have to prove a lemma for one of those. For example, here, you can check that the claim holds trivially for $N=1$. But you will also need to prove the claim for $N=2$ before you can do the inductive step, using a direct proof. See the .tex file.]} 

%\begin{lem}\label{lemma-d}
%Suppose $A, A', B$, and $B'$ are sets such that $A \subseteq B$ and $A' \subseteq B'$. Then $A \cup A' \subseteq B \cup B'$.
%\end{lem}
%\begin{proof}
%\end{proof}
%
%\begin{proof}[Proof of Problem \ref{problem-d}]
%(Be sure to cite Lemma \ref{lemma-d}!)
%\end{proof}


\end{enumerate}

\item The following is an example of why checking the base case is important.

\smallskip

\noindent Let $P(n)$ be the statement ``$2^n < 2^{n-1}$''.


\begin{enumerate}[(a)]
\item Show that $P(n) \Rightarrow P(n+1)$. Namely, assume $2^n < 2^{n-1}$ for some $n \ge 1$, and use that to show that $2^{n+1} < 2^n$. 

%\begin{proof}
%\end{proof}

\item Check the base case, $P(1)$. 


%\begin{ans}
%\end{ans}


\item Prove that $P(n)$ is actually false for all $n \in \ZZ_{\ge 1}$. 

%\begin{proof}
%\end{proof}

\end{enumerate}

\item Each of the following claims are false, but are accompanied by subtly flawed proofs by induction. For each, find the flaw.

\begin{enumerate}[(a)]
\item   \textbf{Claim:} For every positive integer $n$, if $x$ and $y$ are positive integers with $\max(x, y) = n$, then $x = y$.\footnote{In other words, if $x$ and $y$ are (possibly equal) positive integers, and the biggest of them is equal to $n$, then $x = y$.}


\begin{proof}[Proof by induction.] 
First, for $n=1$, if $\max(x, y) = 1$ and $x$ and $y$ are positive integers, then we have $x = 1$ and $y = 1$.

Next, fix $n\ge 1$ and assume that for any positive integers $x', y'$ such that $\max(x',y') = n$, then $x' = y'$. Let $x$ and $y$ be positive integers such that $\max(x, y) = n+1$. Then $\max(x - 1, y - 1) = n$, so by the inductive hypothesis, $x - 1 = y - 1$. It follows that $x = y$. Thus, by induction, the claim holds for all $n \ge 1$. 
\end{proof}

%\begin{ans}
%\end{ans}


\item \textbf{Claim:} If $\cH$ is a set of $n$ horses, then all the horses in $\cH$ are the same color. 

\begin{proof}[Proof by induction.] If the set only has one horse in it, then, trivially, all the horses in that set have the same color. Now assume that the claim holds for a fixed $n \ge 1$, so that all the horses in any set of $n$ horses are the same color. Now consider a set $\cH$ of $n+1$ horses. First, line up those horses in order: the first $n$ of these horses all must be the same color, and the last $n$ of these must also be the same color. Because the set of the first $n$ horses and the set of the last $n$ horses overlap, all $n + 1$ must be the same color. Thus, by induction, all the horses in any finite set of horses must have the same color.
\end{proof}

%\begin{ans}
%\end{ans}


%\item \textbf{Claim.} Let $n \ge 2$. If $\ell_1, \ell_2, \dots, \ell_n$ is a collection of distinct\footnote{``Distinct'' means that no two of them are the same.} lines so that no two of them are parallel, then all $n$ lines meet at a single point. 
%
%\begin{proof}[Proof by induction.] First, for $n = 2$, we know that if two lines $\ell_1$ and $\ell_2$ are not parallel, then they meet at a point. 
%
%Next, for the sake of induction, fix $n$ and assume that for any collection of $n$ lines such that no two of them are parallel, all must meet at a single point. Now let $\ell_1, \ell_2, \dots, \ell_{n+1}$ be a collection of lines so that no two of them are parallel. We would like to show that all $n+1$ lines meet at a single point. 
%
%By the inductive hypothesis, the first $n$ of these lines meet in a common point $p_1$. Similarly, by the inductive hypothesis, the last $n$ of these lines meet in a common point $p_2$. It just remains to show that $p_1$ and $p_2$ must be the same point. If $p_1$ and $p_2$ were different points, all lines containing both of them must be the same line because two points determine a line. This contradicts our assumption that all these lines are distinct. Thus, $p_1$ and $p_2$ are the same point. We conclude that the point $p_1 = p_2$ lies on all $n + 1$ lines. Therefore, by induction, the claim holds for all $n \ge 2$. 
%\end{proof}
%
%
%%\begin{ans}
%%\end{ans}

\end{enumerate}


\end{enumerate}



\end{document}