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$ apeak of the sequenceif $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

2 AnswersIf 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

1 Asked on September 23, 2020 by user801111

2 Asked on September 22, 2020 by aa_bb

abstract algebra commutative algebra finitely generated modules projective module

0 Asked on September 21, 2020 by rage

1 Asked on September 20, 2020 by ton910

abstract algebra extension field field theory minimal polynomials

1 Asked on September 19, 2020 by simey

1 Asked on September 18, 2020 by abhishek

1 Asked on September 18, 2020 by blargoner

adjoint functors category theory continuity general topology

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

3 Asked on September 16, 2020 by yastown

1 Asked on September 16, 2020 by fleccerd

1 Asked on September 15, 2020 by maddy

1 Asked on September 14, 2020 by hlee

1 Asked on September 14, 2020 by user9026

1 Asked on September 13, 2020 by paul-j

4 Asked on September 13, 2020 by global05

contest math modular arithmetic problem solving solution verification

1 Asked on September 10, 2020 by donald-hobson

1 Asked on September 9, 2020 by lad

abstract algebra polynomials ring theory solution verification

1 Asked on September 8, 2020 by qp212223

0 Asked on September 8, 2020 by jacob-denson

Get help from others!

Recent Answers

- Philipp on How do i draw a ray in unity
- kjetil b halvorsen on How to test consistency of responses?
- DMGregory on MouseLook Script “Pops” back to the last value when the script is enabled after being disabled or destroyed
- Justin Markwell on Unity app crashes when using unmodified custom Android manifest (didn’t find class “UnityPlayerActivity”)
- eric_kernfeld on How to test consistency of responses?

Recent Questions

- MouseLook Script “Pops” back to the last value when the script is enabled after being disabled or destroyed
- Unity app crashes when using unmodified custom Android manifest (didn’t find class “UnityPlayerActivity”)
- How do i draw a ray in unity
- How to test consistency of responses?
- How can I understand these variograms?

© 2022 AnswerBun.com. All rights reserved.