$n$ distinct real numbers has a monotone subsequence of length $k$ if $n \ge (k-1)^2 + 1$

Question

I'm working through some problems and I just completed the proof that if $n\ge R(k)$ for a sequence of distinct real numbers $a_1, a_2, a_3, ..., a_n$ has a monotone subsequence of length $k$, that is we have a subsequence of length $k$ such that the $a_i$'s are in increasing or decreasing order.

The next question is making a better bound for $n$. It asks to prove that the previous result holds for $n\ge (k-1)^2 +1 $.

My idea is to label each term of the sequence based on the longest monotone sequence that end with that specific term, but I'm not exactly sure where to go from here. Any help would be greatly appreciated!

Answer 1

You're well on your way. I'll give you a hint: try assigning two labels to each position in the sequence:

• $b_i$ is the length of the longest increasing subsequence ending at position $i$;
• $c_i$ is the length of the longest decreasing subsequence ending at position $i$.

Then compare the tuples $(b_i,c_i)$ and $(b_j,c_j)$ for $i \neq j$.