1.1 Introduction
We have already introduced the concept of inequations in our ‘Theory of Equations’ modules. To recollect:
- \(x>0 \iff \frac{1}{x}>0\)
- \(x>0\) and \(a<0\Rightarrow ax<0\)
- \(x>a\) with both \(a,x>0\) this implies \(\frac{1}{x}<\frac{1}{a}\)
- \(x>a\) with \(x>0, a<0\) this implies \(\frac{1}{x}>\frac{1}{a}\).
We shall introduce ourselves to some advanced inequalities that are used in the modern world.
2.1 The AM-GM-HM Inequality
Consider the positive real numbers \(a_1,a_2,…a_n\). The following inequality is called the AM-GM-HM inequality:
We consider the proof by induction:
Trvial to prove for \(n=2\), let’s assume that this holds true for \(n-1\).
We assume without loss of generality \(a_1\le a_2\le …\le a_n\). Also let \(G=\sqrt[n]{a_1a_2…a_n}\)
Note that we have \(a_1 \le G \le a_n\). Also since \(a_1+a_n \ge \frac{a_1a_n}{G}+G\),
\(a_1+a_n-G-\frac{a_1a_n}{G}=\frac{a_1}{G}(G-a_n)+(a_n-G)=\frac{1}{G}(G-a_1)(a_n-G)\ge 0\). By the induction hypothesis we have
We already know \(a_1+a_n\ge \frac{a_1a_n}{G}+G\), and from this it follows that
We can follow a similar argument to prove the 2nd part, and this is left as an exercise. Also, when we have all \(a_i\) equal we achieve the case of equality for the above inequality.
One important thing is to note that a lot of inequality proves, mainly which involve proving for all positive integers may invoke this principle of Mathematical Induction.
Note that using AM-GM Inequality, the following is trivial :
\(a+\frac{1}{a}\ge 2\) with \(a>0\).
Using this, show that \(\frac{x^2+2}{\sqrt{x^2+1}} \ge 2\) for all \(x\).
2.2 Weighted Means Inequality
Let’s consider that \(a_i\) has weight \(w_i\) for all \(i\).
In such a case we define the arithmetic mean to be:
The Geometric mean is
And the Harmonic mean is :
So, from the AM-GM-HM inequality we conclude that \(A_w \ge G_w\ge H_w\).
2.3 Rearrangement Inequality
We consider 2 rearrangements (or permutations) of \(n\) terms of 2 sequences \(A=\left\{a_i\right\}\) and \(B=\left\{ b_i\right \}\).
Consider the sum \(S=\sum\limits_{i=1}^na_ib_i\).
Rearrangement inequality confirms that \(S\) reaches its maximum when both the sequences are similarly sorted (that is, if \(a_k\) is greater than or equal to exactly \(i\) of the other members of \(A\), then \(b_k\) is also greater than or equal to exactly \(i\) of the other members of \(B\)).Thus, if both of the sequences are in ascending order, or descending order, the sum stated above reaches its peak.
Let’s try a proof by contradiction:
Before we begin the proof properly, it is useful to consider the case where \(n=2\). Without loss of generality, sort \(A\) and \(B\) so that \(a_2\ge a_1\) and \(b_2\ge b_1\). By hypothesis \((a_2-a_1)(b_2-b_1) \ge 0\). Expanding and taking some terms to the other side of the inequality, we get \(a_1b_1+a_2b_2 \ge a_1b_2+a_2b_1\).
For the general case, consider the sequences to be sorted in ascending order. Thus \(a_i\le a_{i+1}\) and similarly for the terms of the other sequence, and suppose the grouping that maximizes the desired sum of products is not the one that pairs \(a_1\) with \(b_1\), \(a_2\) with \(b_2\) and so on. This means that there is at least one instance where \(a_i\) is paired with \(b_j\) while \(a_k\) is [aired with \(b_l\) with \(i<j\) and \(k>l\). However, using the technique seen above to prove the inequality for \(n=2\), we can see that the sum of products can only increase if we instead pair \(a_i\) with \(b_i\), unless both a’s and b’s are equal. This contradicts our assumption that the arrangement we had was already the largest one.
A variation of this is the famous Chebyshev’s Inequality which states that if the sequences \(A\) and \(B\) are sorted in descending order, then the following inequality holds:
\(n\left(\sum\limits_{i=1}^na_ib_i \right ) \ge \left(\sum\limits_{i=1}^na_i \right )\left(\sum\limits_{i=1}^nb_i \right )\)The sign of the inequality gets reversed if the sequences are sorted in opoosite manners (i.e one is sorted in ascending order, while the other is sorted in descending order).
This is a simple consequence of the Rearrangement inequality.