Enrol to start learning
Reading is open to everyone. Enrolling is free, and it is what unlocks the audio lessons, practice tests and progress tracking.
18.1.1. Definition of Increasing and Decreasing Sequences
Learn content
Interactive Audio Lesson
Unlock the classroom podcast
The transcript is free to read. A free account plays the conversation back.
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!
Unlock the classroom podcast
The transcript is free to read. A free account plays the conversation back.
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.
Unlock the classroom podcast
The transcript is free to read. A free account plays the conversation back.
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.
Overview
Short Summary
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.
Medium Summary
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.
Detailed Summary
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.
Reference YouTube Videos
Audio Book
Unlock the audio lesson
The script is above and free to read. A free account plays it back, in the voice you pick.
Create a free accountTake any sequence of k + 1 distinct real numbers. They are arbitrary real numbers, may be positive or negative. The only condition is that they have to be distinct.
Detailed Explanation
This chunk introduces the concept of sequences made up of distinct real numbers. It is important because the distinctness of numbers is a prerequisite for the claims that follow in understanding subsequences.
Examples & Analogies
Think of a group of friends each with unique ages. If you randomly pick some friends, as long as no two have the same age, you're working with 'distinct' ages.
Unlock the audio lesson
The script is above and free to read. A free account plays it back, in the voice you pick.
Create a free accountA sequence of the form (a_1, a_2,...) where a_1 < a_2 < a_3 < ... < a_k.
Detailed Explanation
A strictly increasing sequence means that each number in the sequence is less than the number that follows it. This concept is crucial for identifying subsequences that exhibit increasing behavior.
Examples & Analogies
Imagine you're ranking students in a race by their times. If each student's time is less than the next, their rankings are in strictly increasing order.
Unlock the audio lesson
The script is above and free to read. A free account plays it back, in the voice you pick.
Create a free accountA sequence of the form (a_1, a_2, a_3,...) where a_1 > a_2 > a_3 > ... > a_k.
Detailed Explanation
A strictly decreasing sequence indicates that each number is greater than the one that follows it, similar to an arrangement where performance decreases with each entry.
Examples & Analogies
Picture the countdown to a rocket launch, where the time decreases with each passing second – each second is less than the one before it, reflecting a strictly decreasing sequence.
Unlock the audio lesson
The script is above and free to read. A free account plays it back, in the voice you pick.
Create a free accountA subsequence means that the values may not be consecutive. You can skip some numbers.
Detailed Explanation
A subsequence retains the original order of elements but does not require them to be adjacent. This flexibility allows us to find sequences that are either increasing or decreasing even if elements are skipped.
Examples & Analogies
Think of a playlist where you select some songs from a larger list. You can listen to songs in the order they appear in the list, but you can skip songs in between.
Unlock the audio lesson
The script is above and free to read. A free account plays it back, in the voice you pick.
Create a free accountThe question basically states that irrespective of how the k + 1 distinct real numbers are chosen, you always have a subsequence of length k + 1 that is either strictly increasing or strictly decreasing.
Detailed Explanation
This claim underlines the importance of the subsequence's existence. The goal is to demonstrate that among any k + 1 distinct real numbers, there will inevitably be a subsequence that is either strictly increasing or strictly decreasing, which we will prove.
Examples & Analogies
Consider a class of students where each student has a distinct score. No matter how you pick 5 students, you will find at least some scores that follow a strictly increasing or decreasing trend. This is a foundational concept in understanding sequences.
Unlock the audio lesson
The script is above and free to read. A free account plays it back, in the voice you pick.
Create a free accountLet the arbitrary sequence of k + 1 distinct real numbers be denoted by a_1 to a_k+1. This is a universally quantified statement, and to prove it, I can use the pigeonhole principle along with proof by contradiction.
Detailed Explanation
The pigeonhole principle states that if you have more items than containers, at least one container must hold more than one item. Here, it suggests that with k + 1 values, there are bound to be overlaps in subsequences.
Examples & Analogies
Imagine you have 10 pairs of socks but only 9 drawers. It’s inevitable that at least one drawer will contain more than one pair. Similarly, in the context of sequences, this principle leads to the conclusion that some subsequences must repeat in terms of their lengths.
--
Key concepts
Core takeaways and short definitions to help you quickly recall the key ideas from this section.
- Strictly Increasing Sequence:
A sequence where each term is greater than the previous term.
- Strictly Decreasing Sequence:
A sequence where each term is less than the previous term.
- Subsequence:
A sequence derived from another by deleting some elements without changing the order of the remaining elements.
Examples
Memory aids
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.
Flash Cards
Glossary
Strictly Increasing Sequence
A sequence where each term is greater than the previous term.
Strictly Decreasing Sequence
A sequence where each term is less than the previous term.
Subsequence
A sequence derived from another by deleting some elements without changing the order of the remaining elements.
Pigeonhole Principle
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.