Cauchy-Schwarz Inequality

The Cauchy-Schwarz Inequality (often just "Cauchy") is the most versatile inequality in olympiad mathematics. It relates the dot product of two vectors to the product of their magnitudes.

Statement

Theorem (Cauchy-Schwarz Inequality)

For all real numbers

a_{1}, \dots, a_{n}

and

b_{1}, \dots, b_{n}

(a_{1}^{2} + \dots + a_{n}^{2}) (b_{1}^{2} + \dots + b_{n}^{2}) \geq (a_{1} b_{1} + \dots + a_{n} b_{n})^{2}

Equality holds if and only if the sequences are proportional: $\frac{a _{1}}{b _{1}} = \frac{a _{2}}{b _{2}} = \dots = \frac{a _{n}}{b _{n}}$ .

Titu's Lemma (Engel's Form)

A highly useful corollary for fraction sums.

Corollary (Titu's Lemma)

i = 1 \sum n \frac{x _{i}^{2}}{y _{i}} \geq \frac{( \sum x _{i} ) ^{2}}{\sum y _{i}}

where

y_{i} > 0

Proof. Apply Cauchy-Schwarz to sequences $a_{i} = \frac{x _{i}}{y _{i}}$ and $b_{i} = y_{i}$ .

(\sum \frac{x _{i}^{2}}{y _{i}}) (\sum y_{i}) \geq (\sum \frac{x _{i}}{y _{i}} \cdot y_{i})^{2} = (\sum x_{i})^{2}

Dividing by

\sum y_{i}

gives the result. ∎

Applications

1. Bounding Sums

Use Cauchy to turn a sum of products into a product of sums.

Example

Prove that for positive reals

a, b, c

(a + b + c) (\frac{1}{a} + \frac{1}{b} + \frac{1}{c}) \geq 9

Proof. Let $x = (a, b, c)$ and $y = (\frac{1}{a}, \frac{1}{b}, \frac{1}{c})$ . By Cauchy-Schwarz:

(a + b + c) (\frac{1}{a} + \frac{1}{b} + \frac{1}{c}) \geq (a \frac{1}{a} + b \frac{1}{b} + c \frac{1}{c})^{2} = (1 + 1 + 1)^{2} = 9

∎

2. Eliminating Radicals

Cauchy-Schwarz is excellent for removing square roots from expressions.

A + B \leq 2 (A + B)

Practice Problems

Exercise (Problem 1)

Prove that if

x^{2} + y^{2} + z^{2} = 1

, then

- 3 \leq x + y + z \leq 3

Exercise (Problem 2)

Use Titu's Lemma to prove

\frac{a ^{2}}{b} + \frac{b ^{2}}{c} + \frac{c ^{2}}{a} \geq a + b + c

Exercise (Problem 3)

Find the maximum value of

3 x + 4 y

subject to

x^{2} + y^{2} = 25