AoPSWiki
Looking for a challenging geometry text? Preparing for MATHCOUNTS or the AMC exams? Check out Art of Problem Solving's Introduction to Geometry by Richard Rusczyk.
Personal tools

Chebyshev's Inequality

From AoPSWiki

Chebyshev's inequality, named after Pafnuty Chebyshev, states that if a_1\geq a_2\geq ... \geq a_n and b_1\geq b_2\geq ... \geq b_n then the following inequality holds:

n \left(\sum_{i=1}^{n}a_ib_i\right)\geq\left(\sum_{i=1}^{n}a_i\right)\left(\sum_{i=1}^{n}b_i\right).

On the other hand, if a_1\geq a_2\geq ... \geq a_n and b_n\geq b_{n-1}\geq ... \geq b_1 then: n \left(\sum_{i=1}^{n}a_ib_i\right)\leq\left(\sum_{i=1}^{n}a_i\right)\left(\sum_{i=1}^{n}b_i\right).

Proof

Chebyshev's inequality is a consequence of the Rearrangement inequality, which gives us that the sum S=a_1b_{i_1}+a_2b_{i_2}+...+a_nb_{i_n} is maximal when i_k=k.

Now, by adding the inequalities:

\sum_{i=1}^{n}a_ib_i\geq a_1b_1+a_2b_2+...+a_n b_{n},

\sum_{i=1}^{n}a_ib_i\geq a_1b_2+a_2b_3+...+a_nb_1,

...

\sum_{i=1}^{n}a_ib_i\geq a_1b_n+a_2b_1+...+a_nb_{n-1}

we get the initial inequality.

Retrieved from "http://www.artofproblemsolving.com/Wiki/index.php/Chebyshev%27s_Inequality"
Want to learn how to tackle those tough AMC/AIME/Olympiad algebra problems? Check out Art of Problem Solving's Intermediate Algebra by Richard Rusczyk and Mathew Crawford. Over 1600 problems!
© Copyright 2008 AoPS Incorporated. All Rights Reserved. • Foundation • Privacy • Contact Us