A proof of Theorem 3 based on the generalized pigeonhole

Chapter 5, Problem 5.2.43

(choose chapter or problem)

A 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 h ::::: n for k = 1 , 2, ... , n2 + l . Use the generalized pigeonhole principle to show that there are n + 1 terms ak1 ' ak2 , ... , akn +1 with ik1 = ik2 = . .. = ikn +1 , where I ::::: k, < k2 < ... < kn+, . b) Show that akj > akj +1 for j = 1 , 2, ... , n. [Hint: Assume that akj < akj +1 , and show that this implies that ikj > ikj +1 , which is a contradiction.] c) Use parts (a) and (b) to show that if there is no increasing subsequence of length n + I, then there must be a decreasing subsequence of this length.