Proving that $n!≤((n+1)/2)^n$ by induction

Question

I'm new to inequalities in mathematical induction and don't know how to proceed further. So far I was able to do this:
$V(1): 1≤1 \text{ true}$
$V(n): n!≤((n+1)/2)^n$
$V(n+1): (n+1)!≤((n+2)/2)^{(n+1)}$

and I've got :
$(((n+1)/2)^n)\cdot(n+1)≤((n+2)/2)^{(n+1)}$
$((n+1)^n)n(n+1)≤((n+2)^n)((n/2)+1)$

Answer 1

An induction proof:

First, let's make it a little bit more eye-candy:

$$ n! \cdot 2^{n} \leq (n+1)^n $$

Now, for $n=1$ the inequality holds. For $n=k\in\mathbb{N}$ we know that:

$$ k! \cdot 2^{k} \leq (k+1)^k $$

holds and we need to prove:

$$ (k+1)! \cdot 2^{k+1} \leq (k+2)^{k+1} $$

We will now prove this chain of inequalities (which gives us the actual proof):

$$ (k+1)! \cdot 2^{k+1} \leq 2(k+1)^{k+1} \leq (k+2)^{k+1} $$

The first inequality is from the assumption (both sides multiplied by $2(k+1)$). Now we just need to prove the second one. In other words, we need to prove this (for some big enough positive integer $p$):

$$ 2p^{p} \leq (p+1)^{p} $$

And that's rather obvious. The inequality

$$ 2 \leq \left(1+\frac{1}{p}\right)^{p} $$

holds because the function on the right is known to be increasing and its limit (as $p\to\infty$) is $e$. So at some point on it has to be greater than 2.

Answer 2

It is more easy to prove this inequality without induction. Really $$0 < i\cdot (n + 1 - i) = \left(\frac{n+1}2 + \frac{2i - n - 1}2\right)\left(\frac{n+1}2 - \frac{2i - n - 1}2\right) = \left(\frac{n+1}2\right)^2 - \left(\frac{2i - n - 1}2\right)^2 \le \left(\frac{n+1}2\right)^2.$$ Multiply this inequalities for all $i = 1, 2, \ldots, \left\lfloor\frac n2\right\rfloor$ and by $\frac{n+1}2 = \frac{n+1}2$ for odd $n$ to get $n! \le \left(\frac{n+1}2\right)^n$ as desired.

Answer 3

If you really need induction let it be. Base is $n = 0$: $0! = 1 \le 1 = \left(\frac12\right)^0$. By induction hypothesis the inequality holds for $n = k$. Let proove it for $n = k+1$. $$k! \le \left(\frac{k+1}2\right)^k,\\ k!(k+1) \le \left(\frac{k+1}2\right)^k(k+1),$$ $$(k+1)! \le \frac{(k+1)^{k+1}}{2^k}.\tag{*}$$ Now we need to show that $f(x) = \frac{x^{x}}{(x+1)^x} \le \frac12$. Ok, $f(x) = \left(\frac{x}{x+1}\right)^x = e^{x(\ln x - \ln (x+1))}$, then $$f'(x) = e^{x(\ln x - \ln (x+1))}\left((\ln x - \ln (x+1)) + x\left(\frac1x - \frac1{x+1}\right)\right) = e^{x(\ln x - \ln (x+1))}\left(\ln \left(1 - \frac1{x+1}\right) + \frac1{x+1}\right) \le 0$$ for any positive $x$, since $\ln y \le y - 1$ for any positive $y$. So $f(x) \le f(1) = 1/2$ for any $x \ge 1$. Then from (*) we get $$(k+1)! \le \frac{(k+1)^{k+1}}{2^k} \le \frac{(k+1)^{k+1}}{2^k}\cdot \frac1{2f(k+1)} = \frac{(k+1)^{k+1}}{2^k}\cdot \frac{(k+2)^{k+1}}{2(k+1)^{k+1}} = \frac{(k+2)^{k+1}}{2^{k+1}} = \left(\frac{k+2}2\right)^{k+1}.$$