I am trying to prove this theorem "every sequence has a monotone subsequence"

I found this proof

Proof: Let us call a positive integer $n$ a peak of the sequence if $m > n \implies x_n > x_m$  i.e., if  $x_n$ is greater than every subsequent term in the sequence.

Suppose first that the sequence has infinitely many peaks, $n_1 < n_2 < n_3 < … < n_j < …$. Then the subsequence $\{x_{n_j}\}_j$  corresponding to these peaks is monotonically decreasing, and we are done.

So suppose now that there are only finitely many peaks, let $N$ be the last peak and set $n_1 = N + 1$.

Then $n_1$ is not a peak, since $n_1 > N$, which implies the existence of an $n_2 > n_1$ with $x_{n_2} \geq x_{n_1}.$  Again, as $n_2 > N$ it is not a peak, hence there is $n_3 > n_2$ with $x_{n_3} \geq x_{n_2}.$  Repeating this process leads to an infinite non-decreasing subsequence $x_{n_1} \leq x_{n_2} \leq x_{n_3} \leq \ldots$ as desired.

My question is about this part "So suppose now that there are only finitely many peaks"

is $0$ peak valid? for example the sequence $\{\dfrac{n}{n+1}\}$ has no peaks.

  • $\begingroup$ Thank you, the first term is 1/2 , the second term is 2/3, therefore $x_n$ < $x_m$, the first term is not peak $\endgroup$ – Jose Vega Mar 20 '16 at 20:45
  • $\begingroup$ What does it mean for a sequence to have no peaks? $\endgroup$ – Friedrich Philipp Mar 20 '16 at 20:48
  • $\begingroup$ I understand that: The sequence is a increasing sequence $\endgroup$ – Jose Vega Mar 20 '16 at 20:50
  • $\begingroup$ No, you don't because it's wrong. ;-) $\endgroup$ – Friedrich Philipp Mar 20 '16 at 20:52

Zero peak is valid and should be addressed. If a sequence has no peaks, then for every $n \in \mathbb{N}$, there exists $m > n$ such that $x_n \leq x_m$. Applying this to $n=1$ gives $n_2 > 1$, such that $x_{n_2} \geq x_1$. Applying to $n=n_2$ gives $n_3 > n_2$ such that $x_{n_3} \geq x_{n_2}$. In this way we get an increasing sequence $\left\{ n_k \right\}$ (here $n_1 = 1$), such that $\left\{ x_{n_k} \right\}$ is monotone.

EDIT: It looks like this is equivalent to setting $n_1=1$ if there are no peaks, and applying the same logic as the proof you wrote.

  • 1
    $\begingroup$ It doesn't need to be dealt with separately, you can just set $N=-1$ (assuming your sequences start with $n=0$) and the proof works just fine. $\endgroup$ – Najib Idrissi Mar 20 '16 at 20:59
  • $\begingroup$ Yes, thank you :) $\endgroup$ – Michael Harrison Mar 20 '16 at 21:00
  • $\begingroup$ @NajibIdrissi But if we set N = -1, wouldn't this mean that the last peak is -1? How does this make sense? $\endgroup$ – user825007 Sep 16 '20 at 2:07
  • $\begingroup$ Instead of thinking that the value of N means "the last peak occurs here", think that it means "no peaks occur after this index". Setting the value N=-1 when there are no peaks is just a convenient way to avoid splitting the case of zero peaks into a separate thing. $\endgroup$ – Michael Harrison Sep 16 '20 at 2:48

Consider any sequence $(x_n).$

A "peak" element is an element such that all elements $x_i$ that succeed it in the sequence are no greater than it. In other words, an element $x_p$ is a "peak" element if for all $i > p_1,$ it is the case that $x_{p_1} \geq x_i.$

In the sequence $(x_n),$ either there are finitely many peaks, or there are infinitely many.

If there are finitely many, then there is a peak element $x_p$ that appears last. Then, for all $i \in \mathbb{N}$ such that $i > p,$ there exists some $M \in \mathbb{N}$ such that $M > i$ and $x_M > x_i.$ In such a case, there clearly exists a monotone increasing subsequence $(x_{n_i}).$

If there are infinitely many peaks, then there clearly exists a monotone decreasing subsequence,

$$x_{p_1}, x_{p_2}, x_{p_3}, \ldots$$

where $x_{p_1} \geq x_{p_2} \geq x_{p_3} \geq \cdots$ are all peak elements.

Hence, any sequence has some subsequence that is monotone, whether increasing or decreasing.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.