hi

Here is a problem I am trying to do from Kenneth Rosen's

"Discrete mathematics..."

Use mathematical induction to show that given a set of

positive integers, none exceeding

,there is at least one integer in this set that divides another

integer in the set.

Now I checked the base case for . The problem also

assumes that there might be integers which repeat among these

integers. So, for all the following

sets need to be considered.

So we can establish that base case holds.

Now let be the proposition that given a set of

positive integers, none exceeding

,there is at least one integer in this set that divides another

integer in the set.

For the induction case, let be arbitrary

and also assume .To prove

we assume that there is a set with

positive integers, none exceeding

.

Lets call this set A.

So there are at least 3 elements in A.

Let be the maximum element of set A.

Now I am considering three cases here.

Case 1)

here we can define a new set

now all the elements in do not exceed

and also has

elements and I can now use inductive hypothesis here.

Case 2)

Again, we can define a new set

now all the elements in do not exceed

and also has

elements and I can now use inductive hypothesis here.

Case 3)

Now here I see problem. There could be a case where both

and are in A. So even after removing

m, we can have a set where is still in the set. And

we can't use the inductive hypothesis here. How do I handle this case ?

Thanks