# Thread: An induction problem with primes

1. ## An induction problem with primes

Let $\displaystyle p_{n}$ denote the nth prime. For n>3, show that $\displaystyle p_{n} < \sum ^{n-1}_{1} p_{i}$

My proof so far:

Let $\displaystyle S = \{ n \in N : p_{n} < \sum ^{n-1}_{1} p_{i} , n>3 \}$

Now, 4 is in S because $\displaystyle p_{4}=7 < 2+3+5 =10$

Assume k in S, then $\displaystyle p_{k} < \sum ^{k-1}_{1} p_{i}$

Now, $\displaystyle \sum ^{k}_{1} p_{i} = \sum ^{k-1}_{1} p_{i} + p_{k} < p_{k}+p_{k} = 2p_{k}$

By the Bertrand's postulate, there exist at least one prime number q such that $\displaystyle p_{k} < q < 2p_{k}$

Pick q to be the smallest prime from the set, then $\displaystyle q = p_{k+1} < 2p_{k}$

But now I'm stuck, I'm trying to show that $\displaystyle \sum ^{k}_{1} p_{i} < q$, how do I go about doing that?

2. Do you agree that $\displaystyle p_{n+1} < 2p_n = p_n + p_n$ ---> this is Betrand's conjecture (and it is not easy to prove, but it seems you are allowed to use it)?

Then by induction,
$\displaystyle p_n + p_n < p_1+...+p_{n-1}+p_n$.
Thus, $\displaystyle p_{n+1} < p_1+...+p_{n}$.