Induction question Given a set of n+1 numbers from 1,2....,2n . How to prove by induction that there exists two numbers in the set such that one divides the other ???
 A: Assume we have the statement for 2n, and we are given n+2 numbers up to 2n+2. If n+1 amon them are at most 2n, then we are done by induction. So only n of them can be at most 2n, that is, 2n+1 and 2n+2 are among the numbers. Then n+1 is not among the numbers (as n+1 divides 2n+2). We can now replace 2n+2 by n+1 and still keep the condition. This is a contradiction, as now we have n+1 numbers up to 2n. QED.  
A: As Gjergji points out, I believe this is a problem that Erdos liked to test young children with, and the classical solution uses the pigeonhole principle.  However, I will answer the OP's question, since there is indeed a proof by induction.  
Clearly, the claim holds for $n=1$.  Now, assume that it holds for $n-1$, and consider a subset $X$ of size $n+1$ from $[2n]$.  If $X$ contains at least $n$ elements from $[2n-2]$, then we are done by induction.  So, $X$ must contain both $2n-1$ and $2n$.  Now, if $n \in X$, we are done.  So, let $X'$ be obtained from $X$ by removing $2n$ and adding $n$.  By induction, $X'$ contains two numbers one of which divides the other, and hence $X$ does too.
