Originally Posted by

**oldguynewstudent** Can anyone verify whether the following proof is correct or incorrect? If incorrect please explain where and why I went wrong?

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.

S = { $\displaystyle x_i$ such that i = 1,2,...,n+1, $\displaystyle x_i$ $\displaystyle \le$ 2n}

Show that $\displaystyle \exists$ $\displaystyle x_i$ such that $\displaystyle x_i$ | $\displaystyle x_j$ i $\displaystyle \not=$ j

Basis Step: P(1): case 1: S={1,2} 1 | 2 so P(1) is true

case 2: S={1,1} 1 | 1 so P(1) is true

Inductive Step: P(k) $\displaystyle \Rightarrow$ P(k+1)

Given S = { $\displaystyle x_i$ such that i = 1,2,...,k+1, $\displaystyle x_i$ $\displaystyle \le$ 2k}

$\displaystyle \exists$ $\displaystyle x_i$ such that $\displaystyle x_i$ | $\displaystyle x_j$ i $\displaystyle \not=$ j

Prove that $\displaystyle \exists$ $\displaystyle x_s$ such that $\displaystyle x_s$ | $\displaystyle x_t$, s $\displaystyle \not=$ t

where $\displaystyle x_s$ $\displaystyle \epsilon$ { $\displaystyle x_i$ such that i = 1,2,...,k+1,(k+1)+1 $\displaystyle x_i$ $\displaystyle \le$ 2(k+1)}

Note that { $\displaystyle x_i$ such that i = 1,2,...,k+1,(k+1)+1 $\displaystyle x_i$ $\displaystyle \le$ 2(k+1)} = S $\displaystyle \cup$ { $\displaystyle x_i$ such that i = (k+1)+1 $\displaystyle x_i$ $\displaystyle \le$ 2(k+1)}

Choose $\displaystyle x_s$ = $\displaystyle x_i$ that divides $\displaystyle x_j$ and $\displaystyle x_t$ = $\displaystyle x_j$ from the given part.

This proves P(k+1) is true, so the original statement is true by M.I.