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

I have been studying Pigeonhole Principle and came across this theorem that is mentioned in the Discrete Mathematics book by Rosen. I understand the theorem and understand the example presented along with the same. But I am slightly confused by the what I understand to be the limitations in applicability of this theorem.

For example what about sequences that are not $n^2+1$ elements long, say sequences of length 11? While the theorem can be applied to sequences of length 10 by taking $n$ as 3 ($3^2+1=10$), I cannot find any $n$ such that $n^2+1=11$. Does that mean the theorem is not applicable in such cases? Does that mean there is no strictly increasing (or decreasing) subsequence of any particular length for any such sequences?

I read the theorem over and over again but it does seem like that the theorem is applicable to a very limited set of sequences i.e. sequences whose length can be written in form $n^2+1$. I was wondering if there was any possible relation between sequences of lengths that are not $n^2+1$ (say 7, 8, 9, 11 or 12) and the length of strictly increasing/decreasing sub-sequences that can be observed in such sequences.

• E.g. any sequence Length $3^2+1=10$ must contain a strictly increasing or decreasing subsequence of length $3+1=4$ and similarly a sequence of length $4^2+1=17$ must have such a subsequence length $4+1=5$, all sequences with lengths >10 and <17 have a subsequence of at least length $3+1=4$ by the pigeonhole principle. This is what the theorem is saying, Feb 18 '17 at 4:00
• Erdos Szekeres Theorem Feb 18 '17 at 4:20

Take a sequence of length $11$ and remove one element of your choice. The theorem guarantees that the resulting sequence contains a sequence of $4$ either strictly increasing or strictly decreasing numbers. This subsequence is obviously present also in the original sequence of length $11$.
In general, find the largest $n$ such that $n^2+1$ is less than or equal to the length of your sequence. Then you can apply the pigeonholing theorem.