排序不等式

维基百科,自由的百科全书
跳到导航 跳到搜索

排序不等式數學上的一條不等式。它可以推導出很多有名的不等式,例如算術幾何平均不等式(簡稱算幾不等式),柯西不等式,和切比雪夫總和不等式。它是說:

如果

,和

是兩組實數。而

的一個排列。排序不等式指出

以文字可以說成是順序和不小於亂序和,亂序和不小於逆序和。與很多不等式不同,排序不等式不需限定的符號。

證明[编辑]

排序不等式可以用數學歸納法證明。關鍵在於下列結果:

,則有

移項得出

重複以上步骤便可得出排序不等式。


我们设Si为b1,b2,...bn 原序列 的前i个数的和,即Si=b1+b2+...bi;设S' 为打乱顺序后的序列,S'i表示乱序后的前i个数的和。 所以有:Si<=S'i. 注意到 a[n]-a[n+1]<=0 则 Si*(a[n]-a[n+1])>=S'i*(a[n]-a[n+1])

得证