Show that if $p_k$ is the $k$th prime, where $k$ is a positive integer, then $p_n\leq p_1\cdot p_2\cdot ...\cdot p_{n-1}+1$ for all integers $n$ with $n\geq3$.

I need ideas on how to tackle this.

Question

Show that if $p_k$ is the $k$th prime, where $k$ is a positive integer, then $p_n\leq p_1\cdot p_2\cdot ...\cdot p_{n-1}+1$ for all integers $n$ with $n\geq3$.

I need ideas on how to tackle this.

jamesj · Answer

By induction.  Let P(n) be the statement you have above.

First observe that P(3) is true, as
$$ p_3 = 5 \leq 7 = 2 \cdot 3 + 1 = p_1p_2 + 1 $$

anonymous · Answer

the number on the right throws a remainder of 1 when divide by the first n - 1 primes, and so if it is the next prime you are done, (because of 
$$\leq$$ and if it is not the next prime then it is composite and therefore divisible by some prime number, but not one of the n - 1 primes listed

jamesj · Answer

Actually, that's better

anonymous · Answer

I'm a little confused: it seems I'm supposed to use induction starting at $n=3$. Doesn't this mean that I can't really use analytical methods to prove this? :/

jamesj · Answer

There's nothing with sat73's argument.  The induction argument--or at least the version of it I know--hinges on something else which is even deeper and harder.

In the induction step: we want to show for k greater than or equal to 3 that 
P(k) => P(k+1)

Suppose this is not the case: that P(k) and not P(k+1).

Not P(k+1) implied
$$ p_{k+1} > p_1 ... p_k + 1 $$
$$ = p_k ( p_1 ... p_{k-1} + 1/p_k) $$
$$ \geq p_k(p_k -1) + 1/p_k \ \ \ \text{ by P(k) } $$
$$ \geq p_k(p_k -1) $$

Now, it seems very plausible that this is false; i.e., 

$ p_{k+1} > p_k(p_k -1) $ is false for all $ k \geq 3 $ 

But proving that rigorously is much, much harder than the result we were first asked to prove.  So instead, use sat73's proof.

jamesj · Answer

**Not P(k+1) implies [not implieD]

anonymous · Answer

I see. :/

So, what Satellite is saying is that if $p_1...p_{n-1}+1=N$ is the next prime, $p_n$, then we are done because of the equality, and that if it is not, then it must be a composite number larger than $p_n$ because it is not divisible by any of the listed primes and, because of the fundamental theorem of arithmetic, we know that $N$ has a unique prime factorization, which clearly has a prime that we have not listed.

If my train of thought is on track, then I do not understand what this has anything to do with the RHS having a remainder of $1$ after dividing it by $p_1...p_{n-1}$.