__A supplement on EWD591 “The problem of the maximum length of an ascending subsequence.”__

In the algorithm described in EWD591 occur the array elements ` m`(1) through ` m`(`k`) where `k `= the maximum length of an ascending subsequence taken from `A`(1) through `A`(`n`). In the computational step that increases `n` by 1 , either `k` is increased by 1 and the `m`-sequence is extended by a value ( = the new `A`(`n`), to be precise), or for some value `j` (1 ≤ `j` ≤ `k`) `m`(`j`), that was larger than the new `A`(`n`) is made equal to the new `A`(`n`) . In short: after the adjustment the new `A`(`n`) occurs in the `m`-sequence and existing `m`-values never increase.

Suppose that in parallel we determine `h` = the maximum length of a descending subsequence taken from `A`(1) through `A`(`n`) . That computation would comprise a corresponding array `p`(1) through `p`(`h`), that after each adjustment would contain the new `A`(`n`) and whose elements never decrease. If, for a given `i` (1 ≤ `i` ≤ `h`) and ` j` (1 ≤ `j` ≤ `k`) we have `m`(`j`) ≤ `p`(`i`) we call this “an inversion”; because `m`(`j`) never increases and `p`(`i`) never dercreases, an inversion, once introduced, remains in existence.

If we mentally extend the `m`-sequence at the high end with values = + infinity, and extend the `p`-sequence at the high end with values = – infinity, each step *effectively* decreases an `m`-value by making it equal to the new `A`(`n`) and *effectively* increases a `p`-value by making it equal to the new `A`(`n`). Hence each step increases the total number of inversions by at least one, and we conclude that the total number of inversions ≥ the length `n` of the sequence. Furthermore `h`*`k` ≥ the total number of inversions, hence

`h` * `k` ≥ `n` .

From this we deduce that for `n` ≥ `N`^{2} + 1, we have `h` > `N` *or* `k` > `N`, and that was the theorem we wanted to prove: a sequence of length greater than `N`^{2} has an ascending or descending subsequence of length greater than `N` .