GO AWAY! You're not allowed to read this writeup before reading about the monotone sequence theorem! However, TheBooBooKitty asked me to point out that pirated proofs are more valuable than the ones that come in boxes like this one. So for maximal value, don't read this node at all; try to prove the theorem on your own.

Still here? OK, so say we have a finite sequence a1,...,amn+1 with neither an ascending subsequence of length m+1 nor a descending subsequence of length n+1.

Let bi be the length of the longest ascending subsequence which begins at ai, and let ci be the length of the longest descending subsequence which begins there. Obviously, (ai) is always both an ascending and a descending subsequence, so 1≤bi,ci. And our assumption in that bi≤m and ci≤n. So there are m*n different possible pairs of values for (bi,ci). But there are m*n+1 of these values...

By Dirichelet's Pigeonhole Principle (or by plain common sense), this means that for some pair i<j we have bi=bj and ci=cj. 'Cause no matter how good a mathematician you are, you cannot pick mn+1 different values out of a set of just mn values.

Surprisingly, we're done! For suppose ai≤aj. Then the subsequence beginning with ai and continuing with the ascending subsequence of aj is ascending and has length 1+bj=1+bi, in contradiction to the definition of bi. And if ai≥aj, then the subsequence beginning with ai and continuing with the descending subsequence of aj is descending and has length 1+cj=1+ci, in contradiction to the definition of ci.

Either way, we get a contradiction. So our original assumption — that ∀i.bi≤m&ci≤n — is flawed; there exists either a weakly ascending subsequence of length m+1 or a weakly descending subsequence of length n+1.

Log in or register to write something here or to contact authors.