Hi, I am having trouble understanding this proof.(adsbygoogle = window.adsbygoogle || []).push({});

Statement

If p^{n}is the nth prime number, then p_{n}[tex]\leq[/tex] 2^{2n-1}

Proof:

Let us proceed by induction on n, the asserted inequality being clearly true when n=1. As the hypothesis of the induction, we assume n>1 and the result holds for all integers up to n.

Then

p_{n+1}[tex]\leq[/tex] p_{1}p_{2}...p_{n}+ 1

p_{n+1}[tex]\leq[/tex] 2.2^{2}...2^{2n-1}+ 1 = 2^{1 + 2 + 22+ ...+ 2n-1}

Recalling the indentity 1 + 2 +2^{2}+ ...+2^{n-1}=2^{n}-1

Hence

p_{n+1}[tex]\leq[/tex] 2^{2n-1}+1

But 1 [tex]\leq[/tex] 2^{2n-1}for all n; whence

p_{n+1}[tex]\leq[/tex]2^{2n-1}+2^{2n-1}

=2.2^{2n-1}

=2^{2n}

completing the induction step, and the argument.

What I don't understand is why the proof uses p_{1}, p_{2}, etc as powers of two. What is the nature of the p_{n}? Are they prime or what? Why use powers?

**Physics Forums | Science Articles, Homework Help, Discussion**

Join Physics Forums Today!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

# Euclid's Proof

**Physics Forums | Science Articles, Homework Help, Discussion**