Note 1
[A] Inequalities
Inequality is perhaps the most amiable, but extremely in depth section to study in Algebra. It could range from simple inequalities such as solving for \(x\) in \(x + 1 > 2\) to problems involving numerous advanced techniques and known results. As a result, although few inequalities in advanced problems could be proven by bashing, most would require an elegant solution. With that in mind, this note will begin with numerous classical inequalities such as the AM-GM inequality to advanced concepts such as majorization.
1.1 Fundamental Inequalities
One of the first fields that I studied for olypmiads is inequality, and I think that is the same for many other students. Indeed, naive me when I first started inequalities didn’t know that inequalities is one of the fields that really requires you to have lots of background knowledge because many problems are solved by tweaking known inequalities and doing some clever substitutions. In this section, let’s discuss some fundamental must-know inequalities as an introduction to olympiad inequalities.
1.1.1 AM-GM Inequality
I assume most of you know or at least have heard of this inequality as we learn it in middle and high school. AM-GM inequality stands for Arithmetic Mean-Geometric Mean inequality and literally compares those two means.
Definition 1.1.1: AM-GM Inequality
For \(a_k \geq 0\), the following inequality holds with equality if and only if \(a_1 = a_2 = \dots = a_n\). \[ \frac { \sum _{i=1}^n a_i }{n} \geq \sqrt [n]{ \prod _{i=1}^n a_i } \]
You might be more familiar with \(a + b \geq 2 \sqrt {ab}\), but the inequality above is the generalized version.
In the context of olympiads, AMGM is used the most for cancellation and investigating the minimum.
Let’s take a look at very simple example.
Exercise 1.1.2
Prove the following inequality for \(a, b, c, d \geq 0\). \[ (a + b)(b + c)(c + d)(d + a) \geq 16abcd \]
Solution.
Because \(a, b, c, d\) are non-negative, we could utilize AM-GM inequality. By AM-GM inequality, the following inequalities hold. \begin{align*} a + b &\geq 2 \sqrt {ab} \\ b + c &\geq 2 \sqrt {bc} \\ c + d &\geq 2 \sqrt {cd} \\ d + a &\geq 2 \sqrt {da} \end{align*}
Multiplying the inequalities, \[ (a + b)(b + c)(c + d)(d + a) \geq 2 \sqrt {ab} \cdot 2 \sqrt {bc} \cdot 2 \sqrt {cd} \cdot 2 \sqrt {da} = 16abcd \] hold and \((a + b)(b + c)(c + d)(d + a) \geq 16abcd\).
When we discuss arithmetic and geometric mean, we normally include weighted means, so let’s do the same for inequality.
Definition 1.1.3: Weighted AM-GM Inequality
For weights \(w_1, w_2, \dots , w_n \geq 0\) such that \(\sum _{i=1}^n w_i = w\) the following inequality holds. \[ \frac {\sum _{i=1}^n w_i a_i}{w} \geq \sqrt [w]{\prod _{i=1}^n a_i^{w_i}} \] The equality holds if and only if \(a_1 = a_2 = \dots = a_n\).
From the definition, we can notice that the original inequality is obtained with \(w_1 = w_2 = \cdots = w_n = \frac {1}{n}\). Here is a problem on weighted AM-GM inequality.
Exercise 1.1.4: 2020 IMO Problem 2 (\(\bullet \bullet \circ \))
Show that for \(a, b, c, d \in \mathbb {R}\) such that \(a \geq b \geq c \geq d > 0\) and \(a + b + c + d = 1\), \[ (a + 2b + 3c + 4d) a^a b^b c^c d^d < 1 \] holds.
Solution.
First, consider the following weighted AM-GM inequality for \(a, b, c, d\) with weights \(a, b, c, d\) respectively. \begin{align*} \frac {a \cdot a + b \cdot b + c \cdot c + d \cdot d} {a + b + c + d} &\geq \sqrt [a + b + c + d]{a^a b^b c^c d^d} \\ a^2 + b^2 + c^2 + d^2 &\geq a^a b^b c^c d^d \end{align*}
Therefore, it suffices to show that the following inequality holds. \[ (a + 2b + 3c + 4d)(a^2 + b^2 + c^2 + d^2) < 1 \] Consider inequalities below. \begin{align*} a^2 (a + 2b + 3c + 4d) &< a^2 (a + 3b + 3c + 3d) \quad (\because b \geq d) \\ b^2 (a + 2b + 3c + 4d) &< b^2 (3a + b + 3c + 3d) \quad (\because 2a \geq b + d) \\ c^2 (a + 2b + 3c + 4d) &< c^2 (3a + 3b + c + 3d) \quad (\because 2a + b \geq 2c + d) \\ d^2 (a + 2b + 3c + 4d) &< d^2 (3a + 3b + 3c + d) \quad (\because 2a + b \geq 3d) \end{align*}
Integrating, \begin{align*} &(a + 2b + 3c + 4d)(a^2 + b^2 + c^2 + d^2) \\ &\qquad \qquad < a^2 (a + 3b + 3c + 3d) + b^2 (3a + b + 3c + 3d) \\ &\qquad \qquad \qquad + c^2 (3a + 3b + c + 3d) + d^2 (3a + 3b + 3c + d) \\ &\qquad \qquad < (a + b + c + d)^3 = 1 \end{align*}
and the inequality holds.
With the ideas of weighted AMGM in mind, we can further generalize our results for different means just as we have generalized the means.
1.1.2 Power Mean Inequality
Power Mean inequality, also known as QM-AM-GM-HM inequality, compares the four major means with generalization of AMGM. Without simple notations, we can represent the Power Mean inequality as \(M_2 \geq M_1 \geq M_0 \geq M_{-1}\).
Definition 1.1.5: Power Mean Inequality
For positive real numbers \(a_i\), the inequality \[ \sqrt { \frac {\sum _{i=1}^n a_i^2}{n} } \geq \frac {\sum _{i=1}^n a_i}{n} \geq \sqrt [n]{\prod _{i=1}^n a_i} \geq \frac {n}{ \sum _{i=1}^n \frac {1}{a_i} } \] holds with equality if and only if \(a_1 = \cdots = a_n\).
With the definition in mind, we can naturally apply the same definition for weighted power means.
Definition 1.1.6: Weighted Power Mean Inequality
For positive real numbers \(a_i\), the inequality \[ \sqrt { \frac {\sum _{i=1}^n w_i a_i^2}{w} } \geq \frac {\sum _{i=1}^n w_i a_i}{w} \geq \sqrt [w]{\prod _{i=1}^n a_i^{w_i}} \geq \frac {w}{ \sum _{i=1}^n \frac {w_i}{a_i} } \] holds with equality if and only if \(a_1 = \cdots = a_n\).
Continuing from AMGM and its variations, let’s discuss arguably the second most famous inequality in middle and high schools: Cauchy-Schwarz Inequality.
1.1.3 Cauchy-Schwarz Inequality
As always, let’s get started with the definition.
Definition 1.1.7: Cauchy-Schwarz Inequality
For all real numbers \(a_i\) and \(b_i\), \[ \left ( \sum _{i=1}^n a_i^2 \right ) \left ( \sum _{i=1}^n b_i^2 \right ) \geq \left ( \sum _{i=1}^n a_i b_i \right )^2 \] with equality if and only if \(\frac {a_i}{b_i} = k\) for all integer \(1 \leq i \leq n\), where \(k > 0\) and \(a_ib_i \neq 0\).
When \(n = 2\) we get the form \((a^2 + b^2)(x^2 + y^2) \geq (ax + by)^2\) that we initially learn.
Now there are few standard proofs for Cauchy inequality, and I personally learned the method using determinants, but there is another very interesting way that uses AMGM and normalization, and in my opinion much better than the one that uses determinants. Here is a video explaining two different proofs if you prefer videos instead of text below.
Proof.
Let \(\sum _{i=1}^n a_i^2 = A^2\) and \(\sum _{i=1}^n b_i^2 = B^2\). Then, the terms can be rewritten as \(a_i = A x_i\) and \(b_i = B y_i\). Naturally by construction, it is evident that \(\sum _{i=1}^n x_i^2 = \sum _{i=1}^n y_i^2 = 1\). Rewriting the Cauchy inequality, we obtain the following. \[ A^2 B^2 \geq A^2 B^2 \left ( \sum _{i=1}^n x_i y_i \right ) \] In other words, it suffices to show that \(\sum _{i=1}^n x_i y_i \leq 1\) for positive \(x_i\) and \(y_i\). Using AMGM, \[ \sum _{i=1}^n x_i y_i \leq \sum _{i=1}^n \left ( \frac {x_i^2 + y_i^2}{2} \right ) \] holds and \(\sum _{i=1}^n x_i y_i \leq \frac {2}{2} = 1\). Moreover, the equality holds if and only if \(x_i = y_i\), i.e. \(\frac {a_i}{A} = \frac {b_i}{B}\) for all integer \(i \in [1, n]\) and \(\frac {a_i}{b_i}\) is constant.
I like this proof because we can expand Cauchy inequality as the following. \[ \left ( \sum _{i=1}^n a_i^3 \right ) \left ( \sum _{i=1}^n b_i^3 \right ) \left ( \sum _{i=1}^n c_i^3 \right ) \geq \left ( \sum _{i=1}^n a_i b_i c_i \right )^3 \] We cannot use determinants in this case. However letting \(\sum _{i=1}^n a_i^3 = A^3\), \(\sum _{i=1}^n b_i^3 = B^3\), and \(\sum _{i=1}^n c_i^3 = C^3\), we can set the individual terms \(a_i = Ax_i\), \(b_i = By_i\), and \(c_i = Cz_i\). Therefore, it suffices to show \[ A^3 B^3 C^3 \geq A^3 B^3 C^3 \left ( \sum _{i=1}^n z_i y_i z_i \right )^3 \] and that is equivalent of showing \(\left ( \sum _{i=1}^n z_i y_i z_i \right )^3 \leq 1\). Using AMGM, \[ \left ( \sum _{i=1}^n z_i y_i z_i \right )^3 \leq \sum _{i=1}^n \left ( \frac {x^3 + y^3 + z^3}{3} \right ) = 1 \] holds and our new version of Cauchy inequality holds. With this method, we can continue generalizing for \(n > 3\).
Continuing, we can obtain an interesting direct consequence. The lemma below known as Titu’s lemma, T2 Lemma, Sedrakyan’s inequality, and Engel’s form and was named after one of the greatest mathematician Titu Andreescu.
Corollary 1.1.8: Titu’s Lemma
For positive real numbers \(a_i\) and \(b_i\), \[ \sum _{i=1}^n \frac {a_i^2}{b_i} \geq \frac { \left ( \sum _{i=1}^n a_i \right )^2 }{ \sum _{i=1}^n b_i } \]
Proof.
Substituting \(x_i = \frac {a_i}{\sqrt {b_i}}\) and \(y_i = \sqrt {b_i}\) to the Cauchy-Schwarz inequality, the following inequalities are obtained. \begin{align*} \left ( \sum _{i=1}^n x_i^2 \right ) \left ( \sum _{i=1}^n y_i^2 \right ) &\geq \left ( \sum _{i=1}^n x_i y_i \right )^2 \\[0.5em] \left ( \sum _{i=1}^n \left ( \frac {a_i}{\sqrt {b_i}} \right )^2 \right ) \left ( \sum _{i=1}^n \left ( \sqrt {b_i} \right )^2 \right ) &\geq \left ( \sum _{i=1}^n \frac {a_i}{\sqrt {b_i}} \cdot \sqrt {b_i} \right )^2 \end{align*}
Recasting, \begin{align*} \left ( \sum _{i=1}^n \frac {a_i^2}{b_i} \right ) \left ( \sum _{i=1}^n b_i \right ) &\geq \left ( \sum _{i=1}^n a_i \right )^2 \\ \sum _{i=1}^n \frac {a_i^2}{b_i} &\geq \frac { \left ( \sum _{i=1}^n a_i \right )^2 }{ \sum _{i=1}^n b_i } \end{align*}
are obtained and the lemma holds.
This lemma comes especially handy if an inequality involves fractions with square numbers. Now that we discussed a direct consequence of Cauchy-Schwarz inequality, we can consider its generalization.
1.1.4 Hölder’s Inequality
Cauchy-Schwarz inequality is actually a special case of Hölder’s inequality. Both inequalities can be used in multiple ways such as eliminating radicals and fractions. Below is the definition of Hölder’s inequality.
Definition 1.1.9: Hölder’s Inequality
Let \(a_i, b_i, \ldots , z_i > 0\) and \(\lambda _a, \lambda _b, \ldots , \lambda _z \geq 0\) such that \(\lambda _a + \lambda _b + \dots + \lambda _z = 1\). Then, \begin{align*} \left ( \sum _{i=1}^n a_i \right )^{\lambda _a} \left ( \sum _{i=1}^n b_i \right )^{\lambda _b} \cdots \left ( \sum _{i=1}^n z_i \right )^{\lambda _z} \geq \sum _{i=1}^n a_i^{\lambda _a} b_i^{\lambda _b} \cdots z_i^{\lambda _z} \end{align*}
holds with equality if \(a_1 : a_2 : \dots : a_n \equiv b_1 : b_2 : \dots : b_n \equiv \dots \equiv z_1 : z_2 : \dots : z_n\).
Indeed, Cauchy inequality does resemble Hölder’s Inequality! To derive Cauchy inequality from Hölder’s, it suffices to show that a specific case of Hölder’s inequality will lead to Cauchy inequality.
Let \(\lambda _a = \lambda _b = \frac {1}{2}\). Substituting, the following inequalities hold. \begin{align*} \left ( \sum _{i=1}^n a_i \right )^\frac {1}{2} \left ( \sum _{i=1}^n b_i \right )^\frac {1}{2} \left ( \sum _{i=1}^n c_i \right )^0 \cdots \left ( \sum _{i=1}^n z_i \right )^0 &\geq \sum _{i=1}^n a_i^{\frac {1}{2}} b_i^{\frac {1}{2}} \cdot c_i^0 \cdots z_i^0 \\ \left ( \sum _{i=1}^n a_i \right )^\frac {1}{2} \left ( \sum _{i=1}^n b_i \right )^\frac {1}{2} &\geq \sum _{i=1}^n a_i^\frac {1}{2} b_i^\frac {1}{2} \end{align*}
Let \(\alpha _i = \sqrt {a_i}\) and \(\beta _i = \sqrt {b_i}\). Substituting, \[ \left ( \sum _{i=1}^n \alpha _i^2 \right )^\frac {1}{2} \left ( \sum _{i=1}^n \beta _i^2 \right )^\frac {1}{2} \geq \sum _{i=1}^n \alpha _i \beta _i \] and \[ \left ( \sum _{i=1}^n \alpha _i^2 \right ) \left ( \sum _{i=1}^n \beta _i^2 \right ) \geq \left ( \sum _{i=1}^n \alpha _i \beta _i \right )^2 \] are obtained. This is Cauchy-Schwarz inequality! Below is a very classic problem on Hölder’s Inequality
Exercise 1.1.10
Show that the following inequality holds for all \(a, b, c > 0\). \[ (a^3 + 2)(b^3 + 2)(c^3 + 2) \geq (a + b + c)^3 \]
Solution.
The key to this problem is changing the left-hand side to apply Hölder’s Inequality. Consider the following inequality by Hölder. \[ (a^3 + 1 + 1)^\frac {1}{3} (1 + b^3 + 1)^\frac {1}{3} (1 + 1 + c^3)^\frac {1}{3} \geq a + b + c \] Thus, cubing both sides leads to the desired result.
Continuing from Cauchy-Schwarz inequality and its variation, another fundamental inequality of different type is rearrangement inequality.
1.1.5 Rearrangement Inequality
Let’s start with definition.
Definition 1.1.11: Rearrangement Inequality
Let \(a_i\) and \(b_i\) be real numbers such that \(a_1 \geq a_2 \geq \cdots \geq a_n\) and \(b_1 \geq b_2 \geq \cdots \geq b_n\). Moreover, let \(b_{\sigma (i)}\) be the \(i^\text {th}\) term of the permutations of \(b_1, \cdots , b_n\). Then, the following inequalities hold. \[ \sum _{i=1}^n a_i b_i \geq \sum _{i=1}^n a_i b_{\sigma (i)} \geq \sum _{i=1}^n a_i b_{n-i+1} \] The equality holds if at least one sequence is constant.
With the definition, we can obtain a special consequence.
Corollary 1.1.12: Chebyshev’s Inequality
For real numbers \(a_1 \geq a_2 \geq \cdots \geq a_n\) and \(b_1 \geq b_2 \geq \cdots \geq b_n\), \[ n \left ( \sum _{i=1}^n a_i b_i \right ) \geq \left ( \sum _{i=1}^n a_i \right ) \left ( \sum _{i=1}^n b_i \right ) \geq n \left ( \sum _{i=1}^n a_i b_{n-i+1} \right ) \] holds with the equality if at least one sequence is constant.
Proof.
Consider the following cases where \(b_1 \geq b_2 \geq \cdots \geq b_n\) are cycled through in the rearrangement inequality. \begin{align*} \sum _{i=1}^n a_i b_i &\geq a_1 b_1 + a_2 b_2 + \cdots + a_n b_n \geq \sum _{i=1}^n a_i b_{n-i+1} \\ \sum _{i=1}^n a_i b_i &\geq a_1 b_2 + a_2 b_3 + \cdots + a_n b_1 \geq \sum _{i=1}^n a_i b_{n-i+1} \\ &\qquad \qquad \qquad \vdots \\ \sum _{i=1}^n a_i b_i &\geq a_1 b_n + a_2 b_1 + \cdots + a_n b_{n-1} \geq \sum _{i=1}^n a_i b_{n-i+1} \\ \end{align*}
Adding the inequalities, \[ n \left ( \sum _{i=1}^n a_i b_i \right ) \geq \left ( \sum _{i=1}^n a_i \right ) \left ( \sum _{i=1}^n b_i \right ) \geq n \left ( \sum _{i=1}^n a_i b_{n-i+1} \right ) \] and the corollary holds.