An alternative proof of Theorem 3 based on the generalized pigeonhole principle is outlined in this exercise. The notation used is the same as that used in the proof in the text.
a) Assume that ik ≤ n for k = 1, 2, . . . , n2 + 1. Use the generalized pigeonhole principle to show that there are n + 1 terms ak1, ak2, . . . , akn+1 with ik1 = ik2 = · · · = ikn+1, where 1 ≤ k1 < k2 < · · · < kn+1.
b) Show that akj > akj+1 for j = 1, 2, . . . , n.
c) Use parts (a) and (b) to show that if there is no increasing subsequence of length n + 1, then there must be a decreasing subsequence of this length.