Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

Some advice.

share|improve this question
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

7 Answers 7

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

share|improve this answer

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

share|improve this answer
    
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

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

share|improve this answer
2  
Quite heavy artillery to kill a mouse. –  Ignace Oct 9 '12 at 16:35
1  
yeah, don't make me angry... –  draks ... Oct 9 '12 at 18:12

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.

share|improve this answer

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

share|improve this answer

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.

share|improve this answer
    
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

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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.