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$

  • $\begingroup$ that is by assumption ($n_1$ not a peak) and definition. Just evaluate the statement $n_1$ is not a peak (negation of $n_1$ is a peak). $\endgroup$ – Thomas Sep 12 '14 at 6:15
  • 1
    $\begingroup$ The integer closest to π/2 is not a peak for {sin n}, sin 2 < sin 8. I am not conviced that this sequence has any peaks - ie. I think sin n, with integer n, can approximate 1 arbitrary well. $\endgroup$ – Taemyr Sep 12 '14 at 11:04

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_n\leq x_{n_1}$$ which is exactly what you have.


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.


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.