Statement
Use mathematical induction to show that given a set of n + 1 positive integers, none exceeding 2n, there is at least one integer in this set that divides another integer in the set.
It's clear that the set can't contain two equal integers because one divides the other.
Basis step:
When n=1 the set S has two positive integers, namely S = {1,2}, and 1 divides 2.
Inductive step
Let's assume that when a set S has K+1 positive integers and each one is not greater than 2K, there is at least one integer in this set that divides another integer in the set.
Now I'm stuck, I don't know how to show that assuming this hypothesis I can prove that the statement holds for (K+1)+1.
##I'm bad at English, sentences may be wrong in grammar.
Let $P(n)$ be any subset $S$ containing $n+1$ distinct positive integers no exceeding $2n$ must have at least one pair of integers in which one can divide the other or vise versa.
Basis Step: $P(1)$ is true,because $S = \{1,2\}$ and $1 | 2$.
Inductive Step: When $P(k)$ is true, $P(k+1)$ states that set $S$ of $k+2$ elements must contain no less than one pair. There are $3$ cases below:
A: No element of $S$ is in $Y=\{2k+1, 2k+2\}$. So $k+2$ elements are no bigger than $2k$. $P(k)$ makes it true.
B: Only one element is in $Y$. $P(k)$ makes it true as well.
C: Two elements are in $Y$. Let $X = S - Y$, which contains $k$ elements no exceeding $2k$. $2k+1$ may be prime, so we don't care about it.
Assuming the contradiction, no pairs are found in $S$. With $2k+2$ in $S$, if $k+1$ in $S$, $P(k+1)$ is true. If $k+1$ is not in $S$, obviously all factors of $2k+2$ within $2k$ are also factors of $k+1$.Then we can swap $2k+2$ in $S$ with $k+1$ to form $S'$ and don't change the number of pairs in $S$. Case B makes $S'$ contains at least one pair, So does $S$. As a result, the contradiction is false.