Loading the lesson
Loading the lesson
Search AllRounder.ai
Search the courses, subjects, tracks, games and features, or jump straight to a page.
Search the courses, subjects, tracks, games and features, or jump straight to a page.
Learn it your way
A short class with Sarah and her students. The other ways are under More.
Sign up free to listen. Transcripts are free to read.
Today, we are going to explore what it means for a sequence to be strictly increasing or strictly decreasing. Who can tell me what they think a strictly increasing sequence is?
Isn't it when every number is larger than the one before?
Exactly! A strictly increasing sequence is of the form (a_1, a_2, …) where a_1 < a_2 < a_3 and so on. Now, can anyone define a strictly decreasing sequence?
It’s when each number is smaller than its predecessor, right?
Exactly correct! A strictly decreasing sequence looks like (a_1, a_2, …) where a_1 > a_2 > a_3. This brings us to an important idea: subsequences. Can anyone tell me what a subsequence is?
Is it a part of the sequence that can skip some numbers but keeps the order?
Yes! Good job! A subsequence maintains the original order of terms but may not include all the elements. Let’s look at our definitions again. What if I told you that no matter how we choose n + 1 distinct real numbers, we can always find a subsequence that is either strictly increasing or strictly decreasing?
How is that possible? Can you explain?
Great question! That’s what we’ll prove next!
Let’s delve into why subsequences are significant in sequences of distinct real numbers. We can take these numbers and create subsequences. Can anyone give me an example of a subsequence?
In a sequence like 1, 3, 0, -5, 2, 8, I could pick 1, -5, and 2.
Great example! What you’ve chosen is a valid subsequence, although it’s not strictly increasing or decreasing. Now let's dive into how we prove that some subsequence will always be either increasing or decreasing.
How do we do that?
We use the pigeonhole principle, which states if you have more pigeons than holes, at least one hole must contain more than one pigeon. We can relate this to our increasing and decreasing lengths.
So we pair values of increasing and decreasing subsequences?
Exactly! Now, if we assume that the longest increasing or decreasing subsequence is less than or equal to n for all subsequences, we’ll find a contradiction.
Now, we’ll apply the pigeonhole principle to prove this statement. Suppose we have n + 1 distinct numbers, and we define a_i as the length of the longest increasing sequence starting from that number.
What if it turns out that all subsequences are less than or equal to n?
If that’s assumed, we could pair the longest subsequences, which leads to decreasing subsequences as well.
And that’s how we get a contradiction, right?
Exactly! In both cases of comparing the lengths, we arrive at a contradiction confirming that at least one subsequence must be of length n + 1. So no matter how we arrange n + 1 distinct numbers, we will find at least one subsequence that is either strictly increasing or strictly decreasing.
A sequence where each term is greater than the previous term.
A sequence where each term is less than the previous term.
A sequence derived from another by deleting some elements without changing the order of the remaining elements.
Increasing, sliding up the hill, each number grows, can you feel?
Once there were numbers in a race, climbing higher, they won first place, while others in reverse fell fast, strictly decreasing, they couldn’t last.
I create a subsequence for fun, just skip some numbers, and then I'm done!
SIS - Strictly Increasing Sequence, SSS - Strictly Decreasing Sequence.
Term
Defining strictly increasing sequence
Click to flip
Term
Defining strictly decreasing sequence
Click to flip
Term
Defining subsequence
Click to flip
A sequence where each term is greater than the previous term.
A sequence where each term is less than the previous term.
A sequence derived from another by deleting some elements without changing the order of the remaining elements.
A principle stating that if more items are put into fewer containers than there are items, then at least one container must contain at least two items.
This section introduces the concepts of strictly increasing and decreasing sequences, focusing on the existence of subsequences within a given set of distinct real numbers.
The segment elaborates on the definitions of strictly increasing and decreasing sequences while demonstrating that any sequence of distinct real numbers contains a subsequence with length n + 1, either strictly increasing or decreasing. It also introduces important concepts like subsequences and explains the proof using the pigeonhole principle and contradiction.
In this section, we explore the definitions of strictly increasing and decreasing sequences using distinct real numbers. A strictly increasing sequence is one in which each subsequent element is greater than the preceding one, represented as (a_1, a_2, ...), where a_1 < a_2 < ... < a_n. Conversely, a strictly decreasing sequence has the form (a_1, a_2, ...), where a_1 > a_2 > ... > a_n. The focus of the section is to demonstrate that for any sequence of n + 1 distinct real numbers, a subsequence exists with a length of at least n + 1 that is either strictly increasing or strictly decreasing. This is proven using the pigeonhole principle, which identifies a contradiction based on the assumption that all subsequences of increasing and decreasing length are less than or equal to n. As a result, this establishes the existence of a long enough subsequence that fulfills the required condition.