3
$\begingroup$

prove that $p_{n+1}\leq(2^{2^n}+1)$.where $p_{n+1}$ is $(n+1)^\text{th}$ prime.

i am doing it using induction. for $n=1$, it is true. let true for $n.$

now we want to show that $p_{n+2}\leq{2^{2^{n+1}}}+1.$ here i am using the fact that for given natural number $n$, there exist a prime between $n$ and $2n$. using this result for $n=p_{n+1}$, we get $p_{n+2}\leq2p_{n+1.}$

now using induction our result follow.

is there any more elementary method to prove this, mean without using that result from number theory

$\endgroup$
3
$\begingroup$

The proof will be by strong induction.

Notice it hold for $n=0$ since $p_1=2\leq 2^{2^0}+1$

Now notice $p_{n+1}\leq p_1p_2\dots p_n+1\leq \color{red}{(2^{2^{0}}+1)(2^{2^{1}}+1)\cdots (2^{2^{n-1}}+1)}+1$

When we expand this product we get $\color{red}{1+2+2^2+\cdots + 2^{2^{2^{n}-1}}}+1=\color{red}{2^{2^n}-1}+1$

$\endgroup$
  • $\begingroup$ can you please explain why when we expand product we get this GP? $\endgroup$ – Eklavya Jul 30 '16 at 15:56
  • $\begingroup$ I think of it in binary, there are $2^n$ summands when you expand that product, and each one is a different number in binary. The idea is that every factor represents a "bit". I hope it helps, you can also prove it by induction. $\endgroup$ – Jorge Fernández Hidalgo Jul 30 '16 at 16:00
  • $\begingroup$ Which combination give you the summand $2^{17}$?? notice $17=2^{2^4}+2^1$. So the summand $2^{17} $ comes from $2^{2^0}\times 1 \times 1 \times 2^{2^4}\times 1 \times 1\times 1 \dots $ $\endgroup$ – Jorge Fernández Hidalgo Jul 30 '16 at 16:03
0
$\begingroup$

Use the Bertrand's Postulate and the problem is trivial by induction. As for $n=1$ the claim is true, assume it holds for some $k \in \mathbb{N}$. Then using the weaker form of the Postulate we have that there exist a prime between $2^{2^k}-1$ and $2(2^{2^k}-1) - 1$. Obviously we have that $2(2^{2^k}-1) - 1 = 2^{2^k + 1} - 1 \le 2^{2^{k+1}} - 1$. So we have that $p_{k+2} \le q \le 2^{2^{k+1}} - 1$. Hence the proof.

NOTE: $q$ is the prime, whose existence is guaranteed by Bertrand's Postulate, which is either equal to $p_{k+2}$ or greater than it.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.