https://math.berkeley.edu/~arash/55/6_2.pdf
PS :- proof present in this pdf at page 2, i am going to just explain the proof given by them only, it is not my own proof !
there are n$^2$+1 distinct numbers sequence, ( just restricted to natural numbers for simplification only ).
we have to show that " contains a subsequence of length n+1 that is either strictly increasing or strictly decreasing. "
let assign a pair of values to each number (i$_a$,d$_a$), where i$_a$ indicates the longest increasing sub sequence from the number 'a' and d$_a$ indicates the longest decreasing sub sequence from the number 'a'.
Proof by contradiction :-
let assume there is no subsequence of length n+1 that is either strictly increasing or strictly decreasing. Therefore atmost there can be present a subsequence of length n, that is either strictly increasing or strictly decreasing.
So the value of i$_a$= 1 to n ( both are inclusive ), d$_a$= 1 to n ( both are inclusive ) for any a ( i.e., a ∈[1 to n$^2$+1] )
Therefore for a number the pair can have the possibility of numbers = (i$_a$,d$_a$) = ( n*n ) = n$^2$ possible pairs. But we have totally n$^2$+1 numbers.
∴ there should be 2 numbers (a,b) which have the same pair, (i$_a$,d$_a$) = (i$_b$,d$_b$) ==> i$_a$ = i$_b$ and d$_a$ = d$_b$ where a ≠ b.
Is this possible ?
the relation between a and b is
case 1:- a < b
we know that, b have the increasing subsequence is i$_b$ from b.
then from a, i$_a$ should be atleast 1+i$_b$ ===> i$_a$ ≠ i$_b$
case 2:- a > b
we know that, b have the decreasing subsequence is d$_b$ from b.
then from a, d$_a$ should be atleast 1+d$_b$ ===> d$_a$ ≠ d$_b$
So either case 1 or case 2 must be happen ==> either i$_a$ ≠ i$_b$ or d$_a$ ≠ d$_b$ happen. So there are no two numbers where (i$_a$,d$_a$) = (i$_b$,d$_b$) , So our assumption should be wrong !
Hence Proved !
