# Prove using induction that from a set of $n+1$ numbers from $\{1,2,..2n\}$, at least one number will evenly divide another.

Given a set of $n+1$ numbers out of the first $2n$ natural numbers, $\{1,2,\ldots,2n\}$, prove that there are two numbers in the set, one of which divides the other.

I can't tell if I'm reducing the problem in the right way. Would it be something like:

Induction Hypothesis: A set of $n+1$ numbers from the first $2n$ natural numbers contains two numbers, one of which evenly divides the other.

Base Case: $n=1$, $\{1,2\}$, 2 is divisible by 1.

Consider a set of $n+2$ numbers, $A$, from the first $2n+2$ natural numbers. There are three cases:

1. Each number in $A$ is less than or equal to $2n$. The proof follows from the induction hypothesis.

2. One number in $A$ is greater than $2n$. The remaining set of $n+1$ numbers must each be less than or equal to $2n$. The proof follows from the induction hypothesis.

3. $A$ contains both $2n+1$ and $2n+2$. I'm not sure how to solve this case.

I'm working through Udi Manber's Introduction To Algorithms: A Creative Approach for personal development, so in keeping with the spirit of the book, I'm trying to use induction.

Without induction, the question is identical to Prove two numbers of a set will evenly divide the other

$$3$$.
1. If $$n+1$$ is also in $$A$$, then $$n+1|2n+2$$.
2. If $$n+1$$ is not in $$A$$, then if we replace $$2n+2$$ with $$n+1$$, say the new set is $$B$$, we can use the induction hypothesis like in case $$2$$ to conclude there exist $$a|b$$ in $$B$$. If both $$a,b\neq n+1$$, then $$a,b$$ are in $$A$$ and we are done. If either $$a,b=n+1$$ then the other is in $$A$$ and that number divides $$2n+2$$. $$\blacksquare$$
• Oh, clever. So, in case 2, you're finding either a divisor of 2n+2 or a totally separate $a$ and $b$. – Joe Oct 23 '15 at 3:00
• What if, in case 2, we end up with $(n+1) | b$ in $B$ and $b$ is odd. Then we would not be able to replace $(n+1)$ with $2(n+1)$, correct? – Elliot Gorokhovsky Dec 9 '19 at 7:26
• Ah, the key is that $(n+1)$ cannot divide any integer in $B$ since $\max B \leq 2n$. This may be worth mentioning in the proof; you say "if either $a,b = n+1$", but it must be the case that $b$ specifically is equal to $n+1$. – Elliot Gorokhovsky Dec 9 '19 at 7:28