0
$\begingroup$

Statement

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.

It's clear that the set can't contain two equal integers because one divides the other.

Basis step:

When n=1 the set S has two positive integers, namely S = {1,2}, and 1 divides 2.

Inductive step

Let's assume that when a set S has K+1 positive integers and each one is not greater than 2K, there is at least one integer in this set that divides another integer in the set.

Now I'm stuck, I don't know how to show that assuming this hypothesis I can prove that the statement holds for (K+1)+1.

$\endgroup$
  • 1
    $\begingroup$ In general your question will be better received if you show some effort beyond simply stating the problem. For example, what have you tried? Is there somewhere specific that you are stuck at? You might say something like "I know induction is..., but I can't seem to prove ..." or "I tried doing it for n=..." $\endgroup$ – Kitter Catter Jan 27 '17 at 19:42
  • $\begingroup$ Yes, you're right, sorry for that. $\endgroup$ – Antonio González Borrego Jan 27 '17 at 19:47
  • $\begingroup$ So I notice that in the $K+1$ step you essentially either have the pair that fulfills the requirement or you must include $2K+1$ and $2K+2$ perhaps there is something in that direction? $\endgroup$ – Kitter Catter Jan 27 '17 at 21:19
  • $\begingroup$ Well, I really look at the notebook, but I can't see anything. $\endgroup$ – Antonio González Borrego Jan 28 '17 at 0:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.