2

Prove by induction that $P_{n}<2^{2^n}$, been $P_n$ the $n^\text{th}$ prime number

The prime numbers´s set is defined as $\mathbb P:= \left \{2,3,5,7,11,\ldots\right\} $

Let $P(n)$ be the proposition we want to prov, ie: $P(n):=P_n<2^{2^n}$

For $P(1)$ we have the first prime number, ie, 2 so $2<2^{2^1} \implies 2<4 $, so $P(1)$ is true.

For $P(2)$ we have the second prime number, ie, 3 so $2<2^{2^2} \implies 3<16 $, so $P(2)$ is true.

Inductive Hypothesis: Let $n=k$ and we assume that $$P(k):=P_n<2^{2^n}$$ is true.

I dont know how to do the inductive step, how it should be done?

Victor F Salazar G
  • 1,297

2 Answers2

6

Using Euclid's argument:

Let $\mu = 2 ^{2^{n+1}}$

$$ P_{n+1} \le P_1 P_2 \cdots P_n + 1 < 2^{2^1} 2 ^{2^2} \cdots 2^{2^n} + 1 = 2^{\left(2^1+2^2+2^3\cdots 2^n\right)} + 1 \\= 2 ^{\left(2^{n+1}-1\right)} +1 = \mu /2 + 1 \le \mu/2+\mu/2 = \mu $$ This is the induction step.

Anant
  • 520
user44197
  • 9,730
  • 1
    I think the second line should read $2^{(2^{n+1}-\color{#000080}{2})} + 1 = \mu / 4 + 1 < \mu$ – Anant Mar 22 '14 at 21:09
2

Hint: Use Bertrand's postulate. Applied to this situation, the postulate says that there is always a prime between $P_n$ and $2P_n$. (Thus, you just have to show that $2^{2^{n+1}} > 2P_n$)

Edit: If need be, I can provide more detail to the proof. Just leave a comment.

apnorton
  • 17,706
  • 1
    Isn't Bertrand's postulate a bit too much for this? – Pedro Jan 10 '14 at 02:10
  • @PedroTamaroff It was the first/easiest thing that came to my mind. I don't know when Bertrand is introduced in standard pedagogy, because I've never had a "real" proofs/number theory class (just a "Mathematical Structures" class that briefly covered proofs, set theory, really basic number theory, and logic in one semester). It probably is overkill, but it's effective. ;) – apnorton Jan 10 '14 at 02:13
  • 1
    @anorton Even though I think my answer is simpler ( :) ) I am all for anyone bringing in Bertrand's theorem. I suggest you look at the proof for it simplicity and elegance. – user44197 Jan 10 '14 at 02:41
  • @user44197 Just looked it up--that was very awesome. (And to future readers--I suggest the same! ;) ) – apnorton Jan 10 '14 at 02:44