Use induction and the Bertrand conjecture to show that....

[Math100]

Homework Statement

Let $p_{n}$ denote the nth prime. For $n>3$, show that $p_{n}<p_{1}+p_{2}+\dotsb +p_{n-1}$. [Hint: Use induction and the Bertrand conjecture.]

Relevant Equations

None.

Proof:

The proof is by induction.
(1) When $n=4$, the statement is $p_{4}<p_{1}+p_{2}+\dotsb +p_{3}$,
which is true, because $7<10$.
(2) Now assume $n=k+1$.
Then $p_{k+1}<p_{1}+p_{2}+\dotsb +p_{k+1-1}\implies p_{k+1}<p_{1}+p_{2}+\dotsb +p_{k}$.
Thus $p_{k}<p_{1}+p_{2}+\dotsb +p_{k-1}$.
Applying Bertrand's conjecture produces:
$p_{k+1}<p_{1}+p_{2}+\dotsb +p_{k-1}+p_{k}\implies p_{k+1}<p_{k}+p_{k}=2p_{k}$.
Thus $p_{k+1}<2p_{k}$.
Therefore, $p_{n}<p_{1}+p_{2}+\dotsb +p_{n-1}$ for $n>3$.

 

[Mark44]

Homework Statement:: Let $p_{n}$ denote the nth prime. For $n>3$, show that $p_{n}<p_{1}+p_{2}+\dotsb +p_{n-1}$. [Hint: Use induction and the Bertrand conjecture.]
Relevant Equations:: None.

Proof:

The proof is by induction.
(1) When $n=4$, the statement is $p_{4}<p_{1}+p_{2}+\dotsb +p_{3}$,
which is true, because $7<10$.
(2) Now assume $n=k+1$.

That's not how induction works. The statement P(n) is $p_n < p_1 + p_2 + \dots + p_{n-1}$
1) Establish that the statement is true for some base case, usually P(1). You have done this for P(4), which is fine.
2) Assume that the statement is true for n = k. IOW, Assume that $p_k < p_1 + p_2 + \dots + p_{k-1}$ is true.
3) Show that P(k) being true implies that P(k + 1) must also be true. IOW, show that $p_k < p_1 + p_2 + \dots + p_{k-1} \Rightarrow p_{k+1} < p_1 + p_2 + \dots + p_{k-1} + p_k$.

Then $p_{k+1}<p_{1}+p_{2}+\dotsb +p_{k+1-1}\implies p_{k+1}<p_{1}+p_{2}+\dotsb +p_{k}$.
Thus $p_{k}<p_{1}+p_{2}+\dotsb +p_{k-1}$.

You have it exactly backwards. Your "thus" statement is what you should have assumed. I recommend that you find a good reference that shows how induction proofs work, and gives some examples.

Applying Bertrand's conjecture produces:
$p_{k+1}<p_{1}+p_{2}+\dotsb +p_{k-1}+p_{k}\implies p_{k+1}<p_{k}+p_{k}=2p_{k}$.
Thus $p_{k+1}<2p_{k}$.
Therefore, $p_{n}<p_{1}+p_{2}+\dotsb +p_{n-1}$ for $n>3$.

 

[Mark44]

Thread temporarily closed for mentor discussion.

 

[fresh_42]

Thread re-opened.

@Math100 please consider @Mark44 's advice in post #2.

The structure of a proof of a statement $S(n)$ that depends on an integer $n$ by induction is:
a) Prove $S(n_0)$ for a certain $n_0.$ We have $n_0=4$ above.
b) Prove $S(n+1)$. In order to prove this, we are allowed to use all previous statements $S(n_0),S(n_0+1),\ldots,S(n).$

 

[Math100]

Revised proof:

The proof is by induction.
(1) When $n=4$, the statement is $p_{4}<p_{1}+p_{2}+\dotsb +p_{3}$,
which is true, because $7<10$.
(2) Now assume the statement is true for some integer $n=k>3$,
that is assume $p_{k}<p_{1}+p_{2}+\dotsb +p_{k-1}$.
Next we show that the statement for $n=k+1$ is true.
Observe that $p_{k}<p_{1}+p_{2}+\dotsb +p_{k-1}\implies p_{k+1}<p_{1}+p_{2}+\dotsb +p_{k-1}+p_{k}$.
Applying the Bertrand's conjecture produces:
$p_{k+1}<p_{1}+p_{2}+\dotsb +p_{k-1}+p_{k}\implies p_{k+1}<p_{k}+p_{k}=2p_{k}$.
Thus $p_{k+1}<2p_{k}$.
This completes the proof by induction and the Bertrand conjecture.
Therefore, $p_{n}<p_{1}+p_{2}+\dotsb +p_{n-1}$ for $n>3$.

 

[fresh_42]

Revised proof:

Let's see what you have.

For the record, since it is nowhere mentioned: The Bertrand-Chebychev theorem says that there is always at least one prime between $n$ and $2n.$

Another formulation that fits better with our statement is: $p_{n+1}<2p_n$.

The proof is by induction.

The statement reads:
$S(n)\, : \,p_n<p_1+\ldots+p_{n-1}$
where $p_n$ denotes the $n$-th prime.

(1) When $n=4$, the statement is $p_{4}<p_{1}+p_{2}+\dotsb +p_{3}$,
which is true, because $7<10$.
(2) Now assume the statement is true for some integer $n=k>3$,
that is assume $p_{k}<p_{1}+p_{2}+\dotsb +p_{k-1}$.

You do not need two parameters for the same count. Let's forget about $n$ and assume $S(k)$ is true. Then we have to check $S(k+1)$.

Next we show that the statement for $n=k+1$ is true.
Observe that $p_{k}<p_{1}+p_{2}+\dotsb +p_{k-1}\implies p_{k+1}<p_{1}+p_{2}+\dotsb +p_{k-1}+p_{k}$.

Why that? How?

We have to prove a certain upper bound for $p_{k+1}.$ Since we are allowed to use the theorem above, we know that $p_{k+1}<2p_k=p_k+p_k.$

Now comes the induction hypothesis. Can you go on from here?

Applying the Bertrand's conjecture produces:
$p_{k+1}<p_{1}+p_{2}+\dotsb +p_{k-1}+p_{k}\implies p_{k+1}<p_{k}+p_{k}=2p_{k}$.
Thus $p_{k+1}<2p_{k}$.
This completes the proof by induction and the Bertrand conjecture.
Therefore, $p_{n}<p_{1}+p_{2}+\dotsb +p_{n-1}$ for $n>3$.

 

[Math100]

Let's see what you have.

For the record, since it is nowhere mentioned: The Bertrand-Chebychev theorem says that there is always at least one prime between $n$ and $2n.$

Another formulation that fits better with our statement is: $p_{n+1}<2p_n$.The statement reads:
$S(n)\, : \,p_n<p_1+\ldots+p_{n-1}$
where $p_n$ denotes the $n$-th prime.
You do not need two parameters for the same count. Let's forget about $n$ and assume $S(k)$ is true. Then we have to check $S(k+1)$.

Why that? How?

We have to prove a certain upper bound for $p_{k+1}.$ Since we are allowed to use the theorem above, we know that $p_{k+1}<2p_k=p_k+p_k.$

Now comes the induction hypothesis. Can you go on from here?

What's the induction hypothesis? And how to prove a certain upper bound for $p_{k+1}$?

 

[fresh_42]

What's the induction hypothesis? And how to prove a certain upper bound for $p_{k+1}$?

$p_{k+1}<p_1+\ldots+p_k$ is what we have to show. We have to derive it. Your mistake was, that you used it. We cannot use what we want to prove. So our goal is something along the lines
$$
p_{k+1}<\ldots < \ldots < \ldots < p_1+\ldots+p_k
$$

A proof by induction goes this way: Find a number for which the statement is true. This is the induction base and in our case: $n_0=4.$

Now, if we can find a way to prove it for $n=5$ with the knowledge, that it is true for $n=4,$ which we already showed, then we have it for the next number. Now, if we can find a way to prove it for $n=6$ with the knowledge, that it is true for $n=5,$ which we just showed, then we have it for the next number. Now, if we can find a way to prove it for $n=6$ with the knowledge, that it is true for $n=5,$ which we already showed, then we have it for the next number. This can go on forever. But where to stop? The solution is, that we pretend we have shown it for some number $n=k$. Now, if we can find a way to prove it for $n=k+1$ with the knowledge, that it is true for $n=k,$ which we already showed - ok, we pretend we did - then we have it for the next number.

That's how a proof by induction goes.
Prove $S(n_0).$ (induction base)
Pretend $S(k)$ is true. (induction hypothesis)
Prove $S(k+1)$ is true by using the previous result $S(k)$. (induction step)

In our case, we have already checked $S(4).$ Now we need $S(k+1),$ that is $p_{k+1}<p_1+\ldots+p_k$.

To prove something, we need some truth from which we can derive our desired statement. The tools, these truths, are in our case the induction hypothesis $S(k),$ which is $p_{k}<p_1+\ldots+p_{k-1}$ and the Bertrand-Chebychev theorem $p_{k+1}<2p_k.$

We start with $p_{k+1}$ and want to end up with $< p_1+\ldots+p_k.$

So let's do it:
\begin{align*}
p_{k+1} &< 2p_k \quad\text{ Bertrand }\\
&=p_k+p_k\\
&<p_k+ (p_1+\ldots+p_{k-1} )\quad\text{ induction hypothesis }S(k)\\
&=p_1+\ldots+p_k
\end{align*}

That had to be shown. We started with $p_{k+1}$ and made it bigger and bigger and ended up with $p_1+\ldots+p_{k}.$

This is formally a proof by induction. The and so on, if you like:
\begin{align*}
p_4&=7<10=2+3+5=p_1+p_2+p_3\\
p_5&<2p_4=p_4+p_4<(p_1+p_2+p_3)+p_4\\
p_6&<2p_5=p_5+p_5<(p_1+p_2+p_3+p_4)+p_5\\
p_7&<2p_6=p_6+p_6<(p_1+p_2+p_3+p_4+p_5)+p_6\\
&\text{ and so on }
\end{align*}
Instead of and so on, we formalize one general step $S(k)\Longrightarrow S(k+1).$ Since $k$ can be any number, we do not have to repeat the whole procedure again and again. We have shown it once and for all instead of and so on.

That is the idea. You cannot use what you want to prove. It must be at the end of reasoning, not at the beginning and not in the middle. It is the very last statement of a proof.

 

[Math100]

Thank you.

 

[fresh_42]

Thank you.

You're welcome.

 

[Prof B]

Some tips on induction and proofs in general. Let's say your base case is n=4 for concreteness. You start by proving S(n) when n=4, i.e., you prove the base case S(4). Having dealth with n=4, you next assume n>4 and prove S(n-1) -> S(n). Trust me. I do this stuff for a living. The Derivation Theorem say that if you want to prove an implication you can just assume the left side and prove the right side. So you
assume p_n-1 < p₁ + ... + p_n-2 (this is called the induction hypothesis)
Now you need to prove S(n). When you want to prove an equation or an inequality always start with the more complicated side, i.e., p₁ + ... + p_n-1. If the complicated side is the right side, and it usually is, this approach will flip the inequality in the other direction. The advantage of this approach is that each step of the proof is a simplification instead of a complication.
p₁ + ... + p_n-1 = p₁ + ... + p_n-2 + p_n-1 because n>1
> p_n-1 + p_n-1 by the induction hypothesis
= 2p_n-1
> p_n (why?)
Thus we have proved S(n) (using the assumption S(n-1)). By the Derivation Theorem that proves S(n-1) -> S(n). Since n was an arbitrary number > 4 that proves (for all n > 4)(S(n-1) -> S(n)). Since we also proved S(4) the principle of induction implies (for all n >= 4)S(n).