I am trying to solve the below problem without using induction.
Consider a set of $n+1$ positive integers, each less than or equal to $2n$. Show there must always exist a pair of integers in the set, one dividing the other.
Here is my attempt. I'm trying to "shortcut" the proof somewhat by invoking the fundamental theorem of arithmetic, which I believe to be valid.
Let $S = \{s_1, \ldots, s_{n+1}\}$ be the set of $n+1$ positive integers. By the fundamental theorem of arithmetic, we can write each $s_i = 2^{a_i} \cdot (2b_i - 1)$, uniquely, where $a_i \geq 0$, $b_i >0$. Notice that each element of $s$ is less than or equal to $2n$, and there are exactly $n$ odd numbers less than or equal to $2n$. By the pigeonhole principle, there exists $k \neq j$ such that $2b_k - 1 = 2b_j - 1$. Without loss of generality, suppose $a_k > a_j$. (If $a_k = a_j$, then $s_k = s_j$, which contradicts the fact that $S$ contains $n+1$ distinct elements.) Then $2^{a_k} (2b_k - 1) > 2^{a_j} (2b_j - 1)$. In particular, $$ 2^{a_j} (2b_j - 1) \cdot 2^{a_k - a_j} = 2^{a_k} (2b_j - 1) = 2a^k (2b_k - 1), $$ that is, $$ s_j \cdot 2^{a_k - a_k} = s_k, $$ so $s_j \mid s_k$.