Harman Patil (Editor)

Chebyshev's sum inequality

Updated on
Edit
Like
Comment
Share on FacebookTweet on TwitterShare on LinkedInShare on Reddit

In mathematics, Chebyshev's sum inequality, named after Pafnuty Chebyshev, states that if

Contents

a 1 ≥ a 2 ≥ ⋯ ≥ a n

and

b 1 ≥ b 2 ≥ ⋯ ≥ b n ,

then

1 n ∑ k = 1 n a k ⋅ b k ≥ ( 1 n ∑ k = 1 n a k ) ( 1 n ∑ k = 1 n b k ) .

Similarly, if

a 1 ≤ a 2 ≤ ⋯ ≤ a n

and

b 1 ≥ b 2 ≥ ⋯ ≥ b n ,

then

1 n ∑ k = 1 n a k b k ≤ ( 1 n ∑ k = 1 n a k ) ( 1 n ∑ k = 1 n b k ) .

Proof

Consider the sum

S = ∑ j = 1 n ∑ k = 1 n ( a j − a k ) ( b j − b k ) .

The two sequences are non-increasing, therefore aj − ak and bj − bk have the same sign for any j, k. Hence S ≥ 0.

Opening the brackets, we deduce:

0 ≤ 2 n ∑ j = 1 n a j b j − 2 ∑ j = 1 n a j ∑ k = 1 n b k ,

whence

1 n ∑ j = 1 n a j b j ≥ ( 1 n ∑ j = 1 n a j ) ( 1 n ∑ k = 1 n b k ) .

An alternative proof is simply obtained with the rearrangement inequality.

Continuous version

There is also a continuous version of Chebyshev's sum inequality:

If f and g are real-valued, integrable functions over [0,1], both non-increasing or both non-decreasing, then

∫ 0 1 f ( x ) g ( x ) d x ≥ ∫ 0 1 f ( x ) d x ∫ 0 1 g ( x ) d x ,

with the inequality reversed if one is non-increasing and the other is non-decreasing.

References

Chebyshev's sum inequality Wikipedia
(Text) CC BY-SA


Similar Topics