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.2. Definition of Subsequences
Learn content
Interactive Audio Lesson
Unlock the classroom podcast
The transcript is free to read. A free account plays the conversation back.
Today, we will dive into the concept of subsequences. Can anyone tell me what a subsequence is?
Is a subsequence just a part of a sequence?
Exactly, a subsequence consists of elements from a sequence, maintaining their original order but not necessarily being consecutive. For example, in the sequence (3, 1, 4, 2), (3, 4) is a subsequence.
And what about increasing and decreasing subsequences?
Good question! A subsequence is strictly increasing if each element is greater than the previous one, such as (1, 2, 3). Conversely, it's strictly decreasing if each element is less than the previous one, like (3, 2, 1).
Unlock the classroom podcast
The transcript is free to read. A free account plays the conversation back.
Now, let's discuss a fundamental theorem: in any sequence of n + 1 distinct real numbers, there exists a subsequence of length n + 1 that is either strictly increasing or strictly decreasing. Why do you think that is?
Maybe it's because there are more numbers than positions for them to fit?
That's right! To demonstrate this, we can consider terms representing the lengths of the longest increasing and decreasing subsequences for each number in our sequence.
How can we use that information to prove the theorem?
We apply the principle of contradiction. If we assume that the lengths are capped at n, we could apply the pigeonhole principle to find at least one number violating that assumption.
So this would show that there must be a subsequence of at least one of those kinds?
Exactly! You grasped that very well.
Unlock the classroom podcast
The transcript is free to read. A free account plays the conversation back.
Let’s analyze the proof mechanism using the pigeonhole principle further. Who remembers what this principle states?
If you have more items than containers, at least one container must hold more than one item!
Correct! In this scenario, our 'pigeons' are the lengths of subsequences and the 'holes' are the maximum lengths that we assumed were possible—up to n.
And if we assume both max lengths are n, we end up needing more pairs than available?
Exactly! This setup leads us to conclude that at least one must exceed n, implying the existence of an increasing or decreasing subsequence of that length. Well done!
Overview
Short Summary
The section discusses the concept of subsequences, particularly focusing on the existence of strictly increasing or decreasing subsequences within a given sequence of distinct real numbers.
Medium Summary
This section introduces subsequences from a sequence of distinct real numbers and establishes the theorem that any sequence of n + 1 distinct real numbers will always contain a subsequence of length n + 1 that is either strictly increasing or strictly decreasing. The proof utilizes the pigeonhole principle along with a contradiction approach.
Detailed Summary
Definition of Subsequences
In this section, we explore the concept of subsequences within sequences of distinct real numbers. A subsequence is defined as a sequence derived from another sequence where some elements may be omitted, but the order is preserved. For example, in the sequence 1, 3, 0, -5, 2, 8, (1, 2, 8) is a valid subsequence. The main proposition discussed is that for any sequence of n + 1 distinct real numbers, there exists at least one subsequence of length n + 1 that is either strictly increasing or strictly decreasing.
To prove this, we assign the longest increasing subsequence starting at each element with a value denoted as L and the longest decreasing one as D. The contradiction proof arises by assuming that the longest increasing and decreasing subsequences for every number in the sequence are bounded by n. By applying the pigeonhole principle, we demonstrate that it's impossible due to having more numbers than possible pairs of (L, D), leading us to conclude that at least one of L or D must exceed n. This establishes the theorem's validity.
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 accountA subsequence means that the values may not be consecutive. That means I am allowed to miss a few numbers. For instance, if I take a sequence like (1, 3, 0, -5, 2, 8), I can choose 1 and exclude 3, 0, and -5. This forms a subsequence. Similarly, I can pick a subsequence like (3, 2, 8), meaning I skip 0 and -5.
Detailed Explanation
A subsequence is derived from a sequence by deleting certain elements without changing the order of the remaining elements. This is important because it demonstrates that you can form new sequences while retaining the original order. In our example of the sequence (1, 3, 0, -5, 2, 8), if we take elements 1 and 2, excluding some numbers in between does not prevent us from having a valid subsequence.
Examples & Analogies
Think of a subsequence like picking certain pieces of fruit from a tree. You may decide to collect apples, skipping some branches. The apples you gather still retain their position on the tree, but you're not required to take fruit from every branch.
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 claim is that irrespective of the way your n+1 distinct real numbers are chosen, there always exists a subsequence of length n+1 that is either strictly increasing or strictly decreasing.
Detailed Explanation
This claim suggests that within any set of distinct real numbers, you will always be able to find a subsequence which meets specific criteria—either all numbers increase or all numbers decrease. This property is intrinsic to the nature of sequences and subsequences in mathematics.
Examples & Analogies
Imagine you have a line of people, each taller than the other. No matter how you select individuals from this line, you can always find a group where everyone is either taller or shorter than the next. This reflects the essence of the claim regarding subsequences.
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 strictly increasing sequence is of the form (a_1, a_2, ...) where a_1 < a_2 < a_3 ... < a_n. In contrast, a strictly decreasing sequence is of the form (a_1, a_2, ...) where a_1 > a_2 > a_3 ... > a_n.
Detailed Explanation
The definitions of increasing and decreasing subsequences are crucial. An increasing sequence consistently rises in value while a decreasing sequence consistently falls. This clarity in definitions helps us categorize the types of sequences we can derive and analyze within the context of our claim.
Examples & Analogies
Think of going up or down a staircase. Each step on the way up represents an increasing subsequence, while steps going down represent a decreasing sequence. Each step maintains its relative order, just like numbers in these mathematical 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 accountUsing the pigeonhole principle, we believe that if we have n+1 elements, at least one of these elements must have an 'increasing' or 'decreasing' subsequence associated with it that exceeds length n.
Detailed Explanation
The pigeonhole principle states that if you have more items than containers, at least one container must hold more than one item. In the context of subsequences, with distinct value pairs of increasing or decreasing lengths being limited to n, having more elements (n+1) ensures a 'clash' or overlap that guarantees an increasing or decreasing subsequence.
Examples & Analogies
Consider a classroom with 30 students and only 29 seats. No matter how students sit, at least one seat must be shared. This analogy helps illustrate how in a larger group (the sequence), we are bound to see repeated properties (increasing or decreasing subsequences) among the members.
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 accountTo prove the existence of such subsequences, define 'L' as the length of the longest increasing subsequence starting from each number. Similarly, define 'D' for the longest decreasing subsequence. The goal is to show that either L or D must be greater than n.
Detailed Explanation
By assigning lengths to the longest increasing and decreasing subsequences starting at any number, we can assess whether one of them exceeds n. If it does, it confirms the existence of a subsequence meeting the claim's conditions. On the contrary, if this condition fails, we can derive a contradiction underlining the claim’s validity.
Examples & Analogies
Imagine measuring the heights of people in a line. If you find that at least one group is taller than the specified measure (n), you can conclude confidently that there exists a sufficient count of taller individuals — paralleling how we prove subsequences exist.
--
Key concepts
Core takeaways and short definitions to help you quickly recall the key ideas from this section.
- Subsequences:
Derived sequences from a base sequence maintaining order.
- Strictly Increasing Sequence:
A sequence where each element is greater than its predecessor.
- Strictly Decreasing Sequence:
A sequence where each element is lesser than its predecessor.
Examples
Step-by-step examples to apply the section's ideas and test your understanding.
In the sequence (5, 3, 7, 2, 1), the subsequence (5, 7) is strictly increasing, while (5, 3, 2, 1) is strictly decreasing.
From the sequence (1, 4, 2, 3), possible subsequences include (1, 2, 3) which is increasing and (4, 2) which is decreasing.
Memory aids
Imagine a crowd of birds flying together, some rise while others dive. A subsequence could be the birds that rise, forming a lovely pattern in the skies.
For subsequences, remember 'RISE' - 'Retain', 'In-order', 'Skip elements', 'Evenly spaced'.
Flash Cards
Glossary
Subsequence
A sequence derived from another sequence where some elements may be omitted, but the order is preserved.
Strictly Increasing Sequence
A sequence where each element is greater than the preceding element.
Strictly Decreasing Sequence
A sequence where each element is less than the preceding element.
Pigeonhole Principle
A principle stating that if more items are placed into fewer containers, at least one container must contain more than one item.