# Homework Help: Induction proof

1. Dec 26, 2007

### ehrenfest

[SOLVED] induction proof

1. The problem statement, all variables and given/known data
Given a set of n+1 integers between 1 and 2n (inclusive), show that at least one member of the set must divide another member of the set.
Use induction.

2. Relevant equations

3. The attempt at a solution
When n=1, this is obvious.
Assume the result is true for n=k. Now we have a set of k+2 integers between 1 and 2k+2 and we want to show that one member divides another. If 2k+2 or 2k+1 is NOT in our set, then we have k+1 integers between 1 and 2k, and we apply the induction hypothesis. I am having trouble with the case where 2k+2 and 2k+1 are both in the set. If 1, 2 or k+1 is also in our set we are done. If not, we have k-1 integers in {3,4,...,k} union {k+2,...,2k}, and I am unsure where the induction hypothesis comes in.

2. Dec 28, 2007

### ZioX

Look what you have left when you take out 2k+1 and 2k+2.

3. Dec 28, 2007

### Jimmy Snyder

Better check for n=2.

4. Dec 28, 2007

### D H

Staff Emeritus
That is the only case you need to trouble yourself with. Assume that the conjecture is true for n=1,...,k but false for n=k+1, and get a contradiction. If the conjecture is true for n=k, then there at most k integers in {1,2k} that are all relatively prime with respect to each other. To disprove the conjecture for n=k+1, you will need those k integers plus two more, or 2k+1 and 2k+2.

He has to find 3 integers in {1,2,3,4}, none of which divides the other. One is obviously out, leaving {2,3,4}, and 2 divides 4.

5. Dec 28, 2007

### ehrenfest

Two numbers being relatively prime and two numbers having the property that neither is divisible by the other is not the same thing. The former implies the latter, but the latter does not imply the former.

For example, 8 does not divide 6 and 6 does not divide 8, but 6 and 8 are not relatively prime.

Last edited: Dec 28, 2007
6. Dec 28, 2007

### ehrenfest

Yes. 1 divides every integer.

7. Dec 28, 2007

### D H

Staff Emeritus
Sorry, I used the wrong term. My logic still stands. You need 2k+1 and 2k+2 in your set of k+2 numbers, none of which divides another, to falsify the conjecture for n=k+1.

8. Dec 28, 2007

### ehrenfest

I do not see why you're logic still stands.

There at most k integers in {1,2k} that have the property that none divides another. Because I just showed that relative primeness is more general than that, there could be more than k integers that are relatively prime.

9. Dec 28, 2007

### D H

Staff Emeritus
ARGGHH. I said "I used the wrong term". How does the term "set of mutually non-dividing integers" suit you? Rather than edit my old post, here is the correction:

This is the only case you need to trouble yourself with. Assume that the conjecture is true for n=1,...,k but false for n=k+1, and get a contradiction. If the conjecture is true for n=k, then there at most k integers in {1,2k} none of which divides another. To disprove the conjecture for n=k+1, you will need k+2 mutually non-dividing integers, or those k integers for n=k plus two more. The only two that are available are 2k+1 and 2k+2.

Note that if the largest subset of mutually non-dividing integers of the set {1,2k} is fewer than k elements the conjecture must hold for n=k+1.

10. Dec 28, 2007

### ehrenfest

I am sorry, I still don't see where the contradiction is. I agree that

"there at most k integers in {1,2k} none of which divides another"

and that

"To disprove the conjecture for n=k+1, you will need k+2 mutually non-dividing integers, or those k integers for n=k plus two more. The only two that are available are 2k+1 and 2k+2."

But there could be a set S of EXACTLY k integers in {1,2k} none of which divides another. Then when you add 2k+1 and 2k+2 to S, you MIGHT get k+2 mutually non-dividing integers in {1,2k+2}.
I think we need to show that either 2 or k+1 must be in S.

11. Dec 28, 2007

### D H

Staff Emeritus
I am not doing your homework for you, just giving you hints. I did not say their is a contradiction; I said you need to establish a contradiction. I left that act of establishing the contradiction as an exercise for you to complete.

12. Dec 28, 2007

### D H

Staff Emeritus
For k=7, the set S={4,5,6,7,9,11,13} has 7 members and contains neither 2 nor 8. The existence of 4 in the set does get rid of the 16 for k=8).
For k=11, there are several sets S with 11 members that do not contain 2 or 11. They do contain 4 or 6 (or both).

13. Dec 28, 2007

### ehrenfest

My idea is this:

We want to show that a (k+1) element subset S of {1,2,...,2k+2} cannot be mutually nondividing. We reduced the problem to the case where S contains 2k+1 and 2k+2. I think we want to show that if 1, 2, or k+1 are not in S then, there must be x,y in {3,4,...,k} union {k+2,...,2k} and in S such that x divides y. That is what I am having so much trouble trying to prove!

Note that the last sentence in my original post is wrong: "we have k-1 integers" should be "we have k integers".

Note also that this problem is driving me INSANE.

14. Dec 28, 2007

### ehrenfest

What you have left in your set is k integers in {1,...,2k}. What do you do with that information?
By the strong induction hypothesis, we know that any set of k+1 elements in {1,...,2k} is not mutually non-dividing. But we only have k elements in this set!

Last edited: Dec 28, 2007
15. Dec 28, 2007

### Dick

So with all you done so far, you have k numbers in 1...2k which are mutually nondividing (call this set K), since KU{2k+1,2k+2} is mutually nondividing, right? You've already observed that k+1 is not in K. If you form the set KU{k+1} then your induction hypothesis says that it IS mutually dividing. Therefore either a number in K divides k+1 or k+1 divides a number in K. Which is it? Now finish the problem.

16. Dec 28, 2007

### ehrenfest

AHA. How could I miss that?

k+1 does not divide anything less than or equal to 2k, so there exists x in K such that x divides k+1. But then x divides 2k+2 which contradicts the fact that K union {2k+1,2k+2} is mutually non-dividing.