Use mathematical induction 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.
I can't understand why when n= 1 that this equation is correct .I think I can put the integer likes 3 and 5 that don't meet the answer.
Now my first step is clear, I don't quite understand how should I think for the next step.
Let $P(n)$ be the proposition that given any set of integers $\{a_j\}$ containing $n+1$ distinct $a_j$ all of which are less than or equal to $2n$, then there exists some $j_1 \neq j_2$ such that $a_{j_1}$ divides $a_{j_2}$.
$P(1)$ is trivial to prove: For any set of two integers all of which are less than or equal to 2, either that set contains two identical integers (which divide each other) or it contains $1$, which divides $2$.
Now say that $P(n)$ holds and that $P(n+1)$ is false. Then since $P(n+1)$ there there is some set $S \equiv \{s_j\}$ containing $n+1+1$ integers and all the $s_j \leq 2n+2$, and no $s_j$ divides any $s_k$ for $k \neq j$.
Unless $2n+1 \in S$ and $2n+2 \in S$, the set $T = S-s_j: s_j > 2n$ contains at least $n+1$ integers, no of which exceed $2n$, and by $P(n)$ it is known that one of these elements divides another one. Since we know that no two element of $S$ divides another element of $S$ that can't be. So if $S$ exists,
$$ 2n+1 \in S \text{ and } 2n+2 \in S $$
We then know that $(n+1) \not \in S$ since that divides $(2n+2)$.
Now consider the set $U = S - \{(2n+1), (2n+2)\} + \{(n+1)\}$. $U$ has $n+1$ elements, all of which are less than or equal to $2n$. So by $P(n)$ one of those elements divides another. But if the two elements in question do not include the element $(n+1)$ then they also divide each other when considered as elements of $S$, which by assumption cannot be the case.
So some element of $u\in U$ divides $n+1$ (or $n+1$ divides some other element of $U$, which cannot be since the maximum element in $U$ is less than $2n+1$).
But $u\in S$ and $u|n+1 \implies u|2n+2$, yet $2n+2 \in S$ so we have a contradiction again.
Therefore if $P(n)$ holds, $P(n+1)$ must be true, thus establishing induction.
HINT:
Divide the numbers from $1$ to $2n$ into $n$ groups. Each group is a chain of numbers, any two numbers in the same group, one is a multiple of the other.
For example, when $n=2$, the groups could be $\{1,2,4\}$ and $\{3\}$.
Here is a proof, not quite by induction:
Let $S=\{1,2,3,\ldots,2n\}$ and suppose that there exist at least one $(n+1)$-element set $C\subset S$ such that no two elements of $C$ are multiples of each other.
Consider now the smallest element $x\in C$. Since $C$ has $n+1$ elements, we have $x\le n$ -- otherwise there isn't room in $C$ for all the elements it needs.
However then $2x$ is in $S$ but cannot be in $C$. And $x$ is the largest proper divisor of $2x$, so the only divisor of $2x$ that is in $C$ is $x$ itself (remember that $x$ was the smallest element of $C$).
Therefore the set $(C\setminus\{x\})\cup\{2x\}$ is itself a possible $C$, and its smallest element is larger than $x$.
Thus, we can keep doubling the smallest element of $C$ until the smallest element is larger than $n$, which is absurd -- so the original $C$ cannot have existed.
To formalize this proof, one might phrase it as an proof by induction on $h\ge 0$ that for any $h<n$ then theset $$ \{n-h,n-h+1,\ldots,2n-1,2n\} $$ contains no subset of size $n+1$ where no element divides another.
Straightforward induction.
let $S$ be set in question selected from $N$: $S=\{i_1,i_2,i_3,...i_k\}$ integers all $\le 2n, n\in N$, $S_m\subseteq S$ of distinct integers. $|S_m|=n+1$
$1)$base case: $n=1: S=\{1,2\}/\{1,1\}/\{2,2\};S_m=\{1,2\}$; $1|2$
$2)$inductive hypothesis: $\forall_{S_m\subseteq S\wedge |S_m|=n+1}\exists_{c,d\in S_m\wedge c\neq d}c|d$
$3)S_1=\{i_1,i_2,i_3,...i_t\}$ integers all $\le 2(n+1)=2n+2, n\in N$,$S\subseteq S_1$,$S_{m_1}\subseteq S_1$ of distinct integers. $|S_{m_1}|=n+1+1=n+2$
$4)$ We have $3$ different cases here:
$a)(2n+1\notin S_{m_1}\wedge 2n+2\notin S_{m_1})$: $S_m\subseteq S_{m_1}\subseteq S$ and so inductive hypothesis can be applied. $b)(2n+1\in S_{m_1}\wedge 2n+2\notin S_{m_1})\vee (2n+1\notin S_{m_1}\wedge 2n+2\in S_{m_1})$:in these cases inductive hypothesis holds as $n+1$ distinct integers are selected from $S$. $c)2n+1\in S_{m_1}\wedge 2n+2\in S_{m_1}$:In this case there are two possibilities:$1)$if $2$ or $n+1$ selected done, as both divide $2n+2$. $2)$ otherwise $n+1$ can be said to be selected as any other # that divides $2n+2$ must divide $n+1$. smallest element in $S_{m_1}$ must be $\le n+1$/must be $\ge n$ numbers in $S_{m_1}/S$. with $n+1$(number $n+1$ and $n$ others) integers selected from $S$, inductive hypothesis can be applied.
So $\forall_{S_m\subseteq S\wedge |S_m|=n+1}\exists_{c,d\in S_m\wedge c\neq d}c|d\rightarrow \forall_{S_{m_1}\subseteq S_1\wedge |S_{m_1}|=n+2}\exists_{c,d\in S_{m_1}\wedge c\neq d}c|d$
Therefore by the Principal of Mathematical Induction $\forall_{n\in N}[\forall_{S_m\subseteq S}\exists_{c,d\in S_m, c\neq d}c|d]$
