Difference between revisions of "User:Temperal/The Problem Solver's Resource11"

(Mauclarin's Inequality: update)
(Trivial Inequality: proof)
 
(7 intermediate revisions by 2 users not shown)
Line 1: Line 1:
 
__NOTOC__
 
__NOTOC__
<br /><br />
+
{{User:Temperal/testtemplate|page 11}}
{| style='background:lime;border-width: 5px;border-color: limegreen;border-style: outset;opacity: 0.8;width:840px;height:300px;position:relative;top:10px;'
+
==<span style="font-size:20px; color: blue;">Inequalities</span>==
|+ <span style="background:aqua; border:1px solid black; opacity: 0.6;font-size:30px;position:relative;bottom:8px;border-width: 5px;border-color:blue;border-style: groove;position:absolute;top:50px;right:155px;width:820px;height:40px;padding:5px;">The Problem Solver's Resource</span>
+
My favorite topic, saved for last.
|-
+
===Trivial Inequality===
| style="background:lime; border:1px solid black;height:200px;padding:10px;" | {{User:Temperal/testtemplate|page 11}}
+
For any real <math>x</math>, <math>x^2\ge 0</math>, with equality iff <math>x=0</math>.
==<span style="font-size:20px; color: blue;">Advanced Number Theory</span>==
+
 
These are Olympiad-level theorems and properties of numbers that are routinely used on the IMO and other such competitions.
+
Proof: We proceed by contradiction. Suppose there exists a real <math>x</math> such that <math>x^2<0</math>. We can have either <math>x=0</math>, <math>x>0</math>, or <math>x<0</math>. If <math>x=0</math>, then there is a clear contradiction, as <math>x^2 = 0^2 \not < 0</math>. If <math>x>0</math>, then <math>x^2 < 0</math> gives <math>x < \frac{0}{x} = 0</math> upon division by <math>x</math> (which is positive), so this case also leads to a contradiction. Finally, if <math>x<0</math>, then <math>x^2 < 0</math> gives <math>x > \frac{0}{x} = 0</math> upon division by <math>x</math> (which is negative), and yet again we have a contradiction.
 +
 
 +
Therefore, <math>x^2 \ge 0</math> for all real <math>x</math>, as claimed.
 +
 
 +
===Arithmetic Mean/Geometric Mean Inequality===
 +
For any set of real numbers <math>S</math>, <math>\frac{S_1+S_2+S_3....+S_{k-1}+S_k}{k}\ge \sqrt[k]{S_1\cdot S_2 \cdot S_3....\cdot S_{k-1}\cdot S_k}</math> with equality iff <math>S_1=S_2=S_3...=S_{k-1}=S_k</math>.
 +
 
 +
 
 +
===Cauchy-Schwarz Inequality===
 +
 
 +
For any real numbers <math>a_1,a_2,...,a_n</math> and <math>b_1,b_2,...,b_n</math>, the following holds:
 +
 
 +
<math>\left(\sum a_i^2\right)\left(\sum b_i^2\right) \ge \left(\sum a_ib_i\right)^2</math>
 +
 
 +
====Cauchy-Schwarz Variation====
 +
 
 +
For any real numbers <math>a_1,a_2,...,a_n</math> and positive real numbers <math>b_1,b_2,...,b_n</math>, the following holds:
 +
 
 +
<math>\sum\left({{a_i^2}\over{b_i}}\right) \ge {{\sum a_i^2}\over{\sum b_i}}</math>.
 +
 
 +
===Power Mean Inequality===
 +
 
 +
Take a set of functions <math>m_j(a) = \left({\frac{\sum a_i^j}{n}}\right)^{1/j}</math>.
 +
 
 +
Note that <math>m_0</math> does not exist. The geometric mean is <math>m_0 = \lim_{k \to 0} m_k</math>.
 +
For non-negative real numbers <math>a_1,a_2,\ldots,a_n</math>, the following holds:
 +
 
 +
<math>m_x \le m_y</math> for reals <math>x<y</math>.
 +
 
 +
, if <math>m_2</math> is the quadratic mean, <math>m_1</math> is the arithmetic mean, <math>m_0</math> the geometric mean, and <math>m_{-1}</math> the harmonic mean.
 +
 
 +
===RSM-AM-GM-HM Inequality===
 +
For any positive real numbers <math>x_1,\ldots,x_n</math>:
 +
 
 +
<math>\sqrt{\frac{x_1^2+\cdots+x_n^2}{n}} \ge\frac{x_1+\cdots+x_n}{n}\ge\sqrt[n]{x_1\cdots x_n}\ge\frac{n}{\frac{1}{x_1}+\cdots+\frac{1}{x_n}}</math>
 +
 
 +
with equality iff <math>x_1=x_2=\cdots=x_n</math>.
 +
 
 +
===Chebyshev's Inequality===
 +
 
 +
Given real numbers <math>a_1 \ge a_2 \ge ... \ge a_n \ge 0</math> and <math>b_1 \ge b_2 \ge ... \ge b_n</math>, we have
 +
 
 +
<math>{\frac{\sum a_ib_i}{n}} \ge {\frac{\sum a_i}{n}}{\frac{\sum b_i}{n}}</math>.
 +
 
 +
===Minkowski's Inequality===
 +
 
 +
Given real numbers <math>a_1,a_2,...,a_n</math> and <math>b_1,b_2,\ldots,b_n</math>, the following holds:
 +
 
 +
<math>\sqrt{\sum a_i^2} + \sqrt{\sum b_i^2} \ge \sqrt{\sum (a_i+b_i)^2}</math>
 +
 
 +
===Nesbitt's Inequality===
 +
 
 +
For all positive real numbers <math>a</math>, <math>b</math> and <math>c</math>, the following holds:
 +
 
 +
<math>{\frac{a}{b+c}} + {\frac{b}{c+a}} + {\frac{c}{a+b}} \ge {\frac{3}{2}}</math>.
 +
 
 +
===Schur's inequality===
 +
 
 +
Given positive real numbers <math>a,b,c</math> and real <math>r</math>, the following holds:
 +
 
 +
<math>a^r(a-b)(a-c)+b^r(b-a)(b-c)+c^r(c-a)(c-b)\ge 0</math>.
 +
 
 
===Jensen's Inequality===
 
===Jensen's Inequality===
 
For a convex function <math>f(x)</math> and real numbers <math>a_1,a_2,a_3,a_4\ldots,a_n</math> and <math>x_1,x_2,x_3,x_4\ldots,x_n</math>, the following holds:
 
For a convex function <math>f(x)</math> and real numbers <math>a_1,a_2,a_3,a_4\ldots,a_n</math> and <math>x_1,x_2,x_3,x_4\ldots,x_n</math>, the following holds:
Line 13: Line 74:
  
 
===Holder's Inequality===
 
===Holder's Inequality===
For positive real numbers <math>a_{i_{j}}, 1\le i\le m, 1\le j\le n be</math>, the following holds:
+
For positive real numbers <math>a_{i_{j}}, 1\le i\le m, 1\le j\le n</math>, the following holds:
 +
 
 +
<cmath>\prod_{i=1}^{m}\left(\sum_{j=1}^{n}a_{i_{j}}\right)\ge\left(\sum_{j=1}^{n}\sqrt[m]{\prod_{i=1}^{m}a_{i_{j}}}\right)^{m}</cmath>
  
<cmath>\prod_{i=1}^{m}\left(\sum_{j=1}^{n}a_{i_{j}}\right)\ge\left(\sum_{j=1}^{n}\sqrt[m]{\prod_{i=1}^{m}a_{i_{j}}}\right)^{m}</cmath>
 
 
===Muirhead's Inequality===
 
===Muirhead's Inequality===
 
For a sequence <math>A</math> that majorizes a sequence <math>B</math>, then given a set of positive integers <math>x_1,x_2,\ldots,x_n</math>, the following holds:
 
For a sequence <math>A</math> that majorizes a sequence <math>B</math>, then given a set of positive integers <math>x_1,x_2,\ldots,x_n</math>, the following holds:
Line 28: Line 90:
  
 
with equality exactly iff all <math>x_i</math> are equivalent.  
 
with equality exactly iff all <math>x_i</math> are equivalent.  
===Mauclarin's Inequality===
+
===MacLaurin's Inequality===
 
For non-negative real numbers <math>x_1,x_2,x_3 \ldots, x_n</math>, and <math>d_1,d_2,d_3 \ldots, d_n</math> such that
 
For non-negative real numbers <math>x_1,x_2,x_3 \ldots, x_n</math>, and <math>d_1,d_2,d_3 \ldots, d_n</math> such that
<cmath>d_k = \frac{\displaystyle \sum_{ 1\leq i_1 < i_2 < \cdots < i_k \leq n}x_{i_1} x_{i_2} \cdots x_{i_k}}{\displaystyle {n \choose k}}</cmath>, for <math>k\subset [1,n]</math> the following holds:
+
<cmath>d_k = \frac{\sum\limits_{ 1\leq i_1 < i_2 < \cdots < i_k \leq n}x_{i_1} x_{i_2} \cdots x_{i_k}}{{n \choose k}}</cmath>, for <math>k\subset [1,n]</math> the following holds:
  
 
<cmath>d_1 \ge \sqrt[2]{d_2} \ge \sqrt[3]{d_3}\ldots \ge \sqrt[n]{d_n}</cmath>
 
<cmath>d_1 \ge \sqrt[2]{d_2} \ge \sqrt[3]{d_3}\ldots \ge \sqrt[n]{d_n}</cmath>
Line 38: Line 100:
 
[[User:Temperal/The Problem Solver's Resource10|Back to page 10]] | Last page (But also see the  
 
[[User:Temperal/The Problem Solver's Resource10|Back to page 10]] | Last page (But also see the  
 
[[User:Temperal/The Problem Solver's Resource Tips and Tricks|tips and tricks page]], and the  
 
[[User:Temperal/The Problem Solver's Resource Tips and Tricks|tips and tricks page]], and the  
[[User:Temperal/The Problem Solver's Resource Competition|competition]]!
+
[[User:Temperal/The Problem Solver's Resource Proofs|methods of proof]]!
|}<br /><br />
 

Latest revision as of 23:01, 10 January 2009

Introduction | Other Tips and Tricks | Methods of Proof | You are currently viewing page 11.

Inequalities

My favorite topic, saved for last.

Trivial Inequality

For any real $x$, $x^2\ge 0$, with equality iff $x=0$.

Proof: We proceed by contradiction. Suppose there exists a real $x$ such that $x^2<0$. We can have either $x=0$, $x>0$, or $x<0$. If $x=0$, then there is a clear contradiction, as $x^2 = 0^2 \not < 0$. If $x>0$, then $x^2 < 0$ gives $x < \frac{0}{x} = 0$ upon division by $x$ (which is positive), so this case also leads to a contradiction. Finally, if $x<0$, then $x^2 < 0$ gives $x > \frac{0}{x} = 0$ upon division by $x$ (which is negative), and yet again we have a contradiction.

Therefore, $x^2 \ge 0$ for all real $x$, as claimed.

Arithmetic Mean/Geometric Mean Inequality

For any set of real numbers $S$, $\frac{S_1+S_2+S_3....+S_{k-1}+S_k}{k}\ge \sqrt[k]{S_1\cdot S_2 \cdot S_3....\cdot S_{k-1}\cdot S_k}$ with equality iff $S_1=S_2=S_3...=S_{k-1}=S_k$.


Cauchy-Schwarz Inequality

For any real numbers $a_1,a_2,...,a_n$ and $b_1,b_2,...,b_n$, the following holds:

$\left(\sum a_i^2\right)\left(\sum b_i^2\right) \ge \left(\sum a_ib_i\right)^2$

Cauchy-Schwarz Variation

For any real numbers $a_1,a_2,...,a_n$ and positive real numbers $b_1,b_2,...,b_n$, the following holds:

$\sum\left({{a_i^2}\over{b_i}}\right) \ge {{\sum a_i^2}\over{\sum b_i}}$.

Power Mean Inequality

Take a set of functions $m_j(a) = \left({\frac{\sum a_i^j}{n}}\right)^{1/j}$.

Note that $m_0$ does not exist. The geometric mean is $m_0 = \lim_{k \to 0} m_k$. For non-negative real numbers $a_1,a_2,\ldots,a_n$, the following holds:

$m_x \le m_y$ for reals $x<y$.

, if $m_2$ is the quadratic mean, $m_1$ is the arithmetic mean, $m_0$ the geometric mean, and $m_{-1}$ the harmonic mean.

RSM-AM-GM-HM Inequality

For any positive real numbers $x_1,\ldots,x_n$:

$\sqrt{\frac{x_1^2+\cdots+x_n^2}{n}} \ge\frac{x_1+\cdots+x_n}{n}\ge\sqrt[n]{x_1\cdots x_n}\ge\frac{n}{\frac{1}{x_1}+\cdots+\frac{1}{x_n}}$

with equality iff $x_1=x_2=\cdots=x_n$.

Chebyshev's Inequality

Given real numbers $a_1 \ge a_2 \ge ... \ge a_n \ge 0$ and $b_1 \ge b_2 \ge ... \ge b_n$, we have

${\frac{\sum a_ib_i}{n}} \ge {\frac{\sum a_i}{n}}{\frac{\sum b_i}{n}}$.

Minkowski's Inequality

Given real numbers $a_1,a_2,...,a_n$ and $b_1,b_2,\ldots,b_n$, the following holds:

$\sqrt{\sum a_i^2} + \sqrt{\sum b_i^2} \ge \sqrt{\sum (a_i+b_i)^2}$

Nesbitt's Inequality

For all positive real numbers $a$, $b$ and $c$, the following holds:

${\frac{a}{b+c}} + {\frac{b}{c+a}} + {\frac{c}{a+b}} \ge {\frac{3}{2}}$.

Schur's inequality

Given positive real numbers $a,b,c$ and real $r$, the following holds:

$a^r(a-b)(a-c)+b^r(b-a)(b-c)+c^r(c-a)(c-b)\ge 0$.

Jensen's Inequality

For a convex function $f(x)$ and real numbers $a_1,a_2,a_3,a_4\ldots,a_n$ and $x_1,x_2,x_3,x_4\ldots,x_n$, the following holds:

\[\sum_{i=1}^{n}a_i\cdot f(x_i)\ge f(\sum_{i=1}^{n}a_i\cdot x_i)\]

Holder's Inequality

For positive real numbers $a_{i_{j}}, 1\le i\le m, 1\le j\le n$, the following holds:

\[\prod_{i=1}^{m}\left(\sum_{j=1}^{n}a_{i_{j}}\right)\ge\left(\sum_{j=1}^{n}\sqrt[m]{\prod_{i=1}^{m}a_{i_{j}}}\right)^{m}\]

Muirhead's Inequality

For a sequence $A$ that majorizes a sequence $B$, then given a set of positive integers $x_1,x_2,\ldots,x_n$, the following holds:

\[\sum_{sym} {x_1}^{a_1}{x_2}^{a_2}\ldots {x_n}^{a_n}\geq \sum_{sym} {x_1}^{b_1}{x_2}^{b_2}\cdots {x_n}^{b_n}\]

Rearrangement Inequality

For any multi sets ${a_1,a_2,a_3\ldots,a_n}$ and ${b_1,b_2,b_3\ldots,b_n}$, $a_1b_1+a_2b_2+\ldots+a_nb_n$ is maximized when $a_k$ is greater than or equal to exactly $i$ of the other members of $A$, then $b_k$ is also greater than or equal to exactly $i$ of the other members of $B$.

Newton's Inequality

For non-negative real numbers $x_1,x_2,x_3\ldots,x_n$ and $0 < k < n$ the following holds:

\[d_k^2 \ge d_{k-1}d_{k+1}\],

with equality exactly iff all $x_i$ are equivalent.

MacLaurin's Inequality

For non-negative real numbers $x_1,x_2,x_3 \ldots, x_n$, and $d_1,d_2,d_3 \ldots, d_n$ such that \[d_k = \frac{\sum\limits_{ 1\leq i_1 < i_2 < \cdots < i_k \leq n}x_{i_1} x_{i_2} \cdots x_{i_k}}{{n \choose k}}\], for $k\subset [1,n]$ the following holds:

\[d_1 \ge \sqrt[2]{d_2} \ge \sqrt[3]{d_3}\ldots \ge \sqrt[n]{d_n}\]

with equality iff all $x_i$ are equivalent.

Back to page 10 | Last page (But also see the tips and tricks page, and the methods of proof!