# every sequence has a monotone subsequence

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.

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

• 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 – Jose Vega Mar 20 '16 at 20:45
• What does it mean for a sequence to have no peaks? – Friedrich Philipp Mar 20 '16 at 20:48
• I understand that: The sequence is a increasing sequence – Jose Vega Mar 20 '16 at 20:50
• No, you don't because it's wrong. ;-) – 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.

• 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. – Najib Idrissi Mar 20 '16 at 20:59
• Yes, thank you :) – Michael Harrison Mar 20 '16 at 21:00
• @NajibIdrissi But if we set N = -1, wouldn't this mean that the last peak is -1? How does this make sense? – user825007 Sep 16 '20 at 2:07
• 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. – 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.