# Monotonic increasing subsequence

The theorem states that every sequence has a monotonic subsequence.

In the case of the finite peak points, those points must be in the "beginning" of the sequence or at the "end" as "We note that an increasing sequence will have no peaks as each successive term is larger than the previous"

Does this mean that the monotonic (strictly) increasing subsequence is finite? as after a peak index lets say $$n$$ for all $$n we have $$a_n>a_N$$?

An $$a_n$$ is a "peak" iff $$\forall m >n: a_n \ge a_m$$.

Suppose we're in the case of finitely many peaks, so we can enumerate them:

$$a_{n_1}, a_{n_2},\ldots, a_{n_p}$$ (s0 $$p$$ many peaks) with $$n_1 < n_2 < \ldots n_p$$. Then for any index $$n > n_p$$ we are sure that $$a_n$$ is not a peak, which means, by the negation of the definitional condition of a peak: $$\exists m >n: a_m > a_n$$, and this gives us a way to go on and find an increasing subsequence: after every term we're always guaranteed to find a new value at least as large, as soon as we're "beyond the peaks". Because we always find new strictly larger indices this way we are guarantueed an infinite increasing subsequence.

A subsequence cannot be finite, by definition. Indeed the second part of the proof does construct an actual subsequence. Let $$a_{n_1},\,\ldots,\,a_{n_k}$$ be the peaks of the sequence $$(a_n)_{n\geq 0}$$, with $$n_1<\cdots . It is true that $$a_n\leq a_{n_k}$$ for all $$n\geq n_k$$, this is the definition of peak, but this does not prevent extracting a strictly increasing subsequence from $$n_k$$ on. For instance, suppose that for $$n>n_k$$ the sequence is strictly increasing and converges to a limit that is less than $$a_{n_k}$$.

An example. Define $$(a_n)_{n\geq 0}$$ such that $$a_{2k}=2$$ and $$a_{2k+1}=0$$ for $$k=0,1$$ and $$a_n=1-\frac{1}{n}$$ for $$n\geq 4$$. The peak indices are $$0$$ and $$2$$, and the sequence is strictly increasing for $$n\geq 3$$.

• I should not use "finite" maybe the limit of the subsequence cannot be greater than the peaks – gbox Feb 12 at 10:06
• Sorry, I don't understand the comment. The limit of the strictly increasing subsequence you extract exists and is finite since the subsequence is bounded by $a_{n_k}$ (the "lowest" of the peaks). Please, tell me if I misunderstood the comment. – AlessioDV Feb 12 at 10:29