Inequalities

Study Sheet

Inequalities

AM–GM, Cauchy–Schwarz, smoothing

The Essential Inequalities

Tip
AM–GM and Cauchy–Schwarz

AM–GM: ∑ain≥∏ain\dfrac{\sum a_i}{n}\ge\sqrt[n]{\prod a_i}. Cauchy–Schwarz: (∑aibi)2≤(∑ai2)(∑bi2)\left(\sum a_ib_i\right)^2\le\left(\sum a_i^2\right)\left(\sum b_i^2\right).

In plain terms. AM–GM says an average beats a geometric mean; Cauchy–Schwarz bounds a "dot product" by the sizes of the two lists. Together they settle most olympiad inequalities.

Example. By AM–GM, a+b+c≥3abc3a+b+c\ge 3\sqrt[3]{abc}; if abc=1abc=1 this gives a+b+c≥3a+b+c\ge 3.

Concept
Rearrangement and smoothing

A sum ∑aibi\sum a_ib_i is largest when both sequences are sorted the same way; "smoothing" nudges variables toward equality while keeping the constraint.

In plain terms. Pair big with big to maximize a sum of products; to find an extreme, gently push the variables together and watch the value improve.

Example. To maximize abab with a+b=10a+b=10 fixed, smoothing pushes toward a=b=5a=b=5, giving the maximum 2525.

Good-to-Know Inequalities

Tip
Titu’s lemma (Cauchy, Engel form)

x12a1+x22a2+⋯+xn2an ≥ (x1+x2+⋯+xn)2a1+a2+⋯+an\dfrac{x_1^2}{a_1}+\dfrac{x_2^2}{a_2}+\cdots+\dfrac{x_n^2}{a_n}\ \ge\ \dfrac{(x_1+x_2+\cdots+x_n)^2}{a_1+a_2+\cdots+a_n} for positive denominators, with equality when the xiai\tfrac{x_i}{a_i} are all equal.

In plain terms. Any sum of "squares over things" is at least the square of the summed tops over the summed bottoms — the fastest tool for minimizing sums of fractions under a linear constraint.

Example. With a+b+c=20a+b+c=20: 4a+9b+25c≥(2+3+5)220=5\dfrac4a+\dfrac9b+\dfrac{25}{c} \ge \dfrac{(2+3+5)^2}{20} = 5, met at (4,6,10)(4,6,10).

Tip
The QM–AM–GM–HM chain

For positive reals: ∑ai2n ≥ ∑ain ≥ ∏ain ≥ n∑1ai\sqrt{\dfrac{\sum a_i^2}{n}}\ \ge\ \dfrac{\sum a_i}{n}\ \ge\ \sqrt[n]{\prod a_i}\ \ge\ \dfrac{n}{\sum \tfrac{1}{a_i}}, all with equality exactly when the numbers are equal.

In plain terms. Four averages, always in this order: quadratic, arithmetic, geometric, harmonic. Contest problems hand you one end of the chain and ask about the other.

Example. (a+b+c)(1a+1b+1c)≥9(a+b+c)\left(\tfrac1a+\tfrac1b+\tfrac1c\right)\ge 9 is exactly AM ≥\ge HM in disguise.

Concept
Check the equality case first

Before hunting bounds, ask WHERE equality would hold and whether the constraint permits it — an unattainable equality point means the true extremum sits at a boundary instead.

In plain terms. AM–GM promising 1212 means nothing if the balancing point violates the constraint: minimize 9u+4u\tfrac9u + 4u on 0<u≤10<u\le1 and the answer is 1313 at the endpoint, not 1212.

Example. Equality in Cauchy–Schwarz needs proportional sequences; if the constraint forbids proportionality, look at the boundary.