 Solution

ID: past-exam-of-the-mathematics-course-of-the-university-of-oxford/2015/prelims/mathematics-ii/1/a/i/solution

Call

k

a_{k} \geq a_{m}

for every

m > k

. If there are infinitely many peaks of a sequence, list their indices in increasing order,

k_{1} < k_{2} < \dots

. Since

k_{r + 1} > k_{r}

a_{k_{1}} \geq a_{k_{2}} \geq \dots .

This is a decreasing subsequence; throughout this argument, a decreasing monotone sequence may have equal successive terms.

If there are only finitely many peaks of a sequence, choose

N

beyond all their indices; take

N = 1

if there are none. Every

n \geq N

fails to be a peak of a sequence, so some

m > n

satisfies

a_{m} > a_{n}

. Starting with

n_{1} = N

, choose such an

n_{r + 1} > n_{r}

recursively. This gives

a_{n_{1}} < a_{n_{2}} < \dots .

The two cases prove the monotone subsequence theorem without any boundedness hypothesis.

 New to topics? Read the docs here!