# Prove that for an integer $x \ge 7$, it follows that $x\# > x^2+x$

Is the following argument sufficient to show that for an integer $$x \ge 7, x\# > x^2 + x$$.

Please let me know if I made a mistake or if there is a more straight forward way to make the same argument.

Let:

• $$p_n$$ be the $$n$$th prime
• $$p\#$$ be the primorial for $$p$$

Here's the argument by induction:

(1) Base case: $$p_4=7$$

For $$7 \le x < 14, 7\# = 210 > x^2+x$$ since:

$$7^2 + 7 < 8^2 + 8 < 9^2 + 9 < 10^2 + 10 < 11^2 + 11 < 12^2 + 12 < 13^2 + 13 = 182 < 210$$

(2) Assume up to some prime $$p_n \ge 7$$ that for $$p_n \le x < 2p_n, p_n\# > x^2+x$$.

(3) From Bertrand's Postulate, $$p_n < p_{n+1} < 2p_n$$

(4) $$p_{n+1}\# > p_{n+1}[(2p_n-1)^2 + 2p_n-1] = p_{n+1}(2p_n)^2 - 2p_{n+1}p_n$$

(5) Since $$p_{n+1} \ge 11$$, it follows from Bertrand's Postulate:

$$p_{n+1}(2p_n)^2 - 2p_{n+1}p_n > p_{n+1}(p_{n+1})^2 - 2p_{n+1}p_n > 9(p_{n+1})^2$$

(6) It follows:

$$p_{n+1}\# > (3p_{n+1})^2 > (2p_{n+1})^2 - 2p_{n+1} = (2p_{n+1} - 1)^2 + 2p_{n+1} - 1$$

(7) For any integer $$x \ge 7$$, let $$p_n$$ be the highest prime less than or equal to $$x$$.

(8) If $$x$$ is prime, from the above, $$x\# > x^2 + x$$

(9) If $$x$$ is not prime, from Bertrand's Postulate, it follows:

$$x\# = p_n\# > (2p_n-1)^2 + 2p_n - 1 \ge x^2 + x$$

• You could also use the fact that $p_n\#>p_n^{\lfloor \frac{\theta(p_n)}{\log p_n} \rfloor}$ and use some Dusart bound on $\theta(p_n)$ or use the fact that the exponent is growing with $n$ and is still valid for larger $p_n$ May 30, 2020 at 16:19

As an alternative, let's suppose we've verified the inequality for all integers up to $$24$$ (a simple extension of the OP's argument taking things up to $$13$$, since $$2\cdot3\cdot5\cdot7\cdot11=2310\gt24^2+24$$), and let's invoke Bertrand's Postulate in the equivalent form that for any real number $$u\gt1$$ there is a prime satisfying $$u\lt p\lt2u$$.

This version of BP allows for the following conclusion: If $$x\gt24$$, then there exist prime numbers $$p$$, $$q$$, and $$r$$ such that

$$2\lt3\lt{x\over8}\lt p\lt{x\over4}\lt q\lt{x\over2}\lt r\lt x$$

It follows that

$$\#x\ge6pqr\gt6\cdot{x\over8}\cdot{x\over4}\cdot{x\over2}={3x^3\over32}$$

and it's easy to see that

$${3x^3\over32}\gt x^2+x$$

if $$x\gt24$$ (in fact, if $$x\ge12$$).

What you've done looks correct. However, one small thing to note in your step $$(1)$$ base case, you only need to show $$10^2 + 10 = 110 \lt 210$$ since $$11$$ is prime and, as such, will be handled later by induction as $$p_5$$.

Also, I believe a somewhat simpler way to proceed after your step $$(5)$$ is to then show, for all $$p_{n+1} \le x \lt 2p_{n+1}$$, that

\begin{aligned} p_{n+1}\# & \gt 9p_{n+1}^2 \\ & = 4p_{n+1}^2 + 5p_{n+1}^2 \\ & \gt (2p_{n+1})^2 + 2p_{n+1} \\ & \gt x^2 + x \end{aligned}\tag{1}\label{eq1A}

As you stated in your step $$(3)$$, Bertrand's postulate shows there's a prime $$p_{n+1} \lt p_{n+2} \lt 2p_{n+1}$$. Thus, for all $$p_{n+1} \le x \lt p_{n+2}$$, you have $$x\# = p_{n+1}\#$$, with \eqref{eq1A} showing

$$x\# \gt x^2 + x \tag{2}\label{eq2A}$$