Demonstrate by induction

Question

Let $p,q \in \mathbb{N}$, be prime among them and $p<q$.

Proposition : $\exists{n} \in \mathbb{N}\;|\; \frac{1}{n+1} \le \frac{p}{q} < \frac{1}{n}$

Demonstration :

And I'm stuck there!

Can you help me?

The statment isn't "for every $n$, this inequality holds" it is "there exists $n$ so that this inequality holds". Indeed, for $p = 1$, $q = 3$, your statement $P(1)$ is false (since $p/q < 1/2$). Thus, induction on $n$ isn't going to work. What you are trying to prove is that, given $p/q$, you have $p/q$ in $[1/2,1)$, or $[1/3,1/2)$ or $[1/4,1/3)$ or $[1/5,1/4)$, etc. — BaronVT, Jan 16 '15 at 20:04
I don't understand. In my mind, because the statement is "there exists" and not "for every", we can say $P(1)$ it's true when $p=2$ and $q=3$!? — hlapointe, Jan 16 '15 at 20:09
Here's a "normal" case of induction: "for every $n$, $\sum_{k = 1}^n k = n(n+1)/2$". In this case, the statement $P(n)$ could be "$\sum_{k = 1}^n k = n(n+1)/2$"; you would show $P(1)$ is true, and that $P(n)$ being true implies $P(n+1)$ is true. This would demonstrate that, for every $n$, $P(n)$ is true. — BaronVT, Jan 16 '15 at 20:14
If it's not by induction, how can I demonstrate this proposition. — hlapointe, Jan 16 '15 at 20:15
Induction doesn't seem to be useful for this proof. It's not that hard to simply construct n given p and q — Joffan, Jan 16 '15 at 20:15
In this case, given a specific $p,q$, it will not be the case that $P(n)$ is true for every $n$. For example, if $p = 2, q = 3$ then $P(1)$ is true as you point out, but $P(2)$ is not (and general $P(n)$ will be false too). For a different choice of $p, q$, a different $P(n)$ will be true. For example, if $p = 1, q = 3$, then $P(1)$ is false, $P(2)$ is true, the others are false. — BaronVT, Jan 16 '15 at 20:16
@hlapointe Try to do a specific example in careful steps, and then adapt that process to work out the details for a general case. If I give you $p = 3, q = 5$, then for what $n$ is the inequality true? What if $p = 2, q = 5$? — BaronVT, Jan 16 '15 at 20:17
Well, I don't know, you didn't tell me what steps you took to work out the specific cases. — BaronVT, Jan 16 '15 at 20:19
or try p=7, q=1999 - something you can't do just by inspection. — Joffan, Jan 16 '15 at 20:19
Once I'll have my specific case, i.e. $p=2$, $q=3$ and $n=1$, how can I transform the steps for make this case general? — hlapointe, Jan 16 '15 at 20:21
Work out a method for the harder case and see if the steps still work for the simple case. — Joffan, Jan 16 '15 at 20:22
Can you write an answer, because I'm not sure that I really understand your explanations. — hlapointe, Jan 16 '15 at 20:22

score 0 · Answer 1 · answered Jan 16 '15 at 20:32

Hint: Start with a concrete example, $p = 7, q = 1999$. Note that $q = 285p + 4$ so

$$ \dfrac{p}{q} = \dfrac{7}{285\cdot 7 + 4} $$

and so, since $$q - 4 \leq q \leq q + 3,$$ you have $$285 \cdot 7 + 4 - 4 \leq q \leq 285\cdot 7 + 4 + 3$$ and thus

$$ \dfrac{7}{285\cdot 7 + 7} \leq \dfrac{p}{q} \leq \dfrac{7}{285 \cdot 7}. $$

What does $n$ need to be in this case?

Now adapt to a general $p,q$.

Demonstrate by induction

1 Answers1