Proving Repetition in Sequences

Intro to Proofs · Axiom Academy

EXAMPLE Proving Repetition in Sequences Using the Pigeonhole Principle to prove a long monotonic subsequence must exist Prove the Erdős–Szekeres theorem : any sequence of n^2 + 1 distinct integers must contain a monotonic subsequence of length n + 1 — one that is either strictly increasing or strictly decreasing. We'll build the proof step by step using the Pigeonhole Principle. Each element of the sequence [5,2,8,3,7] is labelled with the pair (L_i, D_i) — the lengths of the longest increasing and decreasing subsequences ending there. Every element lands in a different hole of the grid. If both coordinates were capped at n , only n^2 holes would exist. Nice work — you've built a complete pigeonhole proof. Here's what makes it tick: Clever construction: the right "pigeonholes" were the labels (L_i, D_i) , which capture each element's role in the sequence. Pigeonhole application: with n^2 + 1 elements and only n^2 possible labels, a collision is forced. Contradiction from structure: two distinct elements can't share a label, because either coordinate would have to grow. Existence proof: it doesn't tell you which subsequence works — only that one must exist. Tight bound: a sequence of length n^2 can avoid it (e.g. [2,1,4,3] for n=2 has no monotonic run of length 3), so the n+1 guarantee is sharp. "Label the elements cleverly, then count" recurs all over combinatorics — this is the heart of the Erdős–Szekeres theorem.

This is the written version of the interactive lesson above. See the full Intro to Proofs course.