# Induction

• Nov 9th 2006, 08:19 AM
feiyingx
Induction
Hi! I have an induction question as follows:

Use induction to show that given a set of n+1 positive integers, none exceeding 2n, there is at least one integer in this set that divides another integer in the set.

Thanks!
• Nov 13th 2006, 03:34 PM
TriKri
Quote:

Originally Posted by feiyingx
Hi! I have an induction question as follows:

Use induction to show that given a set of n+1 positive integers, none exceeding 2n, there is at least one integer in this set that divides another integer in the set.

Thanks!

Start with filling the set from n+1 to 2n. There is no free number within the interval that you can choose cause it will divide the nunber that is twise as large, and you have only chosen n numbers.

Now, we can prove that for any set of n positive integer numbers <= 2n, where no of the numbers divides any other, and no more number can be added cause it will divide another of the numbers or be divided itself, it is impossible to change the value of one of the numbers making one place in the interval free to place yet another number in. And...

Or something like that, just continue on and I'm sure you will solve it :D