# Why does $x!$ grow faster than $(x/2)^{(x/2)}$ but slower than $x^x$?

I'm having trouble understanding this.

I understand the reasoning about why $$x!$$ grows slower than $$x^x$$. However, I'm not sure how to show that $$x!$$ grows faster than $$(x/2)^{(x/2)}$$. I was thinking that the $$(1/2)^{x/2}$$ term would end up affecting the function, but I'm not sure how to proceed.

## 4 Answers

Perhaps taking naturals logs is illuminating:

$$\ln (x!) = \sum_{k=1}^x \ln(k)$$.

$$\ln (x^x) = x \ln x \geq \ln(x!)$$.

$$\ln(x/2)^{(x/2)} = (x/2) \ln (x/2)$$. We can see there are half as many logarithms here as in the sum $$\sum_{k=1}^x \ln(k)$$. We compare our $$\ln(x/2)$$ with the upper half of the $$\ln(k)$$ logarithms, i.e. $$x\geq k \geq floor(x/2)$$. When $$x$$ even you can see every $$\ln(k)$$ logarithm is greater than the $$\ln(x/2)$$. For $$x$$ odd, we add the extra logarithm $$\ln((x-1)/2)$$. It is fairly clear the summed logarithms still win.

The change in the exponent from $$x$$ to $$x/2$$ is enormous. The $$2$$ in the denominator doesn't matter so much. We can use Stirling's approximation for the factorial $$x! \approx \frac {x^x}{e^x}\sqrt{2 \pi x}$$ to see $$(x/2)^{(x/2)} \lt x^{(x/2)}=\sqrt{x^x}\lt x! \lt x^x$$

Let's assume $$x$$ even, for simplicity:

One way to see that $$x!$$ is way bigger than $$(\frac{x}{2})^{\frac{x}{2}}$$ is by looking at the last $$\frac{x}{2}$$ numbers of the product $$x!=1\cdot 2\cdot \dots (\frac{x}{2})(\frac{x}{2}+1)(\frac{x}{2}+2)\dots \cdot x.$$ In the following product, each factor is bigger than $$\frac{x}{2}$$, so $$(\frac{x}{2}+1)(\frac{x}{2}+2)\dots \cdot x\geq (\frac{x}{2})^{\frac{x}{2}}$$ So, $$x!\geq 1\cdot 2\cdot \dots (\frac{x}{2})(\frac{x}{2})^{\frac{x}{2}} =(\frac{x}{2})!(\frac{x}{2})^{\frac{x}{2}}$$. So, $$\lim_{x\to\infty} \frac{x!}{(\frac{x}{2})^\frac{x}{2}}\geq \lim_{x\to\infty} (\frac{x}{2})! =\infty.$$ Which means that $$x!$$ grows faster than $$(\frac{x}{2})^\frac{x}{2}$$

If $$x$$ is even then more than half the $$x$$ terms in $$1\times 2 \times \cdots \times \left(\frac{x}{2}-1\right)\times \frac{x}{2}\times \left(\frac{x}{2}+1\right)\times \cdots \times (x-1) \times x$$ are at least as big as $$\frac x2$$, and one term is $$1$$ while the others are no bigger than $$x$$ so

$$\left(\tfrac x2 -1\right) !\times \left(\frac{x}2\right)^{x/2} \times x \le x! \le 1 \times x^{x-1}$$

These are still very loose bounds but are enough for your result. The argument for odd $$x$$ is similar.