排序不等式的证明

设命题为,在的序列 上排序不等式成立

成立,则对于的序列
结合的最大排法里,,由于剩下的序列式长度为的序列,则成立
,而是,由于除外的序列,则最优排法
但是这和题设矛盾,因为子序列的长度,若则由的定义引出矛盾
,则此时
所以
Advertisements