Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "Titu's Lemma"

m
(→‎Solution)
 
(5 intermediate revisions by 3 users not shown)
Line 3: Line 3:
 
<cmath> \frac{ a_1^2 } { b_1 } + \frac{ a_2 ^2 } { b_2 } + \cdots + \frac{ a_n ^2 } { b_n } \geq \frac{ (a_1 + a_2 + \cdots+ a_n ) ^2 } { b_1 + b_2 + \cdots+ b_n }. </cmath>
 
<cmath> \frac{ a_1^2 } { b_1 } + \frac{ a_2 ^2 } { b_2 } + \cdots + \frac{ a_n ^2 } { b_n } \geq \frac{ (a_1 + a_2 + \cdots+ a_n ) ^2 } { b_1 + b_2 + \cdots+ b_n }. </cmath>
  
−
It is a direct consequence of Cauchy-Schwarz theorem as follows,
+
It is a direct consequence of [[Cauchy-Schwarz inequality]].
−
\begin{align*}
 
−
\left(\frac{ a_1^2 } { b_1 } + \frac{ a_2 ^2 } { b_2 } + \cdots + \frac{ a_n ^2 } { b_n } \right)  \left( b_1 + b_2 + \cdots+ b_n \right) &\geq (a_1 + a_2 + \cdots+ a_n ) ^2,\\
 
−
\frac{ a_1^2 } { b_1 } + \frac{ a_2 ^2 } { b_2 } + \cdots + \frac{ a_n ^2 } { b_n } &\geq \frac{ (a_1 + a_2 + \cdots+ a_n ) ^2 } { b_1 + b_2 + \cdots+ b_n }
 
−
\end{align*}
 
  
−
Titu's lemma is named after Titu Andreescu, and is also known as T2 lemma, Engel's form, or Sedrakyan's inequality.
+
Equality holds when <math>a_i = kb_i</math> for <math>1 \leq i \leq n</math>.
 +
 
 +
Titu's lemma is named after Titu Andreescu and is also known as T2 lemma, Engel's form, or Sedrakyan's inequality.
 +
 
 +
==Examples==
 +
===Example 1===
 +
Given that positive reals <math>a</math>, <math>b</math>, and <math>c</math> are subject to <math>a + b + c = 1</math>, find the minimum value of <math>\frac{1}{a} + \frac{4}{b} + \frac{9}{c}</math>. (Source: [https://artofproblemsolving.com/wiki/index.php/User:Cxsmi cxsmi])
 +
 
 +
====Solution====
 +
This is a somewhat standard application of Titu's lemma. Notice that <cmath>\frac{1}{a} + \frac{4}{b} + \frac{9}{c} = \frac{1^2}{a} + \frac{2^2}{b} + \frac{3^2}{c}.</cmath> When solving problems with Titu's lemma, the goal is to get perfect squares in the numerator. Now, we can apply the lemma. <cmath>\frac{1^2}{a} + \frac{2^2}{b} + \frac{3^2}{c}</cmath> <cmath>\geq \frac{(1+2+3)^2}{a + b + c}</cmath> <cmath>= \boxed{36}</cmath>
 +
 
 +
===Example 2===
 +
Prove [https://artofproblemsolving.com/wiki/index.php/Nesbitt%27s_Inequality Nesbitt's Inequality].
 +
 
 +
====Solution====
 +
For reference, Nesbitt's Inequality states that for positive reals <math>a</math>, <math>b</math>, and <math>c</math>, <cmath>\frac{a}{b + c} + \frac{b}{a + c} + \frac{c}{a + b} \geq \frac{3}{2}.</cmath> We rewrite as follows. <cmath>\frac{a^2}{ab + ac} + \frac{b^2}{ab + bc} + \frac{c^2}{ac + bc}</cmath> <cmath>\geq \frac{(a + b + c)^2}{2(ab + ac + bc)}</cmath> This is the application of Titu's lemma. <cmath>\geq \frac{3(ab + bc + ac)}{2(ab + ac + bc)}</cmath> This step follows from <math>a^2 + b^2 + c^2 \geq ab + ac + bc \implies (a + b + c)^2 = a^2 + b^2 + c^2 + 2(ab + bc + ac) \geq 3(ab + bc + ac)</math>. <cmath>= \frac{3}{2}</cmath> <cmath>\blacksquare</cmath>
 +
 
 +
===Example 3===
 +
Let <math>a_1</math>, <math>a_2</math>, <math>\cdots</math>, <math>a_n</math>, <math>b_1</math>, <math>b_2</math>, <math>\cdots</math>, <math>b_n</math> be positive real numbers such that <math>a_1 + a_2 + \cdots + a_n = b_1 + b_2 + \cdots + b_n</math>.  Show that
 +
<cmath> \frac{a_1^2}{a_1 + b_1} + \frac{a_2^2}{a_2 + b_2} + \cdots + \frac{a_n^2}{a_n + b_n} \geq \frac{a_1 + a_2 + \cdots + a_n}{2} </cmath> ([https://artofproblemsolving.com/wiki/index.php/1991_APMO_Problems/Problem_3 Source])
 +
 
 +
====Solution====
 +
By Titu's Lemma,
 +
<cmath>\frac{a_1^2}{a_1 + b_1} + \frac{a_2^2}{a_2 + b_2} + \cdots + \frac{a_n^2}{a_n + b_n} \geq \frac{(a_1 + a_2 + \ldots + a_n)^2}{a_1 + a_2 + ... + a_n + b_1 + b_2 + ... + b_n}</cmath> <cmath>= \frac{(a_1 + a_2 + \ldots + a_n)^2}{2(a_1 + a_2 + ... + a_n)}</cmath> <cmath>= \frac{a_1 + a_2 + \ldots + a_n}{2}</cmath> <cmath>\blacksquare</cmath>
 +
 
 +
==Problems==
 +
===Introductory===
 +
*There exists a smallest possible integer <math>N</math> such that <cmath>\frac{(x_1 + 2x_2 + \ldots + 2014x_{2014})^2}{x_1^2 + x_2^2 + \ldots + x_{2014}^2} \leq N</cmath> for all real sequences <math>x_1, x_2, ..., x_{2014}</math>. Find the sum of the digits of <math>N</math>. ([https://brilliant.org/wiki/titus-lemma/ Source])
 +
 
 +
===Intermediate===
 +
*Prove that, for all positive real numbers <math>a, b, c,</math> <cmath>\frac{1}{a^3+b^3+abc}+\frac{1}{b^3+c^3+abc}+\frac{1}{a^3+c^3+abc} \le \frac{1}{abc}.</cmath> ([https://artofproblemsolving.com/wiki/index.php/1997_USAMO_Problems/Problem_5 Source])
 +
 
 +
===Olympiad===
 +
*Let <math>a, b, c</math> be positive real numbers such that <math>abc = 1</math>. Prove that <cmath>\frac{ab}{a^5 + b^5 + ab} + \frac{bc}{b^5 + c^5 + bc} + \frac{ac}{a^5 + c^5 + ac} \leq 1.</cmath> ([https://artofproblemsolving.com/downloads/printable_post_collections/3947 Source])
 +
 
 +
*Let <math>a, b, c</math> be positive real numbers such that <math>abc = 1</math>. Prove that
 +
<cmath> \frac{1}{a^3(b+c)} + \frac{1}{b^3(c+a)} + \frac{1}{c^3(a+b)} \geq \frac{3}{2}. </cmath> ([https://artofproblemsolving.com/wiki/index.php/1995_IMO_Problems/Problem_2 Source])

Latest revision as of 15:39, 18 June 2025

Titu's lemma states that:

\[\frac{ a_1^2 } { b_1 } + \frac{ a_2 ^2 } { b_2 } + \cdots + \frac{ a_n ^2 } { b_n } \geq \frac{ (a_1 + a_2 + \cdots+ a_n ) ^2 } { b_1 + b_2 + \cdots+ b_n }.\]

It is a direct consequence of Cauchy-Schwarz inequality.

Equality holds when $a_i = kb_i$ for $1 \leq i \leq n$.

Titu's lemma is named after Titu Andreescu and is also known as T2 lemma, Engel's form, or Sedrakyan's inequality.

Examples

Example 1

Given that positive reals $a$, $b$, and $c$ are subject to $a + b + c = 1$, find the minimum value of $\frac{1}{a} + \frac{4}{b} + \frac{9}{c}$. (Source: cxsmi)

Solution

This is a somewhat standard application of Titu's lemma. Notice that \[\frac{1}{a} + \frac{4}{b} + \frac{9}{c} = \frac{1^2}{a} + \frac{2^2}{b} + \frac{3^2}{c}.\] When solving problems with Titu's lemma, the goal is to get perfect squares in the numerator. Now, we can apply the lemma. \[\frac{1^2}{a} + \frac{2^2}{b} + \frac{3^2}{c}\] \[\geq \frac{(1+2+3)^2}{a + b + c}\] \[= \boxed{36}\]

Example 2

Prove Nesbitt's Inequality.

Solution

For reference, Nesbitt's Inequality states that for positive reals $a$, $b$, and $c$, \[\frac{a}{b + c} + \frac{b}{a + c} + \frac{c}{a + b} \geq \frac{3}{2}.\] We rewrite as follows. \[\frac{a^2}{ab + ac} + \frac{b^2}{ab + bc} + \frac{c^2}{ac + bc}\] \[\geq \frac{(a + b + c)^2}{2(ab + ac + bc)}\] This is the application of Titu's lemma. \[\geq \frac{3(ab + bc + ac)}{2(ab + ac + bc)}\] This step follows from $a^2 + b^2 + c^2 \geq ab + ac + bc \implies (a + b + c)^2 = a^2 + b^2 + c^2 + 2(ab + bc + ac) \geq 3(ab + bc + ac)$. \[= \frac{3}{2}\] \[\blacksquare\]

Example 3

Let $a_1$, $a_2$, $\cdots$, $a_n$, $b_1$, $b_2$, $\cdots$, $b_n$ be positive real numbers such that $a_1 + a_2 + \cdots + a_n = b_1 + b_2 + \cdots + b_n$. Show that \[\frac{a_1^2}{a_1 + b_1} + \frac{a_2^2}{a_2 + b_2} + \cdots + \frac{a_n^2}{a_n + b_n} \geq \frac{a_1 + a_2 + \cdots + a_n}{2}\] (Source)

Solution

By Titu's Lemma, \[\frac{a_1^2}{a_1 + b_1} + \frac{a_2^2}{a_2 + b_2} + \cdots + \frac{a_n^2}{a_n + b_n} \geq \frac{(a_1 + a_2 + \ldots + a_n)^2}{a_1 + a_2 + ... + a_n + b_1 + b_2 + ... + b_n}\] \[= \frac{(a_1 + a_2 + \ldots + a_n)^2}{2(a_1 + a_2 + ... + a_n)}\] \[= \frac{a_1 + a_2 + \ldots + a_n}{2}\] \[\blacksquare\]

Problems

Introductory

  • There exists a smallest possible integer $N$ such that \[\frac{(x_1 + 2x_2 + \ldots + 2014x_{2014})^2}{x_1^2 + x_2^2 + \ldots + x_{2014}^2} \leq N\] for all real sequences $x_1, x_2, ..., x_{2014}$. Find the sum of the digits of $N$. (Source)

Intermediate

  • Prove that, for all positive real numbers $a, b, c,$ \[\frac{1}{a^3+b^3+abc}+\frac{1}{b^3+c^3+abc}+\frac{1}{a^3+c^3+abc} \le \frac{1}{abc}.\] (Source)

Olympiad

  • Let $a, b, c$ be positive real numbers such that $abc = 1$. Prove that \[\frac{ab}{a^5 + b^5 + ab} + \frac{bc}{b^5 + c^5 + bc} + \frac{ac}{a^5 + c^5 + ac} \leq 1.\] (Source)
  • Let $a, b, c$ be positive real numbers such that $abc = 1$. Prove that

\[\frac{1}{a^3(b+c)} + \frac{1}{b^3(c+a)} + \frac{1}{c^3(a+b)} \geq \frac{3}{2}.\] (Source)

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=Titu%27s_Lemma&oldid=251483"