Lemma › Guides › Titu's lemma: the statement, the proof, and where to use it
Guide

Titu's lemma: the statement, the proof, and where to use it

Titu's lemma is Cauchy-Schwarz in a shape that fits on one line, and that shape is what makes it useful. If you can see a sum of fractions with squares on top, the lemma replaces the whole sum with a single fraction. It is also called the Engel form or Sedrakyan's inequality.

The statement

For real numbers a1,…,ana_1, \dots, a_n and positive reals b1,…,bnb_1, \dots, b_n,

a12b1+a22b2+⋯+an2bn≥(a1+a2+⋯+an)2b1+b2+⋯+bn.\frac{a_1^2}{b_1} + \frac{a_2^2}{b_2} + \cdots + \frac{a_n^2}{b_n} \ge \frac{(a_1 + a_2 + \cdots + a_n)^2}{b_1 + b_2 + \cdots + b_n}.

Equality holds when the ratios ai/bia_i/b_i are all equal. The aia_i may be negative or zero. The bib_i must be positive.

The proof

For two terms, clear the denominators. The claim is

a2x+c2y≥(a+c)2x+y.\frac{a^2}{x} + \frac{c^2}{y} \ge \frac{(a+c)^2}{x+y}.

Put both sides over xy(x+y)xy(x+y). The left numerator is (a2y+c2x)(x+y)=a2xy+a2y2+c2x2+c2xy(a^2y + c^2x)(x+y) = a^2xy + a^2y^2 + c^2x^2 + c^2xy, and the right numerator is (a+c)2xy=a2xy+2acxy+c2xy(a+c)^2xy = a^2xy + 2acxy + c^2xy. Subtract: what is left is a2y2−2acxy+c2x2=(ay−cx)2a^2y^2 - 2acxy + c^2x^2 = (ay - cx)^2. So the difference of the two sides is (ay−cx)2xy(x+y)\dfrac{(ay - cx)^2}{xy(x+y)}, which is a square over a positive number. That is non-negative, and it is zero exactly when ay=cxay = cx, that is, when a/x=c/ya/x = c/y.

For nn terms, apply the two-term case again and again, merging the first two fractions, then the result with the third, and so on. Or read it as Cauchy-Schwarz applied to the vectors (ai/bi)(a_i/\sqrt{b_i}) and (bi)(\sqrt{b_i}). Their dot product is ∑ai\sum a_i, so (∑ai)2≤(∑ai2/bi)(∑bi)(\sum a_i)^2 \le (\sum a_i^2/b_i)(\sum b_i). Divide by ∑bi\sum b_i and you have the lemma.

The signals

Example: Nesbitt in three lines

For positive reals a,b,ca, b, c, prove

ab+c+bc+a+ca+b≥32.\frac{a}{b+c} + \frac{b}{c+a} + \frac{c}{a+b} \ge \frac32.

The numerators are not squares, so multiply each fraction by its own numerator on top and bottom. The sum becomes ∑a2a(b+c)\sum \dfrac{a^2}{a(b+c)}. Titu's lemma gives

∑a2a(b+c)≥(a+b+c)2a(b+c)+b(c+a)+c(a+b)=(a+b+c)22(ab+bc+ca).\sum \frac{a^2}{a(b+c)} \ge \frac{(a+b+c)^2}{a(b+c) + b(c+a) + c(a+b)} = \frac{(a+b+c)^2}{2(ab+bc+ca)}.

Now (a+b+c)2≥3(ab+bc+ca)(a+b+c)^2 \ge 3(ab+bc+ca), because a2+b2+c2≥ab+bc+caa^2 + b^2 + c^2 \ge ab+bc+ca. So the right side is at least 32\dfrac32. This is the inequality from the archive's Nesbitt problem, and there is a guide on Nesbitt's inequality that compares three ways in.

Example: IMO 1995, Problem 2

The problem: for positive reals a,b,ca, b, c with abc=1abc = 1, prove

1a3(b+c)+1b3(c+a)+1c3(a+b)≥32.\frac{1}{a^3(b+c)} + \frac{1}{b^3(c+a)} + \frac{1}{c^3(a+b)} \ge \frac32.

This looks nothing like a Titu problem. The cubes and the single power of the denominators hide it. Substitute x=1/ax = 1/a, y=1/by = 1/b, z=1/cz = 1/c, so that xyz=1xyz = 1. The first term becomes

1a3(b+c)=x31y+1z=x3yzy+z=x2⋅xyzy+z=x2y+z.\frac{1}{a^3(b+c)} = \frac{x^3}{\frac1y + \frac1z} = \frac{x^3 yz}{y+z} = \frac{x^2 \cdot xyz}{y+z} = \frac{x^2}{y+z}.

The other two terms follow by symmetry. Here 11/y+1/z=yzy+z\dfrac{1}{1/y + 1/z} = \dfrac{yz}{y+z}, which is the step from the first fraction to the second. Now Titu's lemma applies directly:

∑x2y+z≥(x+y+z)22(x+y+z)=x+y+z2.\sum \frac{x^2}{y+z} \ge \frac{(x+y+z)^2}{2(x+y+z)} = \frac{x+y+z}{2}.

Finally, x+y+z≥3x + y + z \ge 3 by AM-GM, since xyz=1xyz = 1. So the sum is at least 32\dfrac32.

When a problem has a product constraint and the terms have mismatched degrees, try replacing each variable with its reciprocal and see if squares appear on top.

Example: a minimum with numbers

Minimise 1x+4y+9z\dfrac1x + \dfrac4y + \dfrac9z for positive x,y,zx, y, z with x+y+z=1x + y + z = 1.

Write it as 12x+22y+32z\dfrac{1^2}{x} + \dfrac{2^2}{y} + \dfrac{3^2}{z}. Titu gives at least (1+2+3)2/(x+y+z)=36(1+2+3)^2/(x+y+z) = 36. Equality needs x:y:z=1:2:3x : y : z = 1 : 2 : 3, so x=1/6x = 1/6, y=1/3y = 1/3, z=1/2z = 1/2. Plug those in: 6+12+18=366 + 12 + 18 = 36. The bound is reached, so 3636 is the minimum.

A lower bound is the minimum only if some input reaches it, and the equality condition in Titu's lemma tells you which input to try.

Where it goes wrong

What to do with this

Take every sum of fractions you have failed on and try to make the numerators squares. If you succeed, write the Titu bound and look at the new denominator. If it collapses to something known, you are done. The AM-GM and Cauchy-Schwarz technique page covers the family this belongs to, and the guide on AM-GM or Cauchy-Schwarz helps you decide between them. The problem archive has more inequalities to practise on.

Related guides

Techniques in this guide

Competitions this guide helps with

Train it on Lemma

Every technique here is taught explicitly, in order. 128 lessons, 1237 curated problems and unlimited generated practice at six difficulties. Free to start, no card, and the paid plan opens with 3 free days.

Find your level