Proof: Let us call a positive integer-valued index formula_5 of a sequence the "peak of the sequence" when formula_6 for every formula_7. Suppose first that the sequence has infinitely many peaks, which means there is a subsequence with the following indices formula_8 and the following terms formula_9. So, the infinite sequence formula_3 in formula_1 has a monotone subsequence, which is formula_12. But suppose now that there are only finitely many peaks, let formula_13 be the final peak and let the first index of a new subsequence formula_12 be set to formula_15. Then formula_16 is not a peak, since formula_16 comes after the final peak, which implies the existence of formula_18 with formula_19 and formula_20. Again, formula_18 comes after the final peak, hence there is an formula_22 where formula_23 with formula_24. Repeating this process leads to an infinite non-decreasing subsequence  formula_25, thereby proving that every infinite sequence formula_3 in formula_1 has a monotone subsequence.