Competition mathematics and problem solving

Olympiad inequalities

The core toolkit for proving inequalities in competition mathematics: AM–GM–HM $\frac{a_1+\dots+a_n}{n} \ge \sqrt[n]{a_1\cdots a_n}$ , Cauchy–Schwarz $\left(\sum a_i^2\right)\left(\sum b_i^2\right) \ge \left(\sum a_i b_i\right)^2$ and its companion Titu's Lemma $\sum \frac{a_i^2}{b_i} \ge \frac{(\sum a_i)^2}{\sum b_i}$ , Rearrangement, Chebyshev, Jensen, and Schur's inequality $a^r(a-b)(a-c) + b^r(b-a)(b-c) + c^r(c-a)(c-b) \ge 0$ . We give full proofs of Cauchy–Schwarz via the discriminant of $\sum(a_i t - b_i)^2 \ge 0$ and of Schur's inequality for $r=1$ , then apply these tools to signal-to-noise ratio bounds and Kullback–Leibler divergence.

IntuitionWhy Averages Behave the Way They Do

Take two positive numbers, say $4$ and $9$ . Their arithmetic mean is $\frac{4+9}{2}=6.5$ , but their geometric mean is $\sqrt{4\cdot 9}=6$ . The geometric mean is always smaller (or equal, when the numbers are equal) — squeezing two unequal numbers together to multiply them "loses" more than adding them does. This single observation, generalized to $n$ numbers and combined with a handful of companion inequalities (Cauchy–Schwarz, Rearrangement, Chebyshev, Jensen, Schur), is the entire toolkit competition mathematicians use to prove that one algebraic expression is always at least as large as another — turning what looks like a search over infinitely many cases into a few lines of clean algebra.

The gap between arithmetic mean

6.5

and geometric mean

6

4,9

traced as a curve: adjust to see how

f(x) = -x^2+13

visualizes the AM–GM gap

\left(\frac{a+b}{2}\right)^2 - ab = \left(\frac{a-b}{2}\right)^2 \ge 0

SchoolAM–GM–HM and Cauchy–Schwarz

Definition: Three Means Compared

For positive reals $a_1,\dots,a_n$ , the arithmetic mean is $\frac{a_1+\dots+a_n}{n}$ , the geometric mean is $\sqrt[n]{a_1\cdots a_n}$ , and the harmonic mean is $\frac{n}{\frac{1}{a_1}+\dots+\frac{1}{a_n}}$ . The AM–GM–HM chain states arithmetic $\ge$ geometric $\ge$ harmonic, with equality throughout exactly when $a_1=\dots=a_n$ .

\frac{a_1+\dots+a_n}{n} \ge \sqrt[n]{a_1\cdots a_n} \ge \frac{n}{\frac{1}{a_1}+\dots+\frac{1}{a_n}}

Cauchy–Schwarz sharpens this idea to dot products: $\left(\sum a_i^2\right)\left(\sum b_i^2\right) \ge \left(\sum a_i b_i\right)^2$ . A direct corollary, Titu's Lemma (Engel form), is often more convenient for competition fractions: $\sum \frac{a_i^2}{b_i} \ge \frac{(\sum a_i)^2}{\sum b_i}$ , obtained by substituting $a_i \to a_i/\sqrt{b_i}$ and $b_i \to \sqrt{b_i}$ into Cauchy–Schwarz.

\sum \frac{a_i^2}{b_i} \ge \frac{(\sum a_i)^2}{\sum b_i}

Which inequality to reach for
Tool	Best for
AM–GM	Products vs. sums, fixed-sum optimization
Cauchy–Schwarz / Titu	Sums of fractions, dot-product bounds
Rearrangement / Chebyshev	Sums of products of ordered sequences
Jensen	Convex/concave function of an average
Schur	Symmetric three-variable inequalities

UndergraduateFull Proofs: Cauchy–Schwarz and Schur

Theorem: Cauchy–Schwarz Inequality

For real numbers $a_1,\dots,a_n$ and $b_1,\dots,b_n$ : $\left(\sum a_i^2\right)\left(\sum b_i^2\right) \ge \left(\sum a_i b_i\right)^2$ , with equality iff the sequences are proportional.

Why is it true?

This single inequality (and its Engel-form corollary, Titu's Lemma) is the single most useful tool in olympiad inequality problems, converting sums of fractions or products into bounds that are easy to manipulate.

Proof

Step 1: Set up an auxiliary quadratic. Consider the real variable $t$ and the expression $\sum_{i=1}^n (a_i t - b_i)^2$ . Since it is a sum of squares of real numbers, it is always $\ge 0$ for every real $t$ : $\sum(a_i t - b_i)^2 \ge 0$ .

**Step 2: Expand into a quadratic in $t$ .** Expanding, $\sum (a_i t - b_i)^2 = t^2 \sum a_i^2 - 2t \sum a_i b_i + \sum b_i^2$ . Write $A = \sum a_i^2$ , $B = \sum a_i b_i$ , $C = \sum b_i^2$ , so the expression is $At^2 - 2Bt + C \ge 0$ for all real $t$ .

Step 3: Handle the degenerate case. If $A = 0$ then every $a_i = 0$ , so both sides of the claimed inequality $B^2 \le AC$ are $0$ , and the inequality holds trivially (with equality).

**Step 4: Use the discriminant when $A > 0$ .** A quadratic $At^2 - 2Bt + C$ with positive leading coefficient $A$ that is $\ge 0$ for every real $t$ can have at most one real root, so its discriminant cannot be positive: $(2B)^2 - 4AC \le 0$ , i.e. $4B^2 \le 4AC$ , i.e. $B^2 \le AC$ .

Step 5: Conclude. Substituting back, $\left(\sum a_i b_i\right)^2 \le \left(\sum a_i^2\right)\left(\sum b_i^2\right)$ , which is exactly $\left(\sum a_i^2\right)\left(\sum b_i^2\right) \ge \left(\sum a_i b_i\right)^2$ . Equality holds exactly when the discriminant is zero, i.e. the quadratic has a real double root $t_0$ , i.e. $a_i t_0 = b_i$ for every $i$ — the sequences $(a_i)$ and $(b_i)$ are proportional.

Theorem: Schur's Inequality (

r=1

)

For nonnegative reals $a,b,c$ : $a(a-b)(a-c)+b(b-a)(b-c)+c(c-a)(c-b)\ge 0$ , with equality iff $a=b=c$ or two of them are equal and the third is $0$ .

Why is it true?

Schur's inequality is the standard closing move for symmetric three-variable competition inequalities that resist AM–GM or Cauchy–Schwarz directly, especially those involving $a+b+c$ , $ab+bc+ca$ , $abc$ simultaneously.

Proof

Step 1: Reduce by symmetry. The expression $a(a-b)(a-c)+b(b-a)(b-c)+c(c-a)(c-b)$ is symmetric in $a,b,c$ , so without loss of generality assume $a \ge b \ge c \ge 0$ .

Step 2: Group the first two terms. Group $a(a-b)(a-c) + b(b-a)(b-c) = (a-b)\big[a(a-c) - b(b-c)\big]$ , factoring out the common factor $(a-b)$ from both terms (note $b(b-a)(b-c) = -(a-b)\cdot b(b-c)$ ).

Step 3: Simplify the bracket. Expand $a(a-c) - b(b-c) = a^2 - ac - b^2 + bc = (a^2-b^2) - c(a-b) = (a-b)(a+b) - c(a-b) = (a-b)(a+b-c)$ .

Step 4: Combine. Substituting back, the grouped terms equal $(a-b)\cdot(a-b)(a+b-c) = (a-b)^2(a+b-c)$ . So the full expression equals $(a-b)^2(a+b-c) + c(a-c)(b-c)$ (the last term is exactly the third original term, unchanged).

Step 5: Sign-check each piece. Since $a \ge b \ge c \ge 0$ : $(a-b)^2 \ge 0$ always. For the sign of $a+b-c$ : since $a \ge c$ , we have $a - c \ge 0$ , and $b \ge 0$ , so $a+b-c = (a-c)+b \ge 0$ . Hence $(a-b)^2(a+b-c) \ge 0$ . For the second piece: $c \ge 0$ , $a-c \ge 0$ (since $a\ge c$ ), and $b - c \ge 0$ (since $b \ge c$ ), so $c(a-c)(b-c) \ge 0$ as a product of three nonnegative numbers.

Step 6: Conclude. The full expression is a sum of two nonnegative terms, $(a-b)^2(a+b-c) + c(a-c)(b-c) \ge 0$ , proving Schur's inequality for $r=1$ . Equality requires both pieces to vanish: either $a=b$ (making the first term $0$ ) together with $c(a-c)(b-c)=0$ (forced if additionally $a=c$ , giving $a=b=c$ , or $c=0$ giving $a=b, c=0$ ), matching the stated equality condition.

AdvancedReal-World Applications and Worked Examples

Cauchy–Schwarz is not just a competition trick: in signal processing, it bounds the correlation between a signal and a matched filter, giving the maximum achievable signal-to-noise ratio (SNR) of a matched-filter receiver. In information theory, Jensen's inequality (applied to the convex function $-\log$ ) proves the Kullback–Leibler divergence $D_{KL}(P\|Q) = \sum p_i \log\frac{p_i}{q_i}$ is always $\ge 0$ (Gibbs' inequality), the foundational fact making KL divergence a valid (if asymmetric) measure of distance between probability distributions, central to machine learning loss functions like cross-entropy.

Example: Matched-Filter SNR Bound via Cauchy–Schwarz

A receiver observes $y_i = s_i + n_i$ for $i=1,\dots,n$ , where $s_i$ is a known signal and $n_i$ is noise with $\sum n_i^2 \le N$ . The receiver computes the correlation $\sum s_i y_i$ . Use Cauchy–Schwarz to bound how much noise can corrupt this correlation, i.e. bound $|\sum s_i n_i|$ .

Solution

Step 1: Apply Cauchy–Schwarz directly to the sequences $(s_i)$ and $(n_i)$ : $\left(\sum s_i n_i\right)^2 \le \left(\sum s_i^2\right)\left(\sum n_i^2\right)$ .

Step 2: Substitute the noise energy bound $\sum n_i^2 \le N$ and write $E_s = \sum s_i^2$ for the signal energy: $\left(\sum s_i n_i\right)^2 \le E_s \cdot N$ .

Step 3: Take square roots: $|\sum s_i n_i| \le \sqrt{E_s N}$ . Meanwhile the noiseless correlation is exactly $\sum s_i^2 = E_s$ , so the worst-case relative disturbance is $\frac{\sqrt{E_s N}}{E_s} = \sqrt{N/E_s}$ — smaller when signal energy $E_s$ is large relative to noise energy $N$ , which is exactly the intuitive statement that SNR (ratio $E_s/N$ ) controls detection reliability, and Cauchy–Schwarz shows the matched filter $s_i$ is in fact the optimal correlator (any other filter gives a weaker bound), by equality holding only when the noise happens to be proportional to $s_i$ itself.

Example: Proving Non-Negativity of KL Divergence via Jensen

For probability distributions $p_1,\dots,p_n$ and $q_1,\dots,q_n$ (all positive, summing to $1$ ), prove Gibbs' inequality $D_{KL}(P\|Q) = \sum_i p_i \log\frac{p_i}{q_i} \ge 0$ .

Solution

Step 1: Rewrite $D_{KL}(P\|Q) = -\sum_i p_i \log\frac{q_i}{p_i} = \sum_i p_i \cdot \left(-\log\frac{q_i}{p_i}\right)$ , recognizing this as an expectation $\mathbb{E}_{p}\left[-\log \frac{q_i}{p_i}\right]$ weighted by the $p_i$ .

Step 2: Since $-\log$ is a convex function, Jensen's inequality gives $\mathbb{E}[-\log X] \ge -\log \mathbb{E}[X]$ for any random variable $X$ (here $X = q_i/p_i$ with probability $p_i$ ).

Step 3: Compute $\mathbb{E}[X] = \sum_i p_i \cdot \frac{q_i}{p_i} = \sum_i q_i = 1$ , since the $q_i$ form a probability distribution.

Step 4: Combining, $D_{KL}(P\|Q) = \mathbb{E}[-\log X] \ge -\log \mathbb{E}[X] = -\log 1 = 0$ , proving $D_{KL}(P\|Q) \ge 0$ , with equality iff $q_i/p_i$ is constant for all $i$ (by the equality condition of Jensen for strictly convex $-\log$ ), i.e. iff $P = Q$ .

Research frontier as of 2026

Modern research extends these classical inequalities in several directions: matrix and operator versions of Cauchy–Schwarz and Schur are active tools in quantum information theory (bounding fidelity and entanglement measures); "Schur convexity" — functions that respect the majorization order — is a systematic modern framework (surveyed by Marshall, Olkin, Arnold) that explains why so many olympiad inequalities have Schur-like proofs, replacing ad hoc case analysis with a single majorization criterion; and automated theorem provers (e.g. using sum-of-squares / Positivstellensatz certificates) can now mechanically verify or discover many polynomial inequalities of Schur/Cauchy–Schwarz type, an active area connecting real algebraic geometry to competition mathematics through 2026.

In the proof of Cauchy–Schwarz via the discriminant of $\sum(a_i t - b_i)^2 \ge 0$ , what property of the quadratic $At^2-2Bt+C$ is used to conclude $B^2 \le AC$ ?

For which values of $a,b,c$ does Schur's inequality $a(a-b)(a-c)+b(b-a)(b-c)+c(c-a)(c-b)\ge 0$ hold with equality (besides $a=b=c$ )?

Titu's Lemma $\sum \frac{a_i^2}{b_i} \ge \frac{(\sum a_i)^2}{\sum b_i}$ is derived from Cauchy–Schwarz by which substitution?

In the Gibbs' inequality proof that $D_{KL}(P\|Q) \ge 0$ , which inequality is applied to the convex function $-\log$ ?

References

J. Michael Steele (2004). The Cauchy-Schwarz Master Class
Radmila Bulajich Manfrino, José Antonio Gómez Ortega, Rogelio Valdez Delgado (2009). Inequalities: A Mathematical Olympiad Approach
Thomas M. Cover, Joy A. Thomas (2006). Elements of Information Theory