Inequality and induction.

Question

I can't solve this inequality by use of induction,

$$(n!)^2\ge n^n$$

so my teacher has advised me to break the multiplies into pairs, but it doesn't help. How do I prove it?

Answer 1

I'll try to continue @Dr. Sonnhard Graubner proof by showing that

$$n+1\geq (1+\frac{1}{n})^{n} \forall n\geq1$$

Let $f(x)=ln(x+1)-xln(1+\frac{1}{x})$ then $f'(x)=\dfrac{2}{n+1}-ln(1+\frac{1}{n})$ and $f''(x)=\dfrac{1-x}{x(x+1)^2}<0$ for $x>1 $ so $f'$ is decreasing and $$\lim_{x\to \infty}f'(x)=0$$

so $f'(x)>0$ for $x>1\Rightarrow f(x)\geq f(1)=0$ for $x\geq1$ which is what we wanted

Answer 2

you have to prove that $$(n+1)!^2\geq (n+1)^{n+1}$$ if $$(n!)^2\geq n^n$$ we write the last inequality in the form $$n!\geq \sqrt{n^n}$$ we multiply by $$n+1>0$$ and get $$(n+1)!\geq (n+1)\sqrt{n^n}$$ and now we Show that $$(n+1)\sqrt{n^n}\geq \sqrt{(n+1)^{n+1}}$$ and this is $$(n+1)^{2}n^{n}\geq (n+1)^{n+1}$$ or $$(n+1)\geq \left(\frac{n+1}{n}\right)^{n}$$ which is $$n^n\geq (n+1)^{n-1}$$ and his is $$n+1\geq \left(1+\frac{1}{n}\right)^n$$

Answer 3

$(n!)^2 = (1*2*.....*n)(1*2*.....*n)$

$ = (1*2*.....*n)(n*(n-1)*.....*1)$

$ = (n*1)((n-1)*2)*.....*((n+1-k)*k)*....(1*n)$

If we can prove $(n+1-k)*k \ge n$ then we are done as

$(n*1)((n-1)*2)*.....*((n+1-k)*k)*....(1*n) \ge (n)(n)(n).....(n) = n^n$

.....

And $(n+1-k)*k = nk + (1-k)k = n + (k-1)n -(k-1)k = n + (k-1)(n-k)$. As $0 \le k \le n$ then $(k-1)(n-k) \ge 0$ and $(n+1-k)*k \ge n$.

Answer 4

For a generic $n$, if it is true that $$ n^{\,n} \le \left( {n!} \right)^{\,2} = \left( {\prod\limits_{1\, \le \,k\, \le \,n} k } \right)^{\,2} = \prod\limits_{1\, \le \,k\, \le \,n} {k^{\,2} } $$ it means that it is true that $$ 1 \le \prod\limits_{1\, \le \,k\, \le \,n} {k{k \over n}} = P(n) $$

then, since $$ \eqalign{ & {{P(n + 1)} \over {P(n)}} = {{\prod\limits_{1\, \le \,k\, \le \,n + 1} {k{k \over {n + 1}}} } \over {\prod\limits_{1\, \le \,k\, \le \,n} {k{k \over n}} }} = {{\left( {n + 1} \right)\prod\limits_{1\, \le \,k\, \le \,n} {k{k \over {n + 1}}} } \over {\prod\limits_{1\, \le \,k\, \le \,n} {k{k \over n}} }} = \cr & = \left( {n + 1} \right)\prod\limits_{1\, \le \,k\, \le \,n} {{n \over {n + 1}}} = \left( {n + 1} \right)\left( {{1 \over {1 + 1/n}}} \right)^{\,n} = {{\left( {n + 1} \right)} \over {\left( {1 + 1/n} \right)^{\,n} }} \ge {{\left( {n + 1} \right)} \over e} \ge {{\left( {n + 1} \right)} \over 3} \cr} $$

we have that $$ P(n) \le P(n + 1)\quad \left| {\;2 \le n} \right. $$

Now, it is $$ \left\{ \matrix{ 1 \le P(0) = {{\left( {0!} \right)^{\,2} } \over {0^{\,0} }} = 1 \hfill \cr 1 \le P(1) = {{\left( {1!} \right)^{\,2} } \over {1^{\,1} }} = 1 \hfill \cr 1 \le P(2) = {{\left( {2!} \right)^{\,2} } \over {2^{\,2} }} = 1 \hfill \cr} \right. $$

and therefore we can conclude that $$ 0 \le P(n) = {{\left( {n!} \right)^{\,2} } \over {n^{\,n} }}\quad \left| {\;0 \le n} \right. $$

Answer 5

This is a supplement to @fleablood's nice answer. Note that the advice of OP's teacher to break the multiples into pairs allows a proof even without induction.

We obtain for $n\geq 1$ \begin{align*} \color{blue}{\left(n!\right)^2}=\prod_{k=1}^n (k\cdot k)=\prod_{k=1}^n \left[k\cdot (n+1-k)\right] =\prod_{k=1}^n[n+\underbrace{(k-1)(n-k)}_{\geq 0}]\color{blue}{\geq n^n} \end{align*} and the claim follows.