# Thread: induction problem on set of positive numbers

1. ## induction problem on set of positive numbers

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
$n+1$ positive integers, none exceeding $2n$
,there is at least one integer in this set that divides another
integer in the set.

Now I checked the base case for $n=1$. The problem also
assumes that there might be integers which repeat among these
$n+1$ integers. So, for $n=1$ all the following
sets need to be considered.

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

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

Now let $P(n)$ be the proposition that given a set of
$n+1$ positive integers, none exceeding $2n$
,there is at least one integer in this set that divides another
integer in the set.

For the induction case, let $n\geqslant 1$ be arbitrary
and also assume $P(n)$.To prove
$P(n+1)$ we assume that there is a set with
$n+2$ positive integers, none exceeding
$2(n+1)=2n+2$.

Lets call this set A.

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

So there are at least 3 elements in A.
Let $m$ be the maximum element of set A.
Now I am considering three cases here.

Case 1)

$m\leqslant 2n$

here we can define a new set

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

now all the elements in $A_1$ do not exceed
$2n$ and also $A_1$ has $n+1$
elements and I can now use inductive hypothesis here.

Case 2)

$m\leqslant 2n+1$

Again, we can define a new set

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

now all the elements in $A_1$ do not exceed
$2n$ and also $A_1$ has $n+1$
elements and I can now use inductive hypothesis here.

Case 3)

$m\leqslant 2n+2$

Now here I see problem. There could be a case where both
$2n+1$ and $2n+2$ are in A. So even after removing
m, we can have a set where $2n+1$ is still in the set. And
we can't use the inductive hypothesis here. How do I handle this case ?

Thanks

$\smile$

2. ## Re: induction problem on set of positive numbers

well, one thing is to see that we don't lose any generality by assuming the numbers are distinct. why? becuase if two numbers are the same, say k is the repeated element, then k|k.

now, consider A - {2n+1,2n+2}. we can apply the induction hypothesis to that set. and if we have a divisible pair in that set, we have a divisible pair in A.

but....for this to be "legal", we must check an additional base case: n = 2.

3. ## Re: induction problem on set of positive numbers

hi Deveno

Here I outline the whole solution as deviced by me.
I have already proven this for n=1. Now let n=2.
Now I am assuming all the elements are distinct. So
the possible sets are

$\{1,2,3\},\{2,3,4\},\{1,2,4\},\{1,3,4\}$

As we can see in every set there is at least one integer
which divides another integer. So P(2).Now we to the
induction case.

To prove P(n+1), we assume that there is a set of
$n+2$ positive integers, none exceeding
$2(n+1)=2n+2$. Lets call this set A.
Let m be the maximum of A. Also we assume the
inductive hypothesis P(n) and let $n\geqslant 2$
be arbitrary.
I am assuming that all elements of A are distinct ...

Case 1: $m\leqslant 2n$

define new set $B=A\setminus \{m\}$

So B has $n+1$ positive numbers and
none exceed $2n$. Using P(n) ,
there is at least one integer in this set
that divides another integer in the set.
Since

$A=B\cup \{m\}$

there is at least one integer in A that divides
another integer in A. Hence P(n+1).

Case 2: $m=2n+1$

define new set $B=A\setminus \{m\}$

So B has $n+1$ positive numbers and
none exceed $2n$. Using P(n) ,
there is at least one integer in this set
that divides another integer in the set.
Since

$A=B\cup \{m\}$

there is at least one integer in A that divides
another integer in A. Hence P(n+1).

Case 3: $m=2n+2$

here we have two possibilities,

$2n+1 \notin A$

$2n+1 \in A$

in the first case, define new set

$B=A\setminus \{m\}$

So B has $n+1$ positive numbers and
none exceed $2n$. Using P(n) ,
there is at least one integer in this set
that divides another integer in the set.
Since

$A=B\cup \{m\}$

there is at least one integer in A that divides
another integer in A. Hence P(n+1).

in the second case, define new set

$B=A\setminus\{2n+1,m\}$

also define a set

$C=\{1,2,\cdots,2n\}\setminus B$

Now B has n elements and

$\because n\geqslant 2\;\therefore \forall n\geqslant 2\; C\neq \varnothing$

So we can choose an element in C, say $'a'$. By the construction of
C, $'a'$ doesn not exceed $2n$. Define new set

$G=B\cup\{a\}$

so G has $n+1$ elements, none of which exceed $2n$.
Using P(n), there is at least one integer in this set
that divides another integer in the set.
Let

$K=G\cup \{m\}$

there is at least one integer in this set
that divides another integer in the set.. also
K has $n+2$ elements , none of which
exceed $2n+2$ . Hence P(n+1).

Since all cases are exhausted , so P(n+1).

Is it correct reasoning ?

4. ## Re: induction problem on set of positive numbers

Originally Posted by Deveno
now, consider A - {2n+1,2n+2}. we can apply the induction hypothesis to that set. and if we have a divisible pair in that set, we have a divisible pair in A.
But if 2n + 1, 2n + 2 ∈ A, then |A - {2n + 1, 2n + 2}| = n, so the induction hypothesis cannot be used (it applies to sets of size n + 1).

5. ## Re: induction problem on set of positive numbers

Originally Posted by issacnewton
Let

$K=G\cup \{m\}$

there is at least one integer in this set
that divides another integer in the set.. also
K has $n+2$ elements , none of which
exceed $2n+2$ . Hence P(n+1).
You had to prove that A has an integer that divides another, and you instead constructed a new set K.

6. ## Re: induction problem on set of positive numbers

Oh I see , any set which has the property of A or K should have at least one integer in set that divides another integer in the set...

But am I close to the solution or far away ?

7. ## Re: induction problem on set of positive numbers

Originally Posted by issacnewton
But am I close to the solution or far away ?
To be honest, I don't know how to prove this at this time. Obviously, the difficult case in the induction step is when both 2n + 1 and 2n + 2 (the maximum) are in A where |A| = n + 2. Maybe somebody else can help.

8. ## Re: induction problem on set of positive numbers

Originally Posted by emakarov
But if 2n + 1, 2n + 2 ∈ A, then |A - {2n + 1, 2n + 2}| = n, so the induction hypothesis cannot be used (it applies to sets of size n + 1).
1) one could use strong induction, instead.

2) if we have proved two base cases, we are free to use the n AND n-1 cases (sets of size n+1, and sets of size n).

here is how it works:

true for 1, true for 2.

true for 3 if true for 2 or true for 1, thus true.

true for 4 if true for 3 or true for 2, thus true.

and so on......

3) do two separate cases: n even, n = 2k, or n odd, n = 2k-1, and use induction on k (twice)

all of these are valid methods.....

9. ## Re: induction problem on set of positive numbers

Originally Posted by emakarov
But if 2n + 1, 2n + 2 ∈ A, then |A - {2n + 1, 2n + 2}| = n, so the induction hypothesis cannot be used (it applies to sets of size n + 1).
Originally Posted by Deveno
1) one could use strong induction, instead.
The induction hypothesis can't be used not because the size of the set is 2 (not 1) less than the size in the conclusion of the induction step, but because |A - {2n + 1, 2n + 2}| = n, but you can only guarantee that max(A - {2n + 1, 2n + 2}) <= 2n. To remind, the induction statement P(n) is

For any set A of positive integers such that |A| = n + 1 and max(A) <= 2n, one element of A divides another.

There are not enough elements in A - {2n + 1, 2n + 2} to invoke the induction hypothesis.

10. ## Re: induction problem on set of positive numbers

one can do an induction argument where you "go up by twos" as long as you prove 2 "base cases". you should convince yourself that this is so, i'm not just making it up. a schema for this would look something like:

if [P(0) & P(1)] & [(P(k-1) v P(k))-->P(k+1)] then P(n) for all n.

this is just a limited form of strong induction, except we only rely on one of the last two cases to be true, instead of all previous cases. do you doubt that strong induction is a valid form of inductive proof?

EDIT: oh, i see what you are saying...if we take two elements out of A, then P(n-1) requires all the numbers to be less than or equal to 2n-2, and we might still have 2n-1 and 2n in our set.

11. ## Re: induction problem on set of positive numbers

Originally Posted by Deveno

if [P(0) & P(1)] & [(P(k-1) $\wedge$ P(k))-->P(k+1)] then P(n) for all n.

this is just a limited form of strong induction, except we only rely on one of the last two cases to be true, instead of all previous cases. do you doubt that strong induction is a valid form of inductive proof?
it should be like this

12. ## Re: induction problem on set of positive numbers

Hello

Let me try to prove what Deveno is saying.....

Theorem:Show that the following form of mathematical induction
is a valid method to prove that $P(n)$ is true for all positive integers
$n$.

Basis Step: $P(1),P(2)$ are true
Inductive Step: For each positive integer $k$
if $P(k)$ and $P(k+1)$ both are true then $P(k+2)$ is true.

Proof: Suppose that a statement $\forall n P(n)$ has been proved
by this method.Let $S$ be the set of counterexamples to $P$. So let

$S=\{n\lvert \;\neg P(n)\}$

We will show that $S=\varnothing$. If $S\neq \varnothing$, then
let $n$ be the minimum element of $S$ (which exists by the well-ordering property).
Clearly $n\neq 1, n\neq 2$ , by the base cases of our proof method.
So $n\geqslant 3$. Since $n$ is the least element of $S$, we know that
$P(n-1),P(n-2)$ are true. Therefore by inductive step of our proof method, we know
that $P(n)$ is also true. This contradicts the choice of $n$.
Therefore $S=\varnothing$ as desired.

13. ## Re: induction problem on set of positive numbers

Originally Posted by issacnewton
Let me try to prove what Deveno is saying.....
That's correct. Note that the well-ordering property is just the contrapositive of strong induction. The fact in the previous post can also be proved by regular induction using Q(n) = P(n) /\ P(n + 1). Similarly, strong induction can be proved using regular one where Q(n) is "for all k < n, P(n)". But if this topic needs further discussion, it's better to start a new thread.

14. ## Re: induction problem on set of positive numbers

OK, I got it. So, the difficult case is when 2n + 1, 2n + 2 ∈ A and |A| = n + 2. We have the induction hypothesis:

for any set B of positive integers such that |B| = n + 1 and max(B) <= 2n, one element of B divides another.

Hint: consider A ∪ {n + 1} - {2n + 1, 2n + 2}.

15. ## Re: induction problem on set of positive numbers

makarov you beat me. I had already solved the problem using that line of
thought. here's the solution

I think I have found the solution. Lets hope its right this
time. The only case where I got stuck was the case where
set A had both $2n+1$ and $2n+2$. We have to
prove that there is at least one integer in A which divides
another integer. I am going to try proof by contradiction.
So assume that there is no pair of integers in A such that
one divides the other.

$\because (n+1)\lvert (2n+2)\therefore (n+1)\notin A$

Now define the set B as

$B=A\setminus \{2n+1,2n+2\}$

also define the set C as

$C=B\cup \{n+1\}$

$\because n\geqslant 1\therefore n+1\leqslant 2n$

So, C has $n+1$ positive integers and none exceed
$2n$. We can use inductive hypothesis on C and
conclude that there is at least one integer in C which
divides another. By assumption, there is no such pair
of integers among the elements of B. So it must be true that
either $n+1$ divides another integer in C or
some another integer divides $n+1$.

Case 1: some another interger in C divides $n+1$.

Let's call this integer, k.

$\because (n+1)\lvert (2n+2)\therefore k\lvert (2n+2)$

So, there is a pair of integers in A so that one divides another.

Case 2: $n+1$ divides another integer in C.

Let's call this another integer in C , k. Since k is different from
$n+1$ , $k\in A$

$\because (n+1)\lvert k\;\therefore (n+1)j=k\quad j\geqslant 1$

If $j=1$ then $n+1 \in A$ which is contradiction.

If $j>1\;\;\Rightarrow k\geqslant (2n+2)$

which is a contradiction since k doesn't exceed $2n$.

Since the cases are exhausted, original assumption is incorrect. Hence
A has at least one interger which divides another.Hence
$P(n+1)$.

Page 1 of 2 12 Last