# Induction / divisibility problem

 P: 4 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/NonDiv...ets/index.aspx
 Sci Advisor HW Helper Thanks P: 25,235 Your thinking is pretty clear on this. Ok, so you've got n elements of [1,2n] that don't divide each other. Assume the opposite. That they don't divide 2n+2=2*(n+1). That means they don't divide (n+1). Does (n+1) divide anything in [1,2n]? What's wrong with this picture?
 P: 4 I'm sorry, I don't see how that helps. P: given any set of n integers from 1 to 2n such that none divides another in the set Q: one of them divides 2n+1 OR 2n+2 You suggested a proof by contradiction, Q' => P'. Q': given any set of n integers from 1 to 2n such that none divides 2n+1 nor 2n+2 P': one of them divides another in the set I don't understand your argument because it seems to me that you suggest that 2 and n+1 cannot be in the set. That doesn't tell me that given any set with that property Q' (i.e. any set without 2 and n+1 necessarily but not sufficiently), there will be one integer that divides another number in the set. Maybe you could elaborate a bit? Thanks for the fast reply.
 HW Helper P: 1,808 Induction / divisibility problem Dick has answered your question. If you assume that for some 2n, no n+1 positive integers below it are linearly independent, then that can never happen. So that is the contradiction you want to show. Try to deduce that there are n+1 linearly independent numbers below 2n.