Increasing or Decreasing Subsequences of Finite Sequences

Recall from The Generalized Pigeonhole Principle page that if $p_1, p_2, ..., p_n$ are positive integers and if $A$ is a finite set that has $p_1 + p_2 + ... + p_n - n + 1$ elements and if $A_1, A_2, ..., A_n$ are subsets of $A$ that form a partition of $A$ then for some $i \in \{1, 2, ..., n \}$ we have that $\lvert A_i \rvert \geq p_i$.

We will now look at a particularly nice application of the generalized pigeonhole principle. We will first need to look at a couple of definitions though, both of which you may be familiar with already.

Definition: A Finite Sequence of $n$ real numbers $a_i \in \mathbb{R}$ is an ordered list of $n$ terms $(a_i)_{i=1}^{n} = (a_1, a_2, ..., a_n)$.

Infinite sequences can be defined analogously.

Definition: A sequence $(a_i)_{i=1}^{n}$ is said to be Increasing if $a_j \leq a_{j+1}$ for each $j = 1, 2, ..., n-1$. A sequence $(a_i)_{i=1}^{n}$ is said to be Decreasing if $a_j \geq a_{j+1}$ for each $j = 1, 2, ..., n- 1$.

For example, the finite sequence of positive integers from $1$ to $10$ is:

(1)

\begin{align} \quad (a_i)_{i=1}^{n} = (1, 2, 3, 4, 5, 6, 7, 8, 9, 10) \end{align}

Clearly each term of the sequence is greater or equal than the previous term in the sequence and so this sequence is increasing.

Definition: A Subsequence $(a_{i_k})_{k=1}^{m}$ of a finite sequence $(a_i)_{i=1}^{n}$ is an ordered sequence of $m$ terms $(a_{i_k})_{k=1}^{m} = (a_{i_1}, a_{i_2}, ..., a_{i_m})$ where $i_1 < i_2 < ... < i_m < n$.

By definition every subsequence is itself a sequence.

For example, consider the finite sequence $(a_i)_{i=1}^{n}$ described above. Then the finite sequence of event integers from $1$ to $10$ is a subsequence of $(a_i)_{i=1}^{n}$ and is given by:

(2)

\begin{align} \quad (a_{i_k})_{k=1}^{5}) = (2, 4, 6, 8, 10) \end{align}

Note that $i_1 = 2$, $i_2 = 4$, $i_3 = 6$, $i_4 = 8$, and $i_5 = 10$.

Now that we have defined a subsequence of a finite sequence, we will now look at an example to motivate the theorem coming up. Consider the following sequence of $10$ terms:

(3)

\begin{align} \quad (4, 2, 9, 5, 1, 3, 5, 4, 6, 10) \end{align}

Now suppose that we want to determine what is the largest number $m$ such that $1 \leq m \leq n$ that guarantees the existence of a subsequence of $m$ elements that is either increasing or decreasing? The following theorem answers this question if the number of elements in the parent sequence is of the form $n^2 + 1$ for $n \in \{ 0, 1, 2, ... \}$.

Theorem 1: For $n \in \{0, 1, 2, ... \}$ there exists a subsequence of $n + 1$ terms of the finite sequence of $n^2 + 1$ terms $(a_1, a_2, ..., a_{n^2 +1})$ that is either increasing or decreasing.

• Proof: Let $(a_i)_{i=1}^{n^2+1} = (a_1, a_2, ..., a_{n^2+1})$ be a finite sequence of $n^2 + 1$ numbers. For each $k \in \{ 1, 2, ..., n^2 + 1 \}$ let $s_k$ equal the maximum length of an increasing subsequence of $(a_i)_{i=1}^{n^2+1}$ starting at $a_k$.

• We will carry the proof by contradiction. Assume that $(a_i)_{i=1}^{n^2+1}$ has no increasing subsequences of length greater or equal to $n+1$ and no decreasing subsequences of length greater or equal to $n+1$. Since $s_k$ is equal to the maximum length of an increasing subsequence of $(a_i)_{i=1}^{n^2+1}$ starting at $a_k$ we therefore have that for all $k \in \{1, 2, ..., n^2 + 1 \}$ that $1 \leq s_k \leq n$.

• Consider the sequence of real numbers $\{ s_1, s_2, ..., s_{n^2+1} \}$. There are $n^2 + 1$ numbers in this sequence and for each $k \in \{1, 2, ..., n^2 + 1\}$ we have that $s_k$ is either $1$, $2$, …, or $n$. We will now apply The Generalized Pigeonhole Principle.

• We have $n^2 + 1$ numbers $s_k$ for which each of these numbers is one of $n$ numbers (from $1$ to $n$). Recall that if $n(r - 1) + 1$ objects are put into $n$ boxes than at least one box contains $r$ objects. Here we have that $n = r - 1$ which implies that $r = n + 1$ so for $n^2 + 1$ numbers $s_k$ put into $n$ groups we have that one group contains $n + 1$ or more of the $s_k$'s.

• For $1 \leq k_1 < k_2 < ... < k_n < k_{n+1} \leq n^2 + 1$ we let:

(4)

\begin{align} \quad s_{k_1} = s_{k_2} = ... = s_{k_n} = s_{k_{n+1}} \end{align}

• Suppose that there exists an $i \in \{1, 2, .., n \}$ such that $a_{k_i} < a_{k_{i+1}}$. Consider a longest increasing sequence starting at $a_{k_{i+1}}$. This sequence has length $s_{k_{i+1}}$. If $a_{k_i} < a_{k_{i+1}}$ then place the element $a_{k_i}$ in front of a longest increasing sequence starting at $a_{k_{i+1}}$. Then there exists an increasing sequence starting at $a_{k_i}$ that is $s_{k_{i+1}} + 1$ in length. However, $s_{k_{i+1}} = s_{k_i}$ so instead we have a sequence starting at $a_{k_i}$ that is $s_{k_i} + 1$ in length. However, $s_{k_i}$ is the length of the longest increasing sequence starting at $a_{k_i}$. Thus our assumption that there exists an $i \in \{1, 2, ..., n \}$ such that $a_{k_i} < a_{k_{i+1}}$ so instead for each $i \in \{1, 2, ..., n \}$ we have:

(5)

\begin{align} \quad a_{k_i} \geq a_{k_{i+1}} \end{align}

• Therefore:

(6)

\begin{align} \quad a_{k_1} \geq a_{k_2} \geq ... \geq a_{k_n} \geq a_{k_{n+1}} \end{align}

• This is a decreasing subsequence of $(a_i)_{i=1}^{n^2+1}$ length $n + 1$ though. Thus by assuming no increasing subsequences exist we have proven that a decreasing subsequence exists. The same follows if we assume no decreasing subsequences exist which will show an increasing subsequence exists. $\blacksquare$