Rosen example 12 Ch 5.2

Question

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

Comments

did you tried with sample examples ?

---

yes I tried with examples...but I want a formal proof @Shaik Masthan brother!

Answer 1

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 !