Induction to prove that a set of $n+1$ integers between $1$ and $2n$ has at least one number which divides another number in the set [duplicate]

Question

Question states: "Show that if $n+1$ integers between $1$ and $2n$ (inclusive) are chosen, the set of chosen integers will contain at least one number which divides another member of the same set."

I have found a non-inductive proof online, which uses pigeonhole principle and expressing each number of the chosen set as $2^{aj}$ where $j$ is an odd number from $\{1,3,5,...,2n-1\}$. (so there are $n$ boxes of $j$) So pretty much divide a number repeatedly by 2 until that number becomes odd. For example, we can express $56$ as $2^3 \times 7$. we have $n+1$ numbers which can fit into $n$ boxes, and by the Pigeon Hole Principle we conclude that there are two numbers in a given $j$ boxes; one of them divides the other.

However, my book says that I can prove the question by using induction. Obviously, the base case holds. Here is my progress so far:

Assume true for an integer $n$. We need to prove that an arbitrary set of $n+2$ integers from $\{1,...,2n,2n+1,2n+2\}$ have a number which divides another number from the chosen set. If either one or none of the two new numbers ($2n+1$ and $2n+2$) is chosen, we are done, since we must pick at least $n+1$ elements from the rest of the set $\{1,...,2n\}$ .

A problem arises if BOTH of the two new numbers are chosen. Then we are required to prove that an arbitrary set of $n$ numbers from the set $\{1,...,2n\}$ contains two numbers, one of which divide another, or that the same arbitrary set of numbers must contain a number that divides either $2n+1$ or $2n+2$. If the arbitrary set of $n$ numbers contain either $1$, $2$, or $n+1$, then we are done. So we must prove that an arbitrary set of $n$ numbers from the set $\{3,4,...,n-1,n,n+2,...,2n\}$ contains two numbers, one of which divide another, or that the same arbitrary set of numbers must contain a number that divides either $2n+1$ or $2n+2$.

How do I show this?

Answer 1

If for the $n+2$ you select only one of them is $2n +1$ or $2n+2$ then the remaining $n+1$ you picked are from $1... 2n$ and must have one number divide another.

If both of $2n+1$ and $2n+2$ are chosen then assume, for sake of a proof by contradiction, that none of the $n+2$ terms have any term dividing another... then you did not pick $n+1$ and none of the terms divide $n+1$ (which divides $2n + 2$). Discard $2n+1$ and $2n+2$ and pick $n+1$ instead. You now have $n+1$ terms from $1... 2n$. None of the terms that aren't $n+1$ divide $n+1$ or each other. $n+1$ doesn't divide any number less then or equal to $2n$. So none of the terms divide any other. That's a contradiction.

==== old answer where I made the faulty assumption that the terms had to be consecutive ===

Suppose you selected $\{m,m+1,.....m+n+1\}\subset \{1....2n\} $

Then $\{m,.....,m+n\}\subset\{1....2n\} $ has a number that divides another.

If $\{m,m+1,...m+n+1\}\not \subset \{1....2n\} $ then $2n+1 \in \{m,m+1,...m+n+1\}$.

Either $m+n+1=2n+1$ so $m=n$ and the set has $n $ and $2n $,

or $m+n+1=2n+2$ in which case $m=n+1$ and the set has $n+1$ and $2n+2$.