Existence Problems for Sequences

In one sentence

A problem of the form “there exists a …” can be attacked in two ways:

construction: build it directly. With sequences you can build term by term, or build small ones first and assemble big ones from them — that is construction by mathematical induction;
indirectly: do not build it, but show that “none exists” leads to a contradiction. The pigeonhole principle is the most common tool.

The problem above: can $1$ to $n$ be arranged in a row so that no number is the average of some number on its left and some number on its right (that is, there are no $a_{i}, a_{j}, a_{k}$ , $i < j < k$ , forming an arithmetic sequence)?

A recursive construction: odds first, evens after

Step 1 / 5

Try it any old way
Place them in increasing order: after $1, 2$ , the $3$ is blocked ( $1, 2, 3$ is arithmetic). Building term by term easily runs into a dead end; the readout in the figure tells you whether you “can still finish”.
A key observation
Inside each half
Build it by induction
Not just powers of 2

Predict first

For $n = 3$ , how many of the $6$ arrangements of $1, 2, 3$ meet the requirement?

arrangements

Choose an answer first; then you can see the result.

Stop 1 · Infinite sequences: build one term at a time

Example There is an infinite sequence $a_{1}, a_{2}, \dots$ of integers greater than $1$ that are pairwise coprime.

“Infinite” sounds scary, but a sequence lets us build one term at a time: just show that once the first $n$ terms are built, the $(n + 1)$ -th can always be built, and by mathematical induction the whole sequence exists.

Make the next term coprime to every earlier term

Step 1 / 4

Start
Take $a_{1} = 2$ .

$a_{1} = 2$
How to build the next term
Why it is coprime
A few terms

Stop 2 · The pigeonhole principle: it exists, without building it

Example (a special case of the Erdős–Szekeres theorem) Any sequence of $10$ distinct real numbers has a monotone (increasing or decreasing) subsequence of length $4$ .

Nobody can “build” that subsequence here — the sequence is given to us arbitrarily. So go the other way: assume there is none, and count.

Give every term a label

Step 1 / 4

Labels
For the $i$ -th term, let $x_{i}$ be the length of the longest increasing subsequence ending at it, and $y_{i}$ the length of the longest decreasing subsequence ending at it.

$a_{i} ⟼ (x_{i}, y_{i})$
All labels are different
Suppose there is none of length 4
Contradiction

Compare the two approaches: Stop 1 produces the sequence, Stop 2 only guarantees that the subsequence exists. The first answers “what is it”, the second only “is there one” — but when the object is “given arbitrarily”, the second is often the only way.

Practice

Exercise 1Basic

In the sequence of Stop 1, $a_{1} = 2$ and $a_{n + 1} = a_{1} a_{2} \dots a_{n} + 1$ . Find $a_{5}$ .

Exercise 2Basic

Arrange $1$ to $16$ by the recursive “odds first, evens after” construction. Which number is in position $2$ ?

Exercise 3Advanced

What is the smallest $m$ such that every sequence of $m$ distinct real numbers has a monotone subsequence of length $3$ ?

Exercise 4Challenge

Prove that for every positive integer $n$ there are $n$ consecutive positive integers that are all composite.

In one sentence

A recursive construction: odds first, evens after

Stop 1 · Infinite sequences: build one term at a time

Make the next term coprime to every earlier term

Stop 2 · The pigeonhole principle: it exists, without building it

Give every term a label

Practice

Mistake Museum · Exhibits from this stop

I could not arrange it, so it does not exist

The pigeonhole principle says “there is one”, so you think you know which