(adsbygoogle = window.adsbygoogle || []).push({}); 1. The problem statement, all variables and given/known data

Prove by induction that no matter how one chooses a set of n+1 positive integers from the first 2n positive integers, one integer in the set divides another integer in the set.

2. The attempt at a solution

Tried direct induction. Base case easy to prove. P(n+1) is with n+2 integers from the first 2n+2. Suppose that at most one is 2n+1 or 2n+2 => there are at least n+1 to be chosen from the first 2n integers (which P(n) guarantees will contain two that divide each other). Therefore, I reduced the problem to "n integers from the first 2n, plus 2n+1 and 2n+2".

So now I have to prove that: given any set of n integers from 1 to 2n (EDIT: such that none divides another in the set), one of them divides 2n+1 OR 2n+2. I am clueless from here on. Maybe my whole approach is misguided? I have to emphasize that using induction is a necessity.

Thank you in advance for your help!

EDIT 2: I know the solution that does not require induction, with the bins based on 2^k * (2i+1) factorization of all the numbers there, and I can use that in the place where I am stuck, but that is extremely artificial because the same argument that I would use in the inductive step could be used completely not modified in the initial problem, so the induction would be superfluous. I am looking for a "real" inductive solution. Here's a link to non-inductive solution: http://www.mathnerds.com/best/NonDividingSets/index.aspx

**Physics Forums | Science Articles, Homework Help, Discussion**

Join Physics Forums Today!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

# Homework Help: Induction / divisibility problem

**Physics Forums | Science Articles, Homework Help, Discussion**