- #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.

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

__Basis__[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?