0
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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$$

$\endgroup$
0
$\begingroup$

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}$

$\endgroup$
0
$\begingroup$

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.

$\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.