Subsequence Theorem From Rosen.

Question

There is a theorem

Every sequence of n^2 + 1 distinct real numbers contains a subsequence of length n + 1 that
is either strictly increasing or strictly decreasing.

Proof: Let a1, a2,...,an2+1 be a sequence of n^2 + 1 distinct real numbers.Associate an ordered
pair with each term of the sequence, namely, associate (ik, dk) to the term ak, where ik is the
length of the longest increasing subsequence starting at ak, and dk is the length of the longest
decreasing subsequence starting at ak.
Suppose that there are no increasing or decreasing subsequences of length n + 1. Then ik
and dk are both positive integers less than or equal to n, for k = 1, 2,...,n^2 + 1. Hence, by the
product rule there are n2 possible ordered pairs for (ik, dk). By the pigeonhole principle, two of
these n^2 + 1 ordered pairs are equal. In other words, there exist terms as and at , with s<t
such that is = it and ds = dt . We will show that this is impossible. Because the terms of the
sequence are distinct, either as < at or as > at . If as < at , then, because is = it , an increasing
subsequence of length it + 1 can be built starting at as, by taking as followed by an increasing
subsequence of length it beginning at at . This is a contradiction. Similarly, if as > at , the same
reasoning shows that ds must be greater than dt , which is a contradiction.

 

 

My question is how n^2 ordered pair possible for (ik,dk) ??

Answer 1

What values $i_k$ can take. Well it can't take 0, because  it's a length of increasing subseq. starting at kth position, so even if $a_{k+1}, a_{k+2}, ... , a_{n^2+1}$ are all less than $a_k$, we still have $a_k$, hence length 1. For the sake of contradiction we are assuming that there is no increasing subsequence of length $n+1$, so maximum value is $n$. Same applies to values of $d_k$.

So there are $n$ values for $i_k$, $n$ values for $d_k$, by multiplication rule there are $n^2$ possible values for $(i_k, d_k)$.