\newpage\documentclass[11pt,onecolumn,fleqn]{article}

\usepackage[latin1]{inputenc}
\usepackage{enumerate}
\usepackage[hang,flushmargin]{footmisc}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{amsthm}
\usepackage{xcolor}

\theoremstyle{definition}
\newtheorem{theorem}{Theorem}[section]
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{example}[theorem]{Example}

\setlength{\oddsidemargin}{0px}
\setlength{\textwidth}{460px}
\setlength{\voffset}{-1.5cm}
\setlength{\textheight}{20cm}
\setlength{\parindent}{0px}
\setlength{\parskip}{10pt}

\newcommand{\TT}{$\checkmark$}
\newcommand{\FF}{$\times$}


\begin{document}
\thispagestyle{empty}
\begin{center}
{\Huge 21-128 and 15-151 problem sheet 9}

Solutions to the following exercises and optional bonus problem are to be submitted through 
blackboard by 8:30AM on

\textbf{Wednesday 30th November 2016.}

\end{center}

\subsubsection*{Problem 1}
For each example below, determine whether the given relation $R$ is an equivalence relation on the given set $S$:
\begin{enumerate}[(a)]
\item $S = \mathbb{N} \setminus \{ 0, 1 \}$; $(x,y) \in R$ if and only if $\mathrm{gcd}(x,y) > 1$.
\item $S = \mathbb{R}$; $(x,y) \in R$ if and only if there exists $n \in \mathbb{Z}$ such that $x=2^ny$.
\end{enumerate}

\subsubsection*{Problem 2}
Find the flaw in the following argument that the symmetric and transitive properties imply the reflexive property 
for a relation $R$ on a set $S$:
\begin{quote}
Consider $x \in S$. If $(x,y) \in R$ then the symmetric property implies that $(y,x) \in R$. Now the transitive property 
applied to $(x,y)$ and $(y,x)$ implies that $(x,x) \in R$.
\end{quote}

\subsubsection*{Problem 3}
Let $x,y,z$ be nonnegative real numbers such that $y+z \ge 2$. Prove that $$(x+y+z)^2 \ge 4x+4yz$$

\vspace{-.2truein}
\subsubsection*{Problem 4}
Let $P(n)$ be a mathematical statement depending on an integer $n$. Suppose that:
\begin{enumerate}[(i)] \vspace{-10pt}
\item $P(1)$ is true; and
\item Given $n \in \mathbb{N^+}$, if $P(n)$ is true, then $P(2n)$ is true; and
\item Given $n \in \mathbb{N^+}$ with $n>1$, if $P(n)$ is true, then $P(n-1)$ is true.
\end{enumerate}
Prove that $P(n)$ is true for all $n \in \mathbb{N^+}$.

\subsubsection*{Problem 5}
Use the result of Problem 4 to deduce that, given $n \in \mathbb{N^+}$ and nonnegative real numbers 
$a_1, a_2, \dots, a_n$, that $$\frac{1}{n} \sum_{i=1}^n a_i \ge \sqrt[n]{\prod_{i=1}^n a_i}$$
\textbf{Hint:} In step (iii) from Problem 4, let $\displaystyle a_n = \frac{1}{n-1} \sum_{i=1}^{n-1} a_i$ and apply $P(n)$.


\subsubsection*{Bonus Problem - (2 points)} Show that for all positive real numbers $A, B, C$,
$$\frac{A}{B+C} +\frac{B}{A+C} +\frac{C}{A+B} \geq \frac32.$$


\end{document}
