- #1
mlsbbe
- 24
- 0
Hi, I am having trouble understanding this proof.
Statement
If pn is the nth prime number, then pn [tex]\leq[/tex] 22n-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
pn+1 [tex]\leq[/tex] p1p2...pn + 1
pn+1 [tex]\leq[/tex] 2.22...22n-1 + 1 = 21 + 2 + 22+ ...+ 2n-1
Recalling the indentity 1 + 2 +22+ ...+2n-1=2n-1
Hence
pn+1 [tex]\leq[/tex] 22n-1+1
But 1 [tex]\leq[/tex] 22n-1 for all n; whence
pn+1 [tex]\leq[/tex]22n-1+22n-1
=2.22n-1
=22n
completing the induction step, and the argument.
What I don't understand is why the proof uses p1, p2, etc as powers of two. What is the nature of the pn? Are they prime or what? Why use powers?
Statement
If pn is the nth prime number, then pn [tex]\leq[/tex] 22n-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
pn+1 [tex]\leq[/tex] p1p2...pn + 1
pn+1 [tex]\leq[/tex] 2.22...22n-1 + 1 = 21 + 2 + 22+ ...+ 2n-1
Recalling the indentity 1 + 2 +22+ ...+2n-1=2n-1
Hence
pn+1 [tex]\leq[/tex] 22n-1+1
But 1 [tex]\leq[/tex] 22n-1 for all n; whence
pn+1 [tex]\leq[/tex]22n-1+22n-1
=2.22n-1
=22n
completing the induction step, and the argument.
What I don't understand is why the proof uses p1, p2, etc as powers of two. What is the nature of the pn? Are they prime or what? Why use powers?