$n + 1$ numbers are picked at random from $2n$ integers $1, 2, 3, \ldots, 2n$. Prove that among the numbers picked we can find at least two, one of which is divisible by the other.
If we try to chose numbers from the right most end from 2n and the approach n we see that there are two pairs of numbers n, 2n and n-1, 2n-1 which satisfy this.
Similarly, I have tried some possibilities, all of them satisfy but I am not able to think of a proof.
Also, this problem is given on the chapter titled "Arithmetic of Integers" that is, related to Number Theory. I don't know anything about Combinatorics except Permutations and Combinations.
Can somebody provide me a hint?
Any help would be highly appreciated.
Edit:— I've just realized that this problem is to be proven via mathematical induction. I would be greatly thankful to anyone who would provide me a solution via induction.