• Support PF! Buy your school textbooks, materials and every day products Here!

DISCRETE MATH: Use math. induction to show that at least 1 integer can divide another

  • Thread starter VinnyCee
  • Start date
  • #1
489
0

Homework Statement



Use mathematical induction to show that given a set of [itex]n\,+\,1[/itex] positive integers, none exceeding [itex]2\,n[/itex], there is at least one integer in this set that divides another integer in the set.



Homework Equations



Mathematical induction, others, I am not sure



The Attempt at a Solution



Let [itex]P(n)[/itex] be the claim that there will be two integers [itex](x,\,y)[/itex] such that y divides x.

[tex]\left{1,\,2,\,\dots,\,2\,n\right}[/tex] <----- Choose only [itex]n\,+\,1[/itex] of these.

Basis: Does [itex]P(1)[/itex] hold?

[tex]\left{1,\,\dots,\,2\,n\right}\,=\,\left{1,\,2\right}[/tex] <----- for [itex]n\,=\,1[/itex]

2 is divisible by 1, so x = 2 and y = 1. [itex]P(1)[/itex] is true.


Inductive hypothesis:

[tex]\left{1,\,2,\,\dots,\,2\,n,\,2\,n\,+\,1,\,2\,n\,+\,2\right}[/tex] <----- Choose only [itex]n\,+\,2[/itex] of these

How do I prove that though?
 

Answers and Replies

  • #2
AlephZero
Science Advisor
Homework Helper
6,994
291
Here's the start of a proof...

Let m be the largest integer in the set of n+1 integers.

If m <= 2(n-1), there are n integers in the set less than 2(n-1) , so by induction P(n) is true.

Now think about the cases where m = 2n-1 or m = 2n.
 
  • #3
HallsofIvy
Science Advisor
Homework Helper
41,808
933
By the way- there is no requirement that the n integers be distinct. In the n= 1 case, the two integers may be {1, 2}, {1, 1} or {2,2}. Of course, if they are NOT distinct, then obviously one of the duplicates divides the other so you really only need to consider the case that they are distinct- but you should say that.
 
  • #4
1
0


Resurrecting old thread, I also really need help with this problem. I'm completely lost, I couldn't even come with what the OP got on my own.

Thanks anyway
 
  • #5


By the way- there is no requirement that the n integers be distinct.
I believe there is that requirement, as the claim states that it is a set of positive integers. Sets contain unique elements.

Since Induction in general was part of your question, I would recommend looking at inductiveproofs.com -- they have a nice template for writing inductive proofs that you might find helpful.

Does the question hint at using weak or strong induction? (if you haven't heard of strong induction yet, that is helpful :) since we know it should use weak then!) The thing to think about is how can we get back to the smaller subset? AKA In the inductive step, we have a set of n+2 elements, all no higher than 2n+2, how do we talk about a subset of n+1 elements all no higher than 2n? What do we know about the other sets that don't contain that subset?
 

Related Threads on DISCRETE MATH: Use math. induction to show that at least 1 integer can divide another

Replies
0
Views
12K
  • Last Post
Replies
6
Views
2K
  • Last Post
Replies
1
Views
801
Replies
7
Views
4K
  • Last Post
Replies
9
Views
2K
Replies
5
Views
1K
Replies
8
Views
524
Replies
1
Views
798
Replies
4
Views
3K
Replies
13
Views
2K
Top