Induction Proof for Divisibility

[ehrenfest]

[SOLVED] induction proof

Homework Statement

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.

Homework Equations

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.

 

[ZioX]

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

 

[Jimmy Snyder]

Better check for n=2.

 

[D H]

I am having trouble with the case where 2k+2 and 2k+1 are both in the set.

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.

Better check for n=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.

 

[ehrenfest]

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.

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.

 

[ehrenfest]

Are we counting 1 as dividing another number?

Yes. 1 divides every integer.

 

[D H]

Two numbers being relatively prime and two numbers having the property that neither is divisible by the other is not the same thing.

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.

 

[ehrenfest]

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.

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

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.

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.

 

[D H]

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:

I am having trouble with the case where 2k+2 and 2k+1 are both in the set.

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.

 

[ehrenfest]

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.

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.

 

[D H]

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

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.

 

[D H]

I think we need to show that either 2 or k+1 must be in S.

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).

 

[ehrenfest]

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).

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.

 

[ehrenfest]

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

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!

 

[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.

 

[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.