4
$\begingroup$

So, there is an excersise in my textbook:

Prove by induction

If $ P_n $ is n-th prime number and $ n\geqslant 12 $, than: $$P_n>3n$$

My approach:

1.For $n={12}:\quad P_{12}=37>3*12=36$

2.Inductive step:$\quad P_{n+1}>3n+3$

3.I figured out that:$\quad P_{n+1}-P_n\geqslant 2$

I got stuck, so i decided to go check answers: $$P_{n+1}\geqslant P_n+2>3n+2\geqslant 3n+3$$

That last part seems very wrong to me, and i do not think this is valid proof.I don't really know what to do next.

$\endgroup$
2
  • $\begingroup$ The proof is wrong? Because statement that $P_{n+1}-P_n \geqslant 2$ is correct, for example 19-17 $\endgroup$
    – 1qwertyyyy
    Dec 11, 2019 at 18:29
  • $\begingroup$ Proving the fact $P_{n+1}-P_n\ge 3$ would be enough for the inductive step. However, this is far from trivial. The reason is that the twin prime conjecture is still open, we still do not know if there are infinitely many pairs of primes that differ by 2. I would try some other way. $\endgroup$
    – GReyes
    Dec 11, 2019 at 18:35

2 Answers 2

Reset to default
4
$\begingroup$

The way the chain of inequalities is written is wrong. Apparently, it should be$$P_{n+1}\ge P_{n}+2>3n+2\\\implies P_{n+1}\ge3n+3$$Now you should use the fact that $3\mid3n+3$ but $3\nmid P_{n+1}\ne3$. So $P_{n+1}\ne3n+3$.

$\endgroup$
3
  • $\begingroup$ @1qwertyyy Note that this result doesn't say anything about the difference $P_{n+1}-P_n$ except that it is $\ge2$. We assumed $P_n>3n$ (not $P_n=3n$) in the inductive hypothesis. The next prime may exceed $P_n$ by $2$, but in that case $P_n\ne3n+1$ and so $P_n>3n+1$. The next prime may exceed $P_n$ by any other number $>2$. $\endgroup$
    – Shubham Johri
    Dec 11, 2019 at 18:47
  • $\begingroup$ The first line proves $P_{n+1}$ is absolutely greater than $3n+2$, so the smallest it can be is $3n+3$ But it cannot be $3n+3$ itself, as that number is not prime, having $3$ as a factor. $\endgroup$
    – Keith Backman
    Dec 11, 2019 at 18:48
  • $\begingroup$ Oh yes, now it is clear, thank you. $\endgroup$
    – 1qwertyyyy
    Dec 11, 2019 at 18:53
0
$\begingroup$

Here is an alternate approach using induction twice. Note all primes $\gt 3$ are congruent to either $1$ or $5$ modulo $6$. Thus, for all $n \gt 2$, the difference between $p_n$ and $p_{n+2}$ is at least $6 = 3 \times 2$. As such, you can use induction to prove the statement of

$$p_{n} \gt 3n \tag{1}\label{eq1A}$$

is true for all odd index primes (i.e, for $n = 2m+1$, you have $p_{2m+1} \gt 3(2m+1)$), and then also use it to prove it's true for all even index primes (i.e, for $n = 2m$, you have $p_{2m} \gt 3(2m)$), for all $n \ge 12$ in both cases. I'll leave it to you to do the rest yourself.

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.