prove or disprove $P_{i}\cdot P_{k+1-i}>P_{k+1}$

Solution 1:

Let's prove that for integers $b \geq a\geq 1$, we have $P_aP_b > P_{a+b}$ (this is slightly stronger than the original statement, since it allows for $a=b$).

There are only ten pairs $(a,b)$ with $b<5$ and it's easy to verify that the statement is true for all of them. Thus, from now on, we'll assume $b\geq 5$.

Weakening the bounds from Wikipedia a little, we get the following inequality, valid for $n\geq 5$: $$n\ln n < P_n < 1.37n\ln n$$

Applying the upper bound to $P_{a+b}$ and using the fact $2b \geq a+b$ yields $$b\log (6.7b^{2.74}) > 2.74b\log(2b) \geq 1.37(a+b)\log(a+b) > P_{a+b}$$

The lower bound applied to $P_b$ gives us $$P_aP_b > P_a b\log b=b\log b^{P_a}$$

For $P_a\geq 5$, we have $b^{P_a}\geq b^5>6.7b^{2.74}$, so we can combine the two inequalities to obtain $P_aP_b>P_{a+b}$. The same is true for $P_a=3$ and $b\geq 1504$. The remaining cases with $P_a=3$ and $2\leq b<1504$ can be checked by a computer (or by hand, if you prefer so; it turns out to be quite easy if you have the list of first ~$1500$ primes by hand).

Finally, $P_a=2$ corresponds to Bertrand's postulate, $2P_b > P_{b+1}$. Q.E.D.

Solution 2:

Given $n$, we have $P_n\gt n\ln n$ (since $n \tilde~ \dfrac {P_n}{\ln(P_n)}$, note the prime counting function) but also $\pi(P_n)=n$. Therefore

$$P_kP_m \gt km\ln k\ln m\\ \pi(P_{k+m})=k+m$$

For all $k,m \ge 2, km \ge k+m.$ For all $n\ge 3, \ln n \ge 1.$ So we have

$$\pi(P_kP_m)\gt \pi(km\ln k\ln m)\gt \pi(km) \ge \frac {km}{\ln k+\ln m}~R~~k+m$$

or

$$km~R~~(k+m)(\ln k+\ln m)$$

If either $k$ or $m$ is increased while the other remains constant, this relation eventually becomes $\lt$ just as $\forall k,\exists m:k\le \ln m$. But if $k=m$ we have

$$k^2~R~~4k\ln k\\ k~R~~4\ln k$$

It doesn't take very long for $k\gt 4\ln k$ and it is certainly true for $k\ge 16$, therefore $P_k^2\gt P_{2k}$ for $k$ "large enough" and we only need to check $P_k:1\le k\le 16.$ By a similar argument, it is possible to get $P_kP_k+1\gt P_{2k+1}.$

Assuming that both of these hold, and taking Bertrand's Postulate, we have a "square induction" over both $i, k$ for the proof that

$$P_iP_{i+k-1} \gt P_{2i+k-1}$$

where $1\le i, 1\le k$.

In particular, Bertrand's Postulate provides the base case as $P_1P_{1+k-1}\gt P_{2+k-1},$ and for each $i$ we have the base case $P_iP_{i+1-1}\gt P_{2i+1-1}.$ So assume that for $i=n,\forall k,$

$$P_iP_{i+k-1}=P_nP_{n+k-1}\gt P_{i+k-1}=P_{n+k-1}$$

and it is necessary to prove this statement for $i=n+1.$ The base case is

$$P_{n+1}P_{n+1}\gt P_{2n+2}$$

and assume it is true for $k=m,$

$$P_{n+1}P_{n+1+m-1}\gt P_{2n+1+m}$$

So now we try $k=m+1$ which means that we must prove

$$P_{n+1}P_{n+1+m}\gt P_{2n+2+m}\tag 1$$

Using this answer we have Pierre Dusart's statement that there is always a prime in the interval $\left[x+1, x+\dfrac x{1+2\log^2 x}\right).$ Again, there are a finite number of cases to check (Dusart's statement requires $x\gt 3275$). Taking apart the larger endpoint, we have

$$\frac x{1+2\log^2 x}\le \frac x{2\log^2 x}=\frac 1{2\log x}\cdot \frac x{\log x}\le \frac {\pi(x)}{2\log x}\le \frac {\pi(x)}2$$

Considering $(1),$ we have

$$P_{n+1}P_{n+1+m}\ge (P_n+1)P_{n+1+m}=P_nP_{n+1+m}+P_{n+1+m}\gt P_{2n+1+m}+P_{n+1+m}$$

By the modification to Dusart's interval, we have that

$$P_{2n+2+m}\in \left[P_{2n+1+m},P_{2n+1+m}+\frac{\pi\left(P_{2n+1+m}\right)}2\right]\subseteq\left[P_{2n+1+m},P_{2n+1+m}+\frac{2n+1+m}2\right]$$

and since $\dfrac{2n+1+m}2\le n+1+m\lt P_{n+1+m},$ we have shown that

$$P_{n+1}P_{n+1+m}\gt P_{2n+1+m}+P_{n+1+m}\gt P_{2n+1+m}+n+1+m\gt P_{2n+2+m}$$