Donate $6,
See Terms and conditions..
Proof of Erdos of his Theorem Concerning Monotonic Subsequences.
|
Donate $6,
|
|
Proof of Erdos of his Theorem Concerning Monotonic Subsequences. |
||
be a sequence of real numbers of length 
.
Then there is a monotonic subsequence of this sequence of length at least n+1.
(of length i) and 
(of length k-i+1). Take all increasing subsequences of
having 
as the last element. Let s(i) be the length of the longest among them. 
such that first element is
. Let t(i) be the length of the longest one.
Assume that a sequence A={
} has not a monotonic subsequence of length n+1. Then all numbers s(i) and t(i) don't exceed n. Reminding the range of i we see that there are
pairs s(i), t(i). But there are only
distinct pairs (x,y), where x,y - natural numbers less of equal n. Hence, for some i1 and i2,
, we have
s(i1)=s(i2), t(i1)=t(i2). But this is impossible. To see this assume first that
. Then clearly s(i2) is bigger than s(i1). If an opposite inequality holds, then t(i1) is bigger than t(i2).
This contradiction proves theorem.