18.1.5. Contradiction and Conclusion

Here we want to show the following that you take any sequence of $n + 1$ distinct real numbers. They are arbitrary real numbers; may be positive, negative in any order you take them. The only condition is that they have to be distinct. Then the claim is that irrespective of the $n + 1$ real numbers that you have in your sequence you always have a subsequence of length $n + 1$ which is either strictly increasing or strictly decreasing.

This chunk introduces the central idea of the proof that from any sequence of $n + 1$ distinct real numbers, you can always find a subsequence of the same length that is either monotonically increasing or decreasing. This means that no matter how you arrange the numbers, the claim holds true for them. An increasing sequence is one where each number is larger than the previous, while a decreasing sequence has each number smaller than the previous one.

Imagine you have a set of different heights for people: 5 feet, 6 feet, 5.5 feet, and 5.8 feet. No matter the arrangement, you can always select a group of four people that is either all arranged from shortest to tallest (increasing) or from tallest to shortest (decreasing).

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 < ...$. Whereas if I have a sequence of the form ($a_1, a_2, a_3, ...$) where $a_1 > a_2 > a_3 ... > a_{k}$ then it is a strictly decreasing sequence.

The concept of subsequences is essential for understanding how we can extract ordered elements from a given sequence. A strictly increasing subsequence means that each subsequent number is greater than the previous one, while a strictly decreasing subsequence means that each number is lower than the one before it. This clarity helps when searching for longer ordered sequences within a larger collection.

Think of a race where each runner's finishing times are recorded. If we select runners who finished in increasing order of their times, we're forming an increasing sequence. Conversely, if we select runners based on their finishing times in decreasing order (the slowest finishes first), we’re forming a decreasing sequence.

Now what does a subsequence mean? A subsequence means that the values may not be consecutive. That means I am allowed to miss a few numbers. For example, 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, I skip -5.

A subsequence is essentially a selection of elements from the original sequence that maintains the original order but does not need to be consecutive. The examples highlight how we can freely choose certain numbers while ignoring others which still preserves the order of their appearance in the sequence.

Imagine you’re reviewing a list of groceries: apples, bananas, carrots, dates. You can choose some items like apples, carrots, and dates, skipping bananas. The result forms a subsequence of your grocery list without needing to follow the exact order or select every item.

What this question basically says is that irrespective of the way your $n + 1$ distinct real numbers are chosen you always have a subsequence.

This emphasizes the core claim that regardless of the particular distinct numbers you start with, there will always exist a subsequence of specific length with the property of being either entirely increasing or completely decreasing. It sets the scene for the proof which will explain how this can be shown.

Picture a classroom with students of various sizes. Even if you randomly select to stand different students, you will be able to sort them to find a group where some are consistently shorter or taller without needing to stand them in a line.

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

The proof begins by formally denoting the sequence of distinct numbers and aims to prove the statement using the pigeonhole principle. This principle suggests that if you have more 'pigeons' (in this case, possible lengths of subsequences) than 'holes' (the maximum values), at least one 'hole' must contain more than one 'pigeon', leading to the conclusion of repeated lengths either being increasing or decreasing.

Suppose you have five cars parked in four parking spaces. If we assume one car can't be in more than one space, at least one space must contain more than one car, illustrating how overlaps (or in this case, dependencies) occur naturally in constrained systems.

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

Assuming the opposite of the claim is key for contradiction proofs. If we assume every increasing and decreasing length is capped at $n$, it leads to a logical inconsistency where we will have more sequences than available options, which is a violation of the pigeonhole principle, indicating that our initial assumption must be incorrect.

Imagine if a classroom only has three chairs but six students. If I claim that every student with a book can only sit individually and each has to take a chair, I reach a point where it becomes impossible to seat all six without exceeding three, demonstrating the impossibility of my statement.

On the other hand if I take the case when $a_j > a_k$ then I have to just give a symmetric argument. What I claim is if you take that subsequence and put an $a_j$ at the beginning, then that now gives me a new decreasing subsequence.

In trying to derive a contradiction, we explore both outcomes (if one value is greater than another and vice versa). This showcases how the longer subsequences can always keep being formed despite assumptions of maximum lengths, illustrating the inherently recursive nature of the sequences and thus affirming the claim.

Consider again the height example. If we keep adding taller students to a lineup, we will end up contradicting the initial boundaries set since we can always find new arrangements of increasing or decreasing heights within our group.

That means there is at least one $a_i$ where either $L_i$ is greater than $n$ or $D_i$ is greater than $n$. I do not know what exactly is that $a_i$. So I gave you a non-constructive proof here.

The conclusion reinforces that at least one of the subsequences must exceed the initial assumption, proving that our claim about subsequences of distinct real numbers is correct. The non-constructive proof emphasizes existence rather than the method of identifying that specific number, demonstrating a deeper understanding of mathematical proofs.

Imagine a treasure hunt where you know that somewhere in a large forest, there is at least one hidden treasure but you don't know its exact location. The assurance of its existence is enough to validate the search even if the exact coordinates remain ambiguous.

--