14 - Scenic Viewpoints Theorem

Scenic Viewpoints Theorem

Let $(a_{n})$ be a real sequence then
$(a_{n}) has a monotone subsequence$

Proof

Let $V = {k \in N : if m > k then a_{m} < a_{k}}$
I.e. the elements of $V$ are peaks
So if $k \in V$ then $a_{k}$ is higher than all terms after it

$V$ is infinite
Suppose the elements of $V$ are $k_{1} < k_{2} < \dots$
Then $(a_{k_{r}})_{r}$ is a subsequence of $(a_{n})$

Hence it is monotone decreasing as
$if r < s then k_{r} < k_{s} so a_{k_{r}} > a_{k_{s}}$

$V$ is finite
Then there is $N$ such that if $k \in V$ then $k < N$
Let $m_{1} = N$ . Then $m_{1} \neq = V$ so there is $m_{2} > m_{1}$ with $a_{m_{2}} \geq a_{m_{1}}$
As $m_{2} \neq \in V$ then there is $m_{3} > m_{2}$ with $a_{m_{3}} \geq a_{m_{2}}$
Repeating inductively, we can construct $m_{1} < m_{2} < m_{3} < \dots$ with

$a_{m_{1}} \leq a_{m_{2}} \leq a_{m_{3}} \leq \dots$
Then
$(a_{m_{r}})_{r} is an increasing subsequence of (a_{n})$

Oxford Maths Notes

Explorer

14 - Scenic Viewpoints Theorem

Graph View

Backlinks