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.
- Assume that $i_{k}\leq n\:\text{for}\: k = 1, 2,\dots ,n^{2} + 1.$ Use the generalized pigeonhole principle to show that there are $n + 1$ terms $a_{k_{1}} , a_{k_{2}} ,\dots,a_{k_{n+1}}$ with $i_{k_{1}} = i_{k_{2}} = \dots = i_{k_{n+1}},$ where $1 \leq k_{1} < k_{2} < \dots < k_{n+1}.$
- Show that $a_{k_{j}} > a_{k_{j+1}}\: \text{for}\: j = 1, 2,\dots,n.$ [Hint:Assume that $a_{k_{j}} < a_{k_{j+1}},$ and show that this implies that $i_{k_{j}} > i_{k_{j+1}},$ which is a contradiction.]
- Use parts $(A)\:\text{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.
