Difference between revisions of "Titu's Lemma"
| 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 inequality]]. | + | It is a direct consequence of [[Cauchy-Schwarz 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. | 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> This is valid because <math>a_1 + a_2 + ... + a_n = b_1 + b_2 + ... + b_n</math> (from the problem statement). <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=== | ||
| + | *Let positive real numbers <math>x</math>, <math>y</math>, and <math>z</math> be roots of the polynomial <math>p(x) = x^3 + bx^2 + cx + d</math> for some real <math>b</math>, <math>c</math>, and <math>d</math>. There exists some minimum integer <math>k>1</math> such that the equation <math>h = \sqrt{\frac{x^2yz + 3x^2y + 2x^2z + 6x^2 + xy^2z + 3xy^2 + y^2z + 3y^2 + xyz^2 + 2xz^2 + yz^2 + 2z^2}{xyz + 3xy + 2xz + 6x + yz + 3y + 2z + 6}}</math> has some solution in <math>x</math>, <math>y</math>, and <math>z</math> when <math>h=k</math> and no solutions when <math>h<k</math>. This is the case if and only if <math>p(x)</math> has y-intercept <math>r</math>, where <math>r</math> is some constant. What is the value of <math>r + k</math>? (Source: [https://artofproblemsolving.com/wiki/index.php/User:Cxsmi cxsmi]) | ||
| + | |||
| + | *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]) | ||
Revision as of 16:35, 14 March 2024
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 }.\]](http://latex.artofproblemsolving.com/2/6/4/264fff665becc96f5f9e05a178f2a31ee3f2603f.png)
It is a direct consequence of Cauchy-Schwarz inequality.
Equality holds when 
for 
.
Titu's lemma is named after Titu Andreescu and is also known as T2 lemma, Engel's form, or Sedrakyan's inequality.
Contents
Examples
Example 1
Given that positive reals 
, 
, and 
are subject to 
, find the minimum value of 
. (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}.\]](http://latex.artofproblemsolving.com/e/6/c/e6c550aa80180085d16847ef9f6d8da37dd06295.png)
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}\]](http://latex.artofproblemsolving.com/d/d/0/dd0c617b2e2fa207ae03826a73984b78ae4a5596.png)
![\[\geq \frac{(1+2+3)^2}{a + b + c}\]](http://latex.artofproblemsolving.com/9/3/1/931521a07fb811cc3666841f35989cc6bcc9b958.png)
![\[= \boxed{36}\]](http://latex.artofproblemsolving.com/2/9/c/29c5311256d817a334a233f2e5dfe4e4afdc05bc.png)
Example 2
Prove Nesbitt's Inequality.
Solution
For reference, Nesbitt's Inequality states that for positive reals , , and , ![\[\frac{a}{b + c} + \frac{b}{a + c} + \frac{c}{a + b} \geq \frac{3}{2}.\]](http://latex.artofproblemsolving.com/8/5/1/8517cfbc92edb09178983dcc3515b3fccedf6a06.png)
We rewrite as follows. ![\[\frac{a^2}{ab + ac} + \frac{b^2}{ab + bc} + \frac{c^2}{ac + bc}\]](http://latex.artofproblemsolving.com/e/a/3/ea3325707e85f9a64bca96669d99fbb379527e98.png)
![\[\geq \frac{(a + b + c)^2}{2(ab + ac + bc)}\]](http://latex.artofproblemsolving.com/a/3/a/a3ad17c7dded3b297a229c8359c68a1a9c9bbbaf.png)
This is the application of Titu's lemma. ![\[\geq \frac{3(ab + bc + ac)}{2(ab + ac + bc)}\]](http://latex.artofproblemsolving.com/f/2/6/f2657888b89af6febef430672accdb8dc0e3d468.png)
This step follows from 
. ![\[= \frac{3}{2}\]](http://latex.artofproblemsolving.com/a/b/0/ab00e731e0992f3a0115be3ed6853a309adc1112.png)
![\[\blacksquare\]](http://latex.artofproblemsolving.com/d/c/d/dcd02eb168c8a18550f9a10c249171171e51f0fd.png)
Example 3
Let 
, 
, 
, 
, 
, 
, , 
be positive real numbers such that 
. 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}\]](http://latex.artofproblemsolving.com/0/f/4/0f4985029cc0227d46a829d94c18ab1432ac8dc6.png)
(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}\]](http://latex.artofproblemsolving.com/c/1/f/c1f0581f753fa5e7023df107da05ba12ded8d6d4.png)
![\[= \frac{(a_1 + a_2 + \ldots + a_n)^2}{2(a_1 + a_2 + ... + a_n)}\]](http://latex.artofproblemsolving.com/9/9/1/99162e3be2ba70c7d8fcaecb40dd8b3f442ba612.png)
This is valid because 
(from the problem statement). ![\[= \frac{a_1 + a_2 + \ldots + a_n}{2}\]](http://latex.artofproblemsolving.com/6/b/5/6b5aa556bdcfc2be1d8e6f5ba2920d9823a298bd.png)
Problems
Introductory
- There exists a smallest possible integer
such that ![\[\frac{(x_1 + 2x_2 + \ldots + 2014x_{2014})^2}{x_1^2 + x_2^2 + \ldots + x_{2014}^2} \leq N\]](//latex.artofproblemsolving.com/2/e/d/2ed5058180b532343a28521955fababd837e1249.png)
for all real sequences 
. Find the sum of the digits of . (Source)
such that ![\[\frac{(x_1 + 2x_2 + \ldots + 2014x_{2014})^2}{x_1^2 + x_2^2 + \ldots + x_{2014}^2} \leq N\]](http://latex.artofproblemsolving.com/2/e/d/2ed5058180b532343a28521955fababd837e1249.png)
for all real sequences 
. Find the sum of the digits of Intermediate
- Let positive real numbers
, 
, and 
be roots of the polynomial 
for some real 
, 
, and 
. There exists some minimum integer 
such that the equation 
has some solution in , , and when 
and no solutions when 
. This is the case if and only if 
has y-intercept 
, where is some constant. What is the value of 
? (Source: cxsmi)
, 
, and 
be roots of the polynomial 
for some real 
. There exists some minimum integer 
such that the equation 
has some solution in 
and no solutions when 
. This is the case if and only if 
has y-intercept 
, where 
? (Source: - Prove that, for all positive real numbers
![\[\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}.\]](//latex.artofproblemsolving.com/a/d/b/adbcc715edd7a68e848bda881783f26fd79183c7.png)
(Source)
![\[\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}.\]](http://latex.artofproblemsolving.com/a/d/b/adbcc715edd7a68e848bda881783f26fd79183c7.png)
(Olympiad
- Let
be positive real numbers such that 
. 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.\]](//latex.artofproblemsolving.com/c/4/d/c4dc01ed1b5465495cee6191571cad0a55e63b9f.png)
(Source)
be positive real numbers such that 
. 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.\]](http://latex.artofproblemsolving.com/c/4/d/c4dc01ed1b5465495cee6191571cad0a55e63b9f.png)
(- Let be positive real numbers such that . Prove that
![\[\frac{1}{a^3(b+c)} + \frac{1}{b^3(c+a)} + \frac{1}{c^3(a+b)} \geq \frac{3}{2}.\]](http://latex.artofproblemsolving.com/e/2/a/e2ad1ca4077a0191129259e27550780a3f1fdeb7.png)
(Source)
