Mathematical Induction, Discrete math problem help!!!!!?

Question

Use mathematical 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 divide another integer in the set.

Answer 1

I will prove it without induction and come back if I think of a way to do it without induction.

Note that all positive integers can be written as:
k * 2^j, where k is odd and j is a nonnegative integer

Since there are only n odd positive integers not exceeding 2n, any set of n+1 positive integers not exceeding 2n must include two with the same k, that is, it must include two numbers k * 2^i and k*2^j for some odd k and some nonnegative integers i and j, such that i < j.

But since k * 2^i divides k * 2^j, two numbers inthe set divide each other.

----------------------------------------------------------------------

To do this by induction, you would assume it for n and then prove for n+1. To do this you would have to show that 2n+1 and 2n+2 could not be added to the maximal subset of 1 ... 2n. To do that, I think it would suffice to argue that some number that divides n+1 must be in the any maximum subset of 1 ... 2n.

Answer 2

evaluate n = a million. 10n - 2n = 10 - 2 = 8, that's divisible with the aid of 4. Now anticipate actual for an arbitrary variety, ok. Is it actual for ok+a million? evaluate 10(ok+a million) - 2(ok+a million) = 10k + 10 - 2k - 2 = (10k - 2k) + (10 - 2). we've shown that 4 divides (10-2), and we've assumed that 4 divides (10k-2k). as a result, (10k-2k) + (10-2) could be expressed as 4 * (m + n). So, 4 divides 10(ok+a million) - 2(ok+a million). QED