用
鸽巢原理的加强形式证明
证：令mk表示从ak（k=1,2…，n²+1）开始的最长递增子序列的长度
若存在mk≥n+1（1≤k≤n²+1），则存在长为n+1的递增子序列，结论成立
若对任意的k（1≤k≤n²+1），有1≤mk≤n（k=1,2…，n²+1），这相当于把n²+1个物品
m1，m2，…，m（n²+1）放入n个盒子1,2,…，n中，有鸽巢原理知，必有一个盒子里面至少有n+1个物品，即存在k1＜k2＜…＜kn+1及1≤i≤n
使得mk1=mk2=…=mk+1=i
则对应于这些下标的时数序列必满足
ak1≥ak2≥…≥a（kn+1），
即存在长为n+1的递减子序列。否则，若有某个j（1≤j≤n）使得a[k（j）]＜a[k(j+1)]
那么由从a[k（j）]开始的最长递增子序列的长度m[k（j）]必大于从a[k(j+1)]开始的最长递增子序列的长度m[k(j+1)]，即有m[k（j）]≥m[k(j+1)]+1，矛盾。
因此结论成立