DISCRETE MATH: Use math. induction to show that at least 1 integer can divide another

[VinnyCee]

1. The problem statement, all variables and given/known data

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



2. Relevant equations

Mathematical induction, others, I am not sure



3. The attempt at a solution

Let P(n) be the claim that there will be two integers (x,\,y) such that y divides x.

\left{1,\,2,\,\dots,\,2\,n\right} <----- Choose only n\,+\,1 of these.

Basis: Does P(1) hold?

\left{1,\,\dots,\,2\,n\right}\,=\,\left{1,\,2\righ t} <----- for n\,=\,1

2 is divisible by 1, so x = 2 and y = 1. P(1) is true.


Inductive hypothesis:

\left{1,\,2,\,\dots,\,2\,n,\,2\,n\,+\,1,\,2\,n\,+\ ,2\right} <----- Choose only n\,+\,2 of these

How do I prove that though?

[AlephZero]

Here's the start of a proof...

Let m be the largest integer in the set of n+1 integers.

If m <= 2(n-1), there are n integers in the set less than 2(n-1) , so by induction P(n) is true.

Now think about the cases where m = 2n-1 or m = 2n.

[HallsofIvy]

By the way- there is no requirement that the n integers be distinct. In the n= 1 case, the two integers may be {1, 2}, {1, 1} or {2,2}. Of course, if they are NOT distinct, then obviously one of the duplicates divides the other so you really only need to consider the case that they are distinct- but you should say that.

[dyang00]

Resurrecting old thread, I also really need help with this problem. I'm completely lost, I couldn't even come with what the OP got on my own.

Thanks anyway

[bryanfoobar]

By the way- there is no requirement that the n integers be distinct.

I believe there is that requirement, as the claim states that it is a set of positive integers. Sets contain unique elements.

Since Induction in general was part of your question, I would recommend looking at inductiveproofs.com -- they have a nice template for writing inductive proofs that you might find helpful.

Does the question hint at using weak or strong induction? (if you haven't heard of strong induction yet, that is helpful :) since we know it should use weak then!) The thing to think about is how can we get back to the smaller subset? AKA In the inductive step, we have a set of n+2 elements, all no higher than 2n+2, how do we talk about a subset of n+1 elements all no higher than 2n? What do we know about the other sets that don't contain that subset?