- #1
VinnyCee
- 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?