18. Subsequence Existence

First of all, what is a strictly increasing sequence? A sequence of the form $(a_1, a_2, ...)$ where $a_1 < a_2 < a_3 < ... < a_n$ . Whereas if I have a sequence of the form $(a_1, a_2, a_3, ...)$ where $a_1 > a_2 > a_3 > ... > a_n$ then it is a strictly decreasing sequence.

A strictly increasing sequence is a series of numbers where each number is larger than the one before it. For example, in the sequence $2, 4, 6, 8$, each number is greater than the previous one. Conversely, a strictly decreasing sequence consists of numbers where each one is smaller than the last. For example, $8, 6, 4, 2$ represents a strictly decreasing sequence.

Think of a ladder. If you step from one rung to the next that is higher, that's like an increasing sequence. If you are descending the ladder and moving from a higher rung to a lower one, it resembles a decreasing sequence.

Now what does a subsequence mean? A subsequence means here that the values may not be consecutive. That means, I am allowed to miss a few numbers. In the sense, say I take a sequence $1, 3, 0, -5, 2, 8$ and so on. Then I can choose to pick 1 and then exclude 3 and 0 and -5. This is a subsequence. In the same way, I can pick a subsequence saying 3, 2, and 8 that means I skip 0 and -5.

A subsequence is formed from a sequence by removing some elements without changing the order of the remaining elements. For example, from the sequence $1, 3, 0, -5, 2, 8$, you can create subsequences like$1, 2, 8$ or $3, 2$ by skipping certain elements but keeping the order intact.

Imagine you are selecting certain fruits from a basket without worrying about keeping the order. If you start with apples, bananas, oranges, and decide to only take the apples and oranges, you can say that apples or oranges form a subsequence of the original selection.

So what this question basically says is that irrespective of the way your $n + 1$ distinct real numbers are chosen, you always have a subsequence. By that I mean that you have a set of $n + 1$ values going from left to right but need not be in consecutive locations; some of the locations might be skipped. But the number of values are $n + 1$ such that if you view those $n + 1$ values they are either strictly increasing or strictly decreasing.

The main idea here is that no matter what set of distinct real numbers you start with, there will always exist a subsequence consisting of $n + 1$ elements that are either in increasing or decreasing order. This fact is important and holds true for any set of distinct numbers, displaying a kind of inherent order within the chaos of randomness.

Consider a group of people standing in a line of different heights. No matter how they are arranged, you can always find a group of people whose heights can increase upwards or decrease downwards if you choose them wisely. This mirrors the idea of subsequences in the mathematical sense.

So let the arbitrary sequence of $n + 1$ distinct real numbers be denoted by $a_1, a_2, ..., a_{n + 1}$. I will use the pigeonhole principle along with proof by contradiction.

In order to prove the existence of increasing or decreasing subsequences, a common approach is to use the pigeonhole principle combined with a proof by contradiction. The logic here is to assume that all subsequences are of limited length and to show that this leads to a contradiction, implying that our original assumption was wrong.

Imagine placing more pigeons than available houses to store them. If you have six pigeons but only five houses, at least one house must contain more than one pigeon. Similarly, in our proof, if we assume the contrary and find a contradiction, we will confirm that increasingly or decreasingly arranged subsequences must exist.

So assume that the statement is false and that means for each $a_i$ in the sequence, the value $L$ is at most $n$. That means you take any number in the sequence the maximum length increasing subsequence of length $n$ and the maximum length decreasing subsequence is also of length $n$.

If we assume that all increasing and decreasing subsequences from the sequence of numbers can only be of size $n$ or smaller, it sets up a situation where we can pair the lengths of these subsequences. Since we have more numbers in the sequence than pairs, the pigeonhole principle guarantees a contradiction by showing that at least one subsequence must exceed length $n$.

Think about a shelf with too many books for the available space. If you claim that each shelf can only hold a certain number of books, but you have more books than shelves, logically at least some shelf must hold more books than allowed, signaling a contradiction in your original claim.

--