An unavoidable pattern
A list can alternate between rises and falls without being monotone itself. A subsequence need not use consecutive entries: it keeps selected entries in their original order. How long must a list be before some long increasing or decreasing subsequence is unavoidable?
Throughout, are positive integers and the entries are distinct real numbers. Distinctness matters: a constant list of arbitrary length has no strictly increasing or decreasing subsequence of length two.
Definition 2.2.1
(Subsequences and strict monotonicity)
Let be a finite sequence. A subsequence of length is for indices ; the indices increase, but they need not be consecutive. The subsequence is increasing if and decreasing if . Increasing and decreasing mean strictly so throughout this note. A single entry is both an increasing and a decreasing subsequence of length one.
The argument uses the pigeonhole principle in its simplest form: if more than objects are placed into boxes, some box receives at least two objects.
Record two lengths at each position
Theorem 2.2.2
(A sharp monotone-subsequence bound)
Every sequence of distinct real numbers contains either a strictly increasing subsequence of length at least or a strictly decreasing subsequence of length at least .
Proof
(Distinct length pairs and the pigeonhole principle)
For each position , let be the length of a longest increasing subsequence ending at position and the length of a longest decreasing subsequence ending there. Both exist and are at least one. If , distinctness gives either or . In the first case, append to a longest increasing subsequence ending at , obtaining . In the second, the analogous decreasing subsequence gives . In either case the ordered pairs and differ.
Suppose neither desired subsequence exists. Then every lies in and every lies in . There are only possible pairs but positions, so the pigeonhole principle forces two equal pairs, a contradiction.
Proof X-ray
Why one length is not enough
The proof turns positions into pigeons and length pairs into boxes, and its one real move is the injectivity of the map from position to the pair. Distinctness is used exactly there: it guarantees that any two positions compare strictly one way or the other. An earlier smaller entry forces the increasing length to grow, but an earlier larger entry need not; the decreasing length handles precisely that other case. Recording only one of the two lengths would leave many positions in the same box. The phrase ending at position is also essential: appending the later entry is legitimate only because the subsequence being extended stops at the earlier position. The contradiction hypothesis then bounds the boxes by times , which is why the count appears.
The conclusion is an either-or statement; a sequence can contain both kinds, and the proof does not say which kind occurs.
Concept lensStructural
Sorting positions into decreasing classes
The increasing lengths alone already split the positions into decreasing subsequences. If and , then , since would give . So each class , read in order, is decreasing. If no increasing subsequence has length , there are at most classes covering positions, and one class has at least members. For the classes are and .
An example and a sharpness construction
Proposition 2.2.3
(The bound cannot be lowered)
For all positive integers there is a sequence of distinct integers with no increasing subsequence of length and no decreasing subsequence of length .
Proof
(Decreasing blocks in increasing order)
Form blocks of length : within each block write its consecutive integers in decreasing order, and make every number in each later block larger than every number in every earlier block. For instance, block for can be . The sequence has distinct entries. Two entries of one block decrease, so an increasing subsequence uses at most one entry per block, and its length is at most . An entry of a later block exceeds every entry of an earlier block, so a decreasing subsequence cannot use entries from two different blocks, and its length is at most .
Thus cannot be reduced in the theorem for arbitrary distinct sequences.
Worked example 2.2.4
(Four entries are not enough when )
With , every sequence of five distinct numbers has an increasing or decreasing subsequence of length three. Four entries do not suffice: the block construction gives . Its first two entries decrease, its last two decrease, and every entry in the first pair is smaller than every entry in the second. An increasing subsequence takes at most one from each pair, so it has length at most two. A decreasing subsequence cannot move from the first pair to the larger second pair, so it also has length at most two.
Worked example 2.2.5
(Tracing the length pairs on five entries)
Take , again with . For , look back for smaller entries: , since extends , extends or , and extends . For , look back for larger entries: , since extends or , extends , and extends the decreasing pair .
The pairs are pairwise distinct, as the proof predicts. Only four pairs fit in , so the fifth must leave the box: here , witnessed by .
Worked example 2.2.6
(The edge case )
With the theorem concerns distinct entries and says: either some earlier entry is smaller than some later one, or the whole sequence decreases. This is immediate, since a sequence with no increasing pair is decreasing at every step. The sharpness construction with is a single block , which has no increasing pair and decreasing length exactly . In the proof, if there is no increasing pair, every equals , so the pairs reduce to the values , which must be distinct positive integers; one of them is at least .
Common mistakes
Counterexample mode
Consecutive runs solve a different problem
Claim: among rs plus one distinct numbers there is a run of plus one consecutive increasing entries or plus one consecutive decreasing entries. Take and equal to two and the five entries 2, 1, 4, 3, 5. The consecutive steps go down, up, down, up, so every monotone run of consecutive entries has length two and the claim fails. The theorem is still satisfied: 1, 3, 5 is an increasing subsequence of length three, using non-adjacent entries. Extending the zigzag 2, 1, 4, 3, 6, 5, and so on keeps every consecutive run at length two for any length, so no bound of the form rs plus one holds for runs. The theorem concerns subsequences only.
The two errors below concern how the conclusion and the recorded lengths are read.
Common mistake
(Reading “or” as “and”)
The theorem guarantees one of the two subsequences, not both. The sequence has an increasing subsequence of length five and no decreasing subsequence of length two. A proof that tries to produce both kinds from the pigeonhole step proves something false.
Common mistake
(Longest in the prefix instead of longest ending here)
If and are replaced by the longest monotone subsequences anywhere among the first entries, the pairs need not differ. For these prefix lengths are : positions three and four collide although . Appending requires a subsequence that ends at position .
Exercises
Quick check
(Why must ten distinct real numbers contain an increasing or decreasing subsequence of length four?)
Choose and .
Solution · Answer
Take : then , so the theorem gives an increasing subsequence of length at least or a decreasing one of length at least .
Quick check
(Give nine distinct numbers with neither an increasing nor a decreasing subsequence of length four.)
Use the block construction.
Solution · Answer
Use . Each decreasing block has length three, all later blocks are larger, and an increasing subsequence takes at most one from each block, so both monotone lengths are at most three.
Quick check
(For , compute the pairs at all four positions.)
Look back for smaller entries to compute and for larger entries to compute .
Solution · Answer
The pairs are , respectively. For example witnesses , while witnesses , and or witnesses .
Quick check
(Why does the proof not apply unchanged to with strict subsequences?)
Check the step that compares two positions.
Solution · Answer
Equal entries satisfy neither nor , so neither recorded length is forced to grow: every position has the pair . In fact the constant list has no strict monotone subsequence of length two, so the distinctness hypothesis cannot be dropped.