We give an explicit construction with letters , and show that it has leading constant :
Note: is a sequence repeated times. We call each in the construction a . Construction
Our construction is
, and for general ,.
Proof that the construction works
Consider two letters . We show that the alternating subsequence containing and has length less than .
The snippits containing and , in order, are
contributes 1 .
contributes 1 .
contributes terms to the sequence, as it starts with a .
contributes 1 .
contributes 1 .
Thus the length of the subsequence with and is . Setting gives a subsequence of length at most . This applies to all and , so the sequence has order at most .
The sequence itself has length , which is with leading coefficient .
More generally, setting gives a subsequence of length at most , creating a sequence of order , which have length asymptotic to , the upper bound.