8
$\begingroup$

How do you show that, if $p_n$ denotes the $n$th prime, $n > 3$, then

$$p_n < p_1 + p_2 +\cdots + p_{n-1}$$

using the Bertrand conjecture and induction?

Here is what I've come up with, but I'm not sure if it's correct:

Let $n=4$. Then, $p_4 = 7$, so we have:

$$7 < 2+3+5 = 10.$$

Assume that the statement is true for $n$ so that $p_n < p_1 + p_2 +\cdots + p_{n-1}$.

We want to prove that this is true for $n+1$.

$$p_{n+1} < p_1 + p_2 +\dotsc + p_{n-1} + p_n.$$

But we assumed that $p_n < p_1 + p_2 +\cdots + p_{n-1}$, so we have:

$$p_{n+1} < p_1 + p_2 +\cdots + p_{n-1} + p_n < p_n + p_n = 2p_n.$$

We know that $p_n < p_{n+1}$, so we have:

$p_n < p_{n+1} < 2p_n$, which is true by the Bertrand conjecture. $\blacksquare$

$\endgroup$
  • 1
    $\begingroup$ You have a good idea about relating this problem to Bertrand's "postulate", but you get some steps out of order toward the end of your argument. Go through the next to last line a little slower, and keep in mind that you know $p_{n+1} \lt 2 p_n $, and are trying to prove $p_{n+1} \lt p_1 + \ldots +p_n $. $\endgroup$ – hardmath Sep 25 '15 at 18:41
3
$\begingroup$

You seem to have the right basic idea, but where you wrote

$$p_{n+1} < p_1 + p_2 +\dotsc + p_{n-1} + p_n < p_n + p_n = 2p_n$$

the second inequality is wrong. It would be better to first invoke Bertrand's postulate to establish $p_{n+1}\lt 2p_n$ and then apply the inductive hypothesis to get

$$p_{n+1}\lt2p_n=p_n+p_n\lt p_1+p_2+\cdots+p_{n-1}+p_n$$

$\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.