5
$\begingroup$

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.

  • 1
    Essentially duplicate of http://math.stackexchange.com/questions/46892/how-do-you-prove-that-nn-is-on2 and http://math.stackexchange.com/questions/136626/lim-limits-n-to-infty-sqrtnn-is-infinite2012-10-09
  • 0
    Given the fact that ab <= a + b - 1.2012-10-09
  • 0
    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!^22012-10-09

7 Answers 7

8

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

4

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

  • 0
    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.2012-10-09
  • 0
    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!^22012-10-09
  • 0
    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$.2012-10-10
2

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

  • 2
    Quite heavy artillery to kill a mouse.2012-10-09
  • 1
    yeah, don't make me angry...2012-10-09
0

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.

0

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

0

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.

  • 0
    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.2012-10-09
  • 0
    @Ignace: I restated the argument relying only on AM-GM inequality which I presume can be considered as an elementary inequality.2012-10-09
  • 0
    Ok, but even log. has yet not been introduced. The author makes us try thinking very elementary.2012-10-09
  • 0
    @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.2012-10-09
0

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