Some trouble with a proof on $n!/(\sqrt{n})^n \geq 1$

Originally the problem is to prove that $n! \geq n^{n/2}$.

I reduced this to: $n! \geq (\sqrt{n})^n$ so that:

Prove that $\frac{n!}{(\sqrt{n})^n} \geq 1$.

Each term in $n!$ is divided by the $\sqrt{n}$ and the multiplication should leave it $\geq 1$.

-
Given the fact that ab <= a + b - 1. –  Ignace Oct 9 '12 at 18:40
Given the fact that (after proof) ab <= a + b - 1. If we write n!^2 = (n * 1)*(n-1)*2*(n-2)*3*........2*(n-1)*(1*n). n*1>=n+1-1<=n, (n-1)*2 >= n - 1 + 2 -1<=n,... According to the theorem each term >= n. So that n!^2 –  Ignace Oct 9 '12 at 18:49

Given the fact that (after proof) $ab \leq a + b - 1$. If we write $n!^2 = (n \cdot 1)\cdot (n-1)\cdot 2\cdot (n-2)\cdot 3 \cdots2 (n-1)\cdot (1\cdot n)$. $n\cdot 1\geq n+1-1\leq n$, $(n-1)\cdot 2 \geq n - 1 + 2 -1\leq n,...$ According to the theorem each term $\geq n$. So that $n!^2 \geq n^n$. It follows that $n! \geq n^(n/2)$

-

The case $n=1$ is trivial, so let $n>1$.$$\frac{1}{n}\prod _{i=1}^{n-1}\left(\frac{1}{i}-\frac{1}{i+1}\right)=n!^{-2}\\\implies-\log n+\sum_{i=1}^{n-1}\log\left(\frac{1}{i}-\frac{1}{i+1}\right)=-2\log n!.$$ Thus we need to prove $$\sum_{i=1}^{n-1}\log\left(\frac{1}{i}-\frac{1}{i+1}\right)\leq (n-1)\log\frac{1}{n},$$ that follows immediately from Jensen's inequality.

EDIT: A more straightforward path is simply to apply the AM-GM ineqauality. We need to show $$\prod_{i=1}^{n-1}\left(\frac{1}{i}-\frac{1}{i+1}\right)\leq \left(\frac{1}{n}\right)^{n-1}.$$ Applying AM-GM to the LHS yields $$\prod_{i=1}^{n-1}\left(\frac{1}{i}-\frac{1}{i+1}\right)\leq\left(\frac{1}{n-1}\sum_{i=1}^{n-1}\left(\frac{1}{i}-\frac{1}{i+1}\right)\right)^{n-1}=\left(\frac{1}{n-1}\left(1-\frac{1}{n}\right)\right)^{n-1},$$ which is the desired inequality.

-
Exercise is one of the first in a dutch book on analysis for beginners. Logs, jensens etc... have not yet been introduced. I rule this one out, as well as the heavy artillery in an other comment, which is even worse. –  Ignace Oct 9 '12 at 16:38
@Ignace: I restated the argument relying only on AM-GM inequality which I presume can be considered as an elementary inequality. –  S.B. Oct 9 '12 at 17:04
Ok, but even log. has yet not been introduced. The author makes us try thinking very elementary. –  Ignace Oct 9 '12 at 17:52
@Ignace: The $\log$ is not used in the AM-GM approach. You only need to write $\frac{1}{n!^2}$ as the product mentioned in the first line, cancel one \frac{1}{n}, and then apply the AM-GM as mentioned in the edit. –  S.B. Oct 9 '12 at 17:57

Consider the product $$(1\cdot2\cdot 3\cdots n)( 1\cdot 2\cdot 3 \cdots n).$$ Divide these numbers into pairs, as in the "Baby Gauss" way of finding $1+2+3+\cdots +n$. Work from both ends in. Our product is $$[1\cdot n][2\cdot (n-1)][3\cdot (n-2)]\cdots [n\cdot 1].$$ We have $n$ pairs, each with sum $n+1$. In general, $$xy=\frac{(x+y)^2}{4}-\frac{(x-y)^2}{4}.$$ Let $x+y$ be fixed at $n+1$, and let $x$ and $y$ be positive integers. Then $xy$ is minimized when $|x-y|$ is as large as possible, that is, when $|x-y|=n-1$. So the minimum product of two paired numbers is $n$. It follows that $$(n!)^2 \ge n^n.$$

-

$$n! \geq n^{n/2}\Leftrightarrow(n!)^{2}\geq n^{n}$$ Notice that $$(n!)^{2} =\prod_{k=1}^{n}k\prod_{k=1}^{n}(n+1-k) =\prod_{k=1}^{n}k(n+1-k)$$ and for each $k$, $k(n+1-k)-n=(k-1)(n-k)\geq0$, so $k(n+1-k)\geq n$ for each $k$, then $$(n!)^{2}=\prod_{k=1}^{n}k(n+1-k)\geq\prod_{k=1}^{n}n=n^{n}$$

-

HINT: Note that $k \times (n+1-k) \geq n$ for $k \in \{1,2,\ldots,n\}$.

-
Just in front of the exercise stood: prove that ab > a + b -1. It was meant as a hint for the problem I think. But I on't see the link. I don't see it Marvis, sorry. –  Ignace Oct 9 '12 at 16:39
I think I got it. Given the fact that (after proof) ab <= a + b - 1. If we write n!^2 = (n * 1)*(n-1)*2*(n-2)*3*........2*(n-1)*(1*n). n*1>=n+1-1<=n, (n-1)*2 >= n - 1 + 2 -1<=n,... According to the theorem each term >= n. So that n!^2 –  Ignace Oct 9 '12 at 18:48
For $a=k$ and $b=n+1-k$ one has $a+b-1=n$; that's the link. Or maybe I should add: now substitute that into $ab>a+b-1$. –  Marc van Leeuwen Oct 10 '12 at 12:03

Hint (also, don't reexpress the problem like you did):

Suppose $n > 1$ is odd, that is, $n = 2k+1$ for some $k \geq 1$.

Then $n! = 1 * 2 * 3 * ... * (2k+1)$. Forget about the first multiplicand:

$n! = [2 * 3 * ... * (k+1)] * [(k+2) * ... * (2k+1)].$

Each bracket contains how many multiplicands? What else can you spot?

Then, a similar argument needs to be carried out for $n$ even.

-

$$s^{-s}=\frac{1}{\Gamma (s)}\int_{0}^{\infty }t^{s-1}e^{-st}dt$$ (from here) therefore $(n!)^2 n^{-n}=\Gamma(n+1)^2\frac1{\Gamma(n)}\int \limits_0^\infty t^{n-1}e^{-nt}=n\Gamma(n+1)\int \limits_0^\infty t^{n-1}e^{-nt}\ge 1$

-
Quite heavy artillery to kill a mouse. –  Ignace Oct 9 '12 at 16:35
yeah, don't make me angry... –  draks ... Oct 9 '12 at 18:12