Prove that the natural numbers are either the result of the subtraction of two elements in a particular set or exist as elements in the set

Question

Prove that in a set made of natural numbers which every element follows ${a_n}$<2n and ${a_n}$<${a_{n+1}}$, every natural number is either found in the set or the result of the subtraction of two elements of this set. obviously the first element of the sequence will be one but the other elements have other possibilities for example the set could be 1,3,4,7,9, or it could be 1,3,5,7,9,... how do we go on to prove this?

Answer 1

You can do it by contradiction.

Let's suppose some number $n$ does not occur in the sequence. Then, the numbers $a_1,\dots,a_n$ are all distinct and lie in $\{1,\dots,n-1,n+1,\dots,2n-1\}$.

That set can be partitioned into $n-1$ pairs of numbers with distance $n$. By the pigeonhole principle, in one of the pairs both numbers must be one of the $a_1,\dots,a_n$.