Peak Point Lemma

Theorem

Let $\left \langle {x_n} \right \rangle$ be a sequence in $\R$.

Then $\left \langle {x_n} \right \rangle$ has a subsequence which is monotone.

Proof

• First, suppose that every set $\left\{{x_n: n > N}\right\}$ has a maximum.

If this is the case, we can find a sequence $n_r \in \N$ such that:

• $\displaystyle x_{n_1} = \max_{n > 1} \left({x_n}\right)$
• $\displaystyle x_{n_2} = \max_{n > n_1} \left({x_n}\right)$
• $\displaystyle x_{n_3} = \max_{n > n_2} \left({x_n}\right)$

and so on.

Obviously, $n_1 < n_2 < n_3 < \cdots$, so at each stage we are taking the maximum of a smaller set than at the previous one. And at each stage, the previous maximum has already been taken as the previous element in the sequence.

Thus, $\left \langle {x_{n_r}} \right \rangle$ is a decreasing subsequence of $\left \langle {x_n} \right \rangle$.

• Second, suppose it is not true that every set $\left\{{x_n: n > N}\right\}$ has a maximum.

Then there will exist some $N_1$ such that $\left\{{x_n: n > N_1}\right\}$ has no maximum.

So it follows that, given some $x_m$ with $m > N_1$, we can find an $x_n$ following that $x_m$ such that $x_n > x_m$.

(Otherwise, the biggest of $x_{N_1+1}, \ldots, x_m$ would be a maximum for $\left\{{x_n: n > N_1}\right\}$.)

So, we define $x_{n_1} = x_{N_1+1}$.

Then $x_{n_2}$ can be the first term after $x_{n_1}$ such that $x_{n_2} > x_{n_1}$.

Then $x_{n_3}$ can be the first term after $x_{n_2}$ such that $x_{n_3} > x_{n_2}$.

And so on.

Thus we get an increasing subsequence of $\left \langle {x_n} \right \rangle$.

• There are only these two possibilities, and from both we get a subsequence that is monotone: one is decreasing and one is increasing.

We can of course choose to investigate whether every set $\left\{{x_n: n > N}\right\}$ has a minimum. The same conclusion will be reached.

$\blacksquare$

Sources

• K.G. Binmore: Mathematical Analysis: A Straightforward Approach (1977)... (previous)... (next): $\S 5.9$