Show that the sequence contains at least one prime term Problem:
Given a sequence of $n$ natural numbers $a_1,a_2,...,a_n$ with $1<a_i<(2n-1)^2$, $(i=\overline{1,n})$ and $i < j \iff a_i < a_j$. If all of the terms are pairwise coprime, show that at least one of them must be prime.

My try: (based on weak arguments)

*

*Claim: $p_n \ge 2n-1$ (i.e. $n^\text{th}$ prime number is not less than $n^\text{th}$ odd number).


*Proof: $\square$ Trivial to check for some initial $n$'s:$$p_1=2 \ge 1$$ $$p_2=3 \ge 3$$ $$p_3=5 \ge 5$$ $$...$$
Now, since $p_{i+1} - p_i \ge 2 \ \ (\forall ~ i \ge 2)$ but the difference between any two consecutive odd numbers is $2$, the claim is obvious. $\blacksquare$
For the sake of contradiction, assume that there is no prime in them. Since $\gcd(a_i,a_j)=1, \ \ (i\neq j)$, all terms of the sequence must have distinct prime factors. As we do not want to be run out of prime factors that are less than $2n-1$, we better assume $a_i=p_i^2$ (if we can prove that the original statement is true for this case, then it is true in general since for any other construction of $a_i'$ we will have $a_i<a_i'$).
Then, $a_n = p_n^2$, but the claim implies $a_n=p_n^2 \ge (2n-1)^2$. A contradiction.
Therefore, at least one of the terms must be prime.

However, this "solution" seems to have many errors yet I cannot fix. I think I started approaching in the wrong way.
Any help is appreciated.
 A: I would not say that your proof has many errors. It has some gaps but it is basically correct.
Let us order all these sequences in Short-Lex order (first look at the first terms, if they are equal, look at the second terms, etc., shorter sequences are smaller).
Take the smallest in the Short-Lex order sequence $a_1,...a_n$ without prime numbers where numbers are pairwise coprime.
Then as you notice primes dividing different  $a_i$ are different. Let $p_1,...,p_m$ be all primes dividing $a_1,...,a_n$, $p_1<...<p_m$.
The number $a_1$ is a product of some $p_j$ ($p_{i_1}<...<p_{i_{k_1}}$), $k_1>1$. None of the other $a_s, s>1$ is divisible by any of these $p_{i_s}$. Then $a_1\ge p_{i_1}^2$. And if we replace in our sequence $a_1$ by $p_{i_1}^2$, the new sequence will not be bigger in the lexicographic order and still satisfy the conditions. Hence $a_1=p_{i_1}^2$. Now look at the next number, $a_2$. By the same argument, we can assume that it is the square of a prime. Note that when we replace $a_2$ by $p^2$ where $p$ is the first prime dividing $a_2$, $p^2$ may be smaller than $a_1$; in that case we  switch $a_1, a_2$.
Therefore we can assume that all numbers in the sequence $a_1,...,a_n$ are squares of primes $p_1^2,...,p_n^2$, $p_1<...<p_n$. But that contradicts, as you notice, the inequality $a_i<(2n-1)^2$. Q.E.D.
