\documentclass[12pt, letterpaper]{article}
\usepackage{fullpage}
\usepackage{graphics}
\usepackage{amssymb}

\title{TJ USAMO Practice/Lecture 2 - Inequalities}
\author{PDiao05\footnote{Although based on Mildorf and Reid Barton Lectures}}
\date{October 6, 2005}
\begin{document}

\maketitle

\par Inequalities often come up on the USAMO.  To learn to do these it is important to have seen many inequalities. 
That way you gain a larger base of inequalities you know to be true.  There are several techniques and theorems that
come up over and over again.  The most fundamental inequality of all is! drumroll... 

\begin{itemize}
\item \textbf{Jensen!} - Let $f:[a,b] \rightarrow \mathbb{R}$ be a convex function.  Then for any $x_{1}, \cdots , x_{n} \in [a,b]$ and any noneggative reals $\lambda_{1}, \cdots , \lambda_{n}$ summing to one, Jensen says:
\begin{eqnarray*}
\lambda_{1}f(x_{1}) + \cdots + \lambda_{n}f(x_{n}) \ge f(\lambda_{1}x_{1} + \cdots + \lambda_{n}x_{n})
\end{eqnarray*}
With equality iff all the $x_i$ are equal. You might be wondering what a convex function is. Here are some ways you can tell if something is convex:
\begin{enumerate}
\item You can check if $f$ is a convex function by looking at the area above the graph of your function.  If that region is convex in the geometric sense then your function is also convex.  Geometrically, a region is convex iff (if and only if) all the points on the line segment joining any two points in the region is also in the region.
\item The formal definition is $(1-\lambda)f(x) + \lambda f(y) \ge f((1-\lambda)x + \lambda y)$ $\forall \lambda \in [0,1]$ Most of the time we deal with continuous $f$ and in those cases it suffices to check for just a single value of $\lambda$, generally $1/2$.  The reason I say suffice and not iff is because conversely, if $f$ is convex, then $f$ is continuous except possibly at $a$ and $b$.
\item Lastly, you may already know this from calculus, but if $f$ is twice differentiable, you can just check for $f''(x) \ge 0$.
\end{enumerate}
Some common examples of convex functions:
\begin{enumerate}
\item $y = |x-a|$
\item $y = cx^{\alpha}$ where $\alpha \ge 1$ or $\alpha \le 0$ and $x > 0$.
\item $y = a^{x}$ for $a \in \mathbb{R}^{+}$.
\end{enumerate}
Jensen follows from the definition of convexity and smoothing.  Smoothing is essentially when we keep on changing the inequality to be less and less true and then show that even when it is least true, it is still true.
\item \textbf{Weighted Power Mean}- If $x_{1}, \cdots , x_{n}$ are nonnegative reals and $\lambda_{1}, \cdots , \lambda_{n}$ are nonnegative reals summing to one again, then The Weighted Power Mean says:
\begin{eqnarray*}
(\lambda_{1}x_{1}^{r} + \cdots \lambda_{n}x_{n}^{r})^{1/r}
\end{eqnarray*}
is a nondecreasing function of $r$.  It is strictly increasing unless all of the $x_{i}$ are equal.  When $r = 0$, this expression representes the weighted geometric mean of the $x_{i}$.  In fact our beloved AM-GM-HM (Arithmetic Mean, Geometric Mean, Harmonic Mean) inequality is just a specific application of this.  That inequality states $\forall a_{1}, \cdots, a_{n} \in
  \mathbb{R}^{+}$, we have
  \[
  \frac{\sum_{i=1}^{n} a_{i}}{n} \ge \left( \prod_{i=1}^{n} a_{i}
  \right)^{\frac{1}{n}} \ge \frac{n}{\sum_{i=1}^{n} \frac{1}{a_{i}}}
  \]
  with equality iff $a_{1} = \cdots = a_{n}$.
  This inequality is extremely important. Jensen on a special function yields this inequality.
\item \textbf{H\"older} - Let $(a_{1}, \cdots, a_{n}), (b_{1}, \cdots, b_{n}), \cdots, (z_{1}, \cdots, z_{n})$ be sequences of nonnegative real numbers and $\lambda_{a}, \lambda_{b}, \cdots, \lambda_{z}$ be nonnegative reals summing to one.  Then H\"older says:
\begin{eqnarray*}
(a_{1} + \cdots + a_{n})^{\lambda_{a}}(b_{1} + \cdots + b_{n})^{\lambda_{b}}\cdots(z_{1} + \cdots + z_{n})^{\lambda_{z}} \ge a_{1}^{\lambda_{a}} b_{1}^{\lambda_{b}}\cdots  z_{1}^{\lambda_{z}} + \cdots  a_{n}^{\lambda_{a}} b_{n}^{\lambda_{b}}\cdots  z_{n}^{\lambda_{z}}
\end{eqnarray*}
In reality, the most commonly used special case of H\"olders is the Cauchy Schwartz inequality.  In vector land it is just a statement about the fact that the dot product of two vectors cannot exceed the product of the magnitudes of the two vectors and are only equal when the vectors are parallel.  It states $\forall a_{1}, \dots, a_{n}, b_{1}, \dots, b_{n} \in
  \mathbb{R}$, we have
  \[
  \left(a_{1}^{2} + \cdots + a_{n}^{2}\right)\left(b_{1}^{2} + \cdots +
    b_{n}^{2}\right) \ge \left(a_{1}b_{1} + \cdots + a_{n}b_{n}\right)^{2}
    \]
    with equality iff $b_{k} = c a_{k}$ for $k = 1, \dots, n$.
As a random note, H\"older's Inequality can be used to prove Minkowski's inequality an even more obscure thing.  However a special case of it is the triangle inequality which is useful sometimes, especially in geometric inequalities:
\begin{eqnarray*}
\sqrt[r]{x_{1}^{r} + \cdots + x_{n}^{r}} + \sqrt[r]{y_{1}^{r} + \cdots + y_{n}^{r}}\ge \sqrt[r]{(x_{1} + y_{1})^{r} + \cdots + (x_{n} + y_{n})^{r}}
\end{eqnarray*}
for $x_{1}, \cdots , x_{n}, y_{1}, \cdots, y_{n},$ nonnegative reals, $r \ge 1$.
To prove H\"older, try reducing it to the case of two sequences and renormalization of the sequences to sum to 1.  
\item \textbf{Rearrangement} - Let $a_{1}, \dots, a_{n}, b_{1}, \dots,
  b_{n} \in \mathbb{R}$ be non-decreasing sequences. Let $\pi$ be a
    permutation of $\{1, \dots, n\}$. Then
    \[
    \sum_{i=1}^{n} a_{i}b_{i} \ge \sum_{i=1}^{n} a_{i}b_{\pi(i)} \ge
    \sum_{i=1}^{n} a_{i}b_{n+1-i}
    \]
This inequality should be intuitively obvious, but how would you prove it?
\item \textbf{Chebyshev} - Chebyshev's inequality applies for two
  sequences of real numbers $a_{1}, \dots, a_{n}$ and $b_{1}, \dots,
    b_{n}$,
    \[
    \frac{\sum_{i=1}^{n} a_{i}b_{i}}{n} \ge \left(\frac{\sum_{i=1}^{n}
        a_{i}}{n}\right)\left(\frac{\sum_{i=1}^{n} b_{i}}{n}\right)
	\]

	if the sequences $A$ and $B$ are sorted in the same order (ascending /
	descending). (If they are sorted in the opposite order, the inequality
	flips.)
This follows from Rearrangement.
\item \textbf{Schur} - Even though this inequality is easily proved, it is also one of the strongest.  That is, it is closer to being not true than some inequalities such as AM-GM.  It states that $\forall a, b, c
  \in \mathbb{R}_{0}^{+}$ and $r \in \mathbb{R}^{+}$, we have
  \[
  a^r(a-b)(a-c) + b^r(b-c)(b-a) + c^r(c-a)(c-b) \ge 0
  \]
  with equality iff $a = b = c$ or one of $\{a, b, c\}$ is 0 and the
  other two are equal.
For the mostly used case of $r=1$, we have:
\begin{eqnarray*}
a^{3} + b^{3} + c^{3} + 3abc \ge a^{2}b + b^{2}a + b^{2}c + c^{2}b + a^{2}c + c^{2}a
\end{eqnarray*}
\item \textbf{Trivial Inequality} - It states that $\forall x \in \mathbb{R}$ we
  have $x^2 \ge 0$.  Can't neglect this.
\item \textbf{Majorization- Majorization and Muirhead} - First we must define what it means to majorize something.  We say that the sequence $(x_{1}, \cdots , x_{n})$ majorizes the sequence $(y_{1}, \cdots, y_{k})$ iff $x_{1} + \cdots + x_{n} \ge y_{1} + \cdots + y_{k}$ for all $k = 1, 2, \cdots, n$ and with equality when $k = n$.  Note: the two sequences are first sorted into nonincreasing order.  If $f:[a,b] \rightarrow \mathbb{R}$ is a convex function and $(x_{1}, \cdots , x_{n})$ majorizes the sequence $(y_{1}, \cdots, y_{k})$ with $x_{i}, y_{i} \in [a,b]$. Then:
\[
\sum_{i=1}^{n}f(x_{i}) \ge \sum_{i=1}^{n}f(y_{i})
\]
Although interesting, perhaps more interesting is Muirhead.  Unfortunately, this is the only theorom in this packet you should never quote
on the USAMO in your proof.  Muirhead states that given the sequence $(a_{1}, \cdots , a_{n})$ that majorizes the sequence $(b_{1}, \cdots, b_{k})$
then for any positive reals $x_{1}, \cdots , x_{n}$:
\[
\sum_{\pi \in S_{n}}x_{\pi(1)}^{a_{1}}x_{\pi(2)}^{a_{2}}\cdots x_{\pi(n)}^{a_{n}} \ge 
\sum_{\pi \in S_{n}}x_{\pi(1)}^{b_{1}}x_{\pi(2)}^{b_{2}}\cdots x_{\pi(n)}^{b_{n}}
\]
where the weird summation is a cyclic summation over all of the permutations of the $x_{i}$'s.  I am told you can prove this with the majorization inequality
from above.  Sometimes it is known as ``Bunching" because if a sequence of $y_{i}$ is majorized by a sequence
of $x_{i}$ it is intuitively more bunched up.  You can always use it to quickly check if you have gone too far.  For example, if you have used AM-GM 20 times
you want to make sure the expression you now have is still true, Muirhead is a very quick way to check the truth of your statement.  In reality, all it does
is do all the dirty work of AM-GM for you.  When writing up your solution find the specific application of AM-GM that you want and do not just quote Muirhead.
\item \textbf{Practice Problem} (USAMO '78) $$ a^{2} + b^{2} + c^{2} + d^{2} + e^{2} = 16$$ $$a + b + c + d + e = 8$$ maximize $e$.
\end{itemize}
\end{document}