Prove that $n! \geq {\lfloor n/2 \rfloor}^{\lfloor n/2 \rfloor}$

Question

I am trying to see why it holds that, for $n \in \mathbb{N},$ $$n! \geq {\lfloor n/2 \rfloor}^{\lfloor n/2 \rfloor}.$$ I would appreciate help to see this.

Answer 1

By definition

$$n! = 1 \cdot 2 \cdot \ldots \cdot n.$$

Suppose $n$ is even. By omitting the first $\frac{n}{2}$ terms we obtain

$$n! \geqslant \left( \frac{n}{2} + 1 \right) \left( \frac{n}{2} + 2 \right) \cdot \ldots \cdot n.$$

Each of the other $\frac{n}{2}$ terms is not smaller than $\frac{n}{2}$, so

$$\left( \frac{n}{2} + 1 \right) \left( \frac{n}{2} + 2 \right) \cdot \ldots \cdot n \geqslant \frac{n}{2} \cdot \ldots \cdot \frac{n}{2} = \left( \frac{n}{2} \right)^{\frac{n}{2}}$$

which completes the argument.

If $n$ is odd, then $n-1$ is even and $\left\lfloor \frac{n}{2} \right\rfloor = \frac{n-1}{2}$ so the by the above argument the inequality holds too.

Answer 2

Stirling's approximation give us $$n!\geq\sqrt{2\pi}n^{n+1/2}e^{-n}>\left(\frac{n}{e}\right)^{\left(2n+1\right)/2}>\left(\frac{n}{2}\right)^{n/2}\geq\left\lfloor \frac{n}{2}\right\rfloor ^{\left\lfloor n/2\right\rfloor }. $$

Answer 3

If $n=2k$, we have $$n! = (1\cdot n) \cdot (2\cdot (n-1)) \cdots (k \cdot (k+1))$$ Note that for all $l \in \{1,2,\ldots,k\}$, we have $l(2k-l) > k$. Hence, we have that $$n! > \underbrace{k \cdot k \cdots k}_{k \text{ times}} = k^k$$

---

If $n=2k+1$, we have $$n! = (1\cdot n) \cdot (2\cdot (n-1)) \cdots (k \cdot (k+2)) \cdot (k+1)$$ Note that for all $l \in \{1,2,\ldots,k\}$, we have $l(2k+1-l) > k+1$. Hence, we have that $$n! > \underbrace{(k+1) \cdot (k+1) \cdots (k+1)}_{k+1 \text{ times}} = (k+1)^{k+1}$$

Answer 4

Suppose that $n = 2m + \epsilon$ where $\epsilon \in \{0,1\}$. Then $\lfloor n/2 \rfloor = m$, and so you need to show that $n! \geq m^m$.

1. As mentioned in the comments, one way to do this is to show for $k = 1, \ldots, n-1$ (or really $k = 1, \ldots, \lfloor n/2 \rfloor$) that $k(n-k) \geq \lfloor n/2\rfloor = m$. To do this, note that if $n-k = 2m+\epsilon -k$, then $k(n-k) = 2mk + \epsilon k - k^2$. So one possibility is to check that $2mk + \epsilon k - k^2 \geq m$ whenever $1 \leq k \leq m$. (It might be easier to think about this as $(m+\epsilon)k \geq k^2$.)

2. Once you know $k(n-k) \geq \lfloor n/2 \rfloor$, write $n!$ as a product over $k(n-k)$ as $k$ varies (with one extra term if $n$ is odd).