[MIT OCW Mathematics for Computer Science] Assume that a1<a2. Show that if there is no 3-chain in our sequence, then a3 must be less than a1.

Define a 3-chain to be a (not necessarily contiguous) subsequence of three integers, which is either monotonically increasing or monotonically decreasing. We will show here that any sequence of five distinct integers will contain a 3-chain. Write the sequence as [;{a}_{1},{a}_{2},{a}_{3},{a}_{4},{a}_{5};]. Note that a monotonically increasing sequences is one in which each term is greater than or equal to the previous term. Similarly, a monotonically decreasing sequence is one in which each term is less than or equal to the previous term. Lastly, a subsequence is a sequence derived from the original sequence by deleting some elements without changing the location of the remaining elements. Source

(a) [4 pts] Assume that [;{ a }_{ 1 }<{ a }_{ 2 };]. Show that if there is no 3-chain in our sequence, then [;{a}_{3};] must be less than [;{a}_{1};]. (Hint: consider [;{a}_{4};]!)

What I have so far:

Theorem: if there is no 3-chain in our sequence, then [;{a}_{3};] must be less than [;{a}_{1};]

Proof: We use proof by contradition

1. Let's assume that if there is no 3-chain sequence, then [;{ a }_{ 3 }>{ a }_{ 1 };]

2. This gives rise to two possibilities:

[;{ a }_{ 1 }<{ a }_{ 2 }<{ a }_{ 3 };] or [;{ a }_{ 1 }<{ a }_{ 3 }<{ a }_{ 2 };]

3. ...

I am stuck at step three of my proof because I do not know how to proceed. From what I understand, either one of the two possibilities I came up with could be true. It's undefined since we do not know the relationship between [;{ a }_{ 2 };] and [;{ a }_{ 3 };]

I would appreciate a hint that would allow me to complete my proof.