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

$\displaystyle n+1$ positive integers, none exceeding $\displaystyle 2n$

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

integer in the set.

Now I checked the base case for $\displaystyle n=1$. The problem also

assumes that there might be integers which repeat among these

$\displaystyle n+1$ integers. So, for $\displaystyle n=1$ all the following

sets need to be considered.

$\displaystyle \{1,1\},\{1,2\},\{2,2\}$

So we can establish that base case $\displaystyle P(1)$ holds.

Now let $\displaystyle P(n)$ be the proposition that given a set of

$\displaystyle n+1$ positive integers, none exceeding $\displaystyle 2n$

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

integer in the set.

For the induction case, let $\displaystyle n\geqslant 1$ be arbitrary

and also assume $\displaystyle P(n)$.To prove

$\displaystyle P(n+1)$ we assume that there is a set with

$\displaystyle n+2$ positive integers, none exceeding

$\displaystyle 2(n+1)=2n+2$.

Lets call this set A.

$\displaystyle \because n\geqslant 1\;\therefore n+2\geqslant 3$

So there are at least 3 elements in A.

Let $\displaystyle m$ be the maximum element of set A.

Now I am considering three cases here.

Case 1)

$\displaystyle m\leqslant 2n$

here we can define a new set

$\displaystyle A_1=A\setminus \{m\}$

now all the elements in $\displaystyle A_1$ do not exceed

$\displaystyle 2n$ and also $\displaystyle A_1$ has $\displaystyle n+1$

elements and I can now use inductive hypothesis here.

Case 2)

$\displaystyle m\leqslant 2n+1$

Again, we can define a new set

$\displaystyle A_1=A\setminus \{m\}$

now all the elements in $\displaystyle A_1$ do not exceed

$\displaystyle 2n$ and also $\displaystyle A_1$ has $\displaystyle n+1$

elements and I can now use inductive hypothesis here.

Case 3)

$\displaystyle m\leqslant 2n+2$

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

$\displaystyle 2n+1$ and $\displaystyle 2n+2$ are in A. So even after removing

m, we can have a set where $\displaystyle 2n+1$ is still in the set. And

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

Thanks

$\displaystyle \smile$