# A question on a proof that every sequence has a monotone subsequence

Consider the following proof that every sequence $${x_n}_n$$ in $$mathbb R$$ has a monotone subsequence.

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.

In the second case, if $$n_1$$ is not a peak, how does this imply the existence of an $$n_2 > n_1$$ with $$x_{n_2} geq x_{n_1}$$? Can’t it be possible that there does not exist any $$n_2 > n_1$$ such that $$x_{n_2} geq x_{n_1}$$?

A possible example can be the sequence $${sin n}_n$$, taking $$N$$ to be the closest integer to $$pi/2$$

Mathematics Asked by MathMan on January 3, 2021

If you have a statement "for all $$x$$, $$P(x)$$ is true", then the negation of this statement is "there exists an $$x$$ such that $$P(x)$$ is not true". (the negation of $$forall x: P(x)$$ is $$exists x: neg P(x)$$).

$$n_1$$ is not a peak. The definition of $$n_1$$ being a peak is:

$$forall ,n> n_1: x_{n_1}>x_n$$ meaning that by definition, $$n_1$$ is not a peak iff $$exists , n > n_1: x_nleq x_{n_1}$$ which is exactly what you have.

Correct answer by 5xum on January 3, 2021

Here is a tedious proof that avoids dealing with peaks:

Let $bar{x} = limsup_n x_n$.

If $bar{x} = infty$, then let $n_1 = 1$, and $n_{k+1} = min {n | n ge n_k+1, x_n ge x_{n_k} +1 }$, then $x_{n_k}$ is a monotone sequence.

Otherwise, suppose $bar{x} < infty$.

Suppose ${x_n} cap (bar{x},infty)$ contains an infinite subset. Let $x_{n_k}$ be the subsequence of $x_n$ that lies in $(bar{x},infty)$. Then $x_{n_k} > bar{x}$, and $lim_k x_{n_k} = bar{x}$. Let $m_1 = n_{1}$, and $m_{k+1} = min {n_j | n_j ge m_k+1, x_{n_j} < x_{m_k} }$, then $x_{m_k}$ is a monotone sequence.

Now suppose ${x_n} cap (bar{x},infty)$ is finite.

Suppose ${x_n} cap {bar{x}}$ contains an infinite subset, then clearly this subsequence is a monotone (in fact, constant) subsequence.

Now suppose ${x_n} cap [bar{x},infty)$ is finite. Then $x_n < bar{x}$ (after a finite number of terms), and there exists a subsequence $x_{n_k}$ such that $lim_k x_{n_k} = bar{x}$. Similar to above, let $m_1 = n_1$, and $m_{k+1} = min {n_j | n_j ge m_k+1, x_{n_j} > x_{m_k} }$, then $x_{m_k}$ is a monotone sequence.

Answered by copper.hat on January 3, 2021

## Related Questions

### Evaluate $int_0^{pi/2} frac{arctan{left(frac{2sin{x}}{2cos{x}-1}right)}sin{left(frac{x}{2}right)}}{sqrt{cos{x}}} , mathrm{d}x$

1  Asked on September 23, 2020 by user801111

### Problem with split exact sequences and free finitely generated modules

2  Asked on September 22, 2020 by aa_bb

### Well posedness of Burgers’ equation

0  Asked on September 21, 2020 by rage

### degree of minimal polynomial and degree of field extension

1  Asked on September 20, 2020 by ton910

### The set of all finite subsets of $mathbb{R}_+$ is countable.

1  Asked on September 19, 2020 by simey

### What is the probability that balls left are white?

1  Asked on September 18, 2020 by abhishek

### Dual image map restricts to open sets?

1  Asked on September 18, 2020 by blargoner

### How to compute $sum_{n=1}^infty{frac{n}{(2n+1)!}}$?

3  Asked on September 18, 2020 by samuel-a-morales

### Prove there is no rational number r such that $2^r = 3$

3  Asked on September 16, 2020 by yastown

### Rational Roots (with Lots of Square Roots!)

1  Asked on September 16, 2020 by fleccerd

### How to say a variable is invertible in Macaulay2?

1  Asked on September 14, 2020 by hlee

### Given $x, y in mathbb{R}^+$ and $x^3 + y^3 = x-y$. Prove $x^2 + 4y^2 < 1$

1  Asked on September 14, 2020 by user9026

### Is a relation that is purely reflexive also symmetric?

1  Asked on September 13, 2020 by paul-j

### $3^{123} mod 100$

4  Asked on September 13, 2020 by global05

### Totally order turing machines by halting

1  Asked on September 10, 2020 by donald-hobson

### Implications of an expected value on almost sure convergence

1  Asked on September 8, 2020 by qp212223

### Density of Tensor Products

0  Asked on September 8, 2020 by jacob-denson

### 2010 USAMO #5:Prove that if $frac{1}{p}-2S_q = frac{m}{n}$ for integers $m$ and $n$, then $m – n$ is divisible by $p$.

2  Asked on September 7, 2020 by shubhangi