18.1.2. Definition of Subsequences

Try these first

1. 1.

   Define 'subsequence' in your own words.

   Hint

   Think about how you might pick numbers from a list without changing their order.

2. 2.

   Give an example of a strictly increasing sequence.

   Hint

   All the numbers must get bigger as you move along!

3. 3.

   What is a subsequence?

   Hint

   Think about how you can rearrange numbers while keeping some of them in order.

4. 4.

   True or False: Every sequence of n distinct numbers contains a strictly increasing subsequence of length n.

   • True
   • False

   Hint

   Consider what happens in sequences with positive and negative numbers.

5. 5.

   Given the sequence of numbers 10, 20, 15, 25, 30, 5, find a subsequence that is strictly increasing.

   Hint

   Look for numbers that ascend without backtracking.

6. 6.

   You have a sequence with elements randomly ordered. How would you apply the pigeonhole principle to demonstrate the existence of either an increasing or decreasing subsequence?

   Hint

   Make a table categorizing your sequences and their potential lengths.