# Please help me prove by induction that $n^n>1\cdot3\cdot5\cdot\ldots\cdot(2n-1)$

Please help me prove by induction that $$n^n>1\cdot3\cdot5\cdot\ldots\cdot(2n-1)$$

-
This sounds like homework, how far did you get? – Listing Mar 15 '12 at 10:24
When $n=1$, LHS$=1^1=1$ and RHS$=1\cdots(2\cdot1-1)=1$=LHS. So I think you want to prove the inequality when $n\geq 2$. – Paul Mar 15 '12 at 10:32

Hint:

$$\rm (n+1)^{n+1}>(2n+1)n^n$$

$$\large\Updownarrow$$

$$\rm \left(1+\frac{1}{n}\right)^n>\binom{n}{0}+\binom{n}{1}\frac{1}{n}=2>\frac{2n+1}{n+1}$$

-

This is proof without induction. $$1\cdot 3\cdot 5\cdot\ldots\cdot(2n-1)= \frac{1\cdot 2\cdot 3\cdot\ldots\cdot 2n}{2\cdot 4\cdot 6\cdot\ldots\cdot 2n}= \frac{1\cdot 2\cdot 3\cdot\ldots\cdot 2n}{(2\cdot 1)\cdot (2\cdot 2)\cdot (2\cdot 3)\cdot\ldots\cdot (2\cdot n)}=$$ $$\frac{1\cdot 2\cdot 3\cdot\ldots\cdot 2n}{2^n\cdot 1\cdot 2\cdot 3\cdot\ldots\cdot n}= \frac{(n+1)\cdot (n+2)\cdot\ldots\cdot 2n}{2^n}$$ So we had to prove that $$n^n>\frac{(n+1)\cdot (n+2)\cdot\ldots\cdot 2n}{2^n}$$ But the last inequality is obvious, since $$\frac{(n+1)\cdot (n+2)\cdot\ldots\cdot 2n}{2^n}= \frac{n+1}{2}\frac{n+2}{2}\cdots\frac{n+n}{2}<n\cdot n\cdot\ldots \cdot n=n^n$$

-

Hint $\$ Use telescopy: a trivial induction shows a product of terms $> 1$ is $> 1$. Applying this to

$$\rm\ f(n)\ =\ \frac{f(n)}{\color{red}{f(n-1)}}\ \frac{\color{red}{f(n-1)}}{\color{green}{f(n-2)}}\ \frac{\color{green}{f(n-2)}}{\cdots }\ \cdots\ \frac{\cdots}{\color{brown}{f(3)}}\ \frac{\color{brown}{f(3)}}{\color{blue}{f(2)}}\ \frac{\color{blue}{f(2)}}{1}$$

the product $\rm\:f(n) > 1\:$ if each factor is, i.e. if $\rm\:f(2) > 1\:$ and $\rm\:f(k+1)/f(k) > 1\:$ for $\rm\:k\ge 2.\:$ But your $\rm\:f(n) = n^n/(1\cdot 3\cdot 5\cdots 2n\!-\!1)\:$ satisfies such by an easy calculation (see anon's answer).

-

$$\frac{(n+1)^{n+1}}{n^n}=(n+1)\left(1+\frac{1}{n}\right)^n\ge(n+1)\left(1+n\cdot\frac{1}{n}\right)=2n+2>2n+1$$

-

This could be an interesting method. For k>1 and even n>0, show that

$n^{2k}>[n-(2k-1)]\times[n-(2k-3)]\times...(n-1)\times(n+1)\times...\times[n+(2k-3)]\times[n+(2k-1)]$

Our base case: $n^2>n^2-1=(n-1)\times(n+1)$

Now the inductive step: Assume true for $k=m$, prove true for $k=m+1$

$n^{2m}>[n-(2m-1)]\times[n-(2m-3)]\times...\times[n+(2m-3)]\times[n+(2m-1)]$

$n^2>n^2-(2m+1)^2=[n-(2m+1)]\times[n+(2m+1)]$

Multiply the top inequality by $[n-(2m+1)]\times[n+(2m+1)]$ and the bottom by $n^{2m}$ to get

$n^{2(m+1)}>[n^2-(2m+1)^2]\times n^{2m}>[n-(2m+1)]\times[n-(2m-1)]\times...\times[n+(2m-1)]\times[n+(2m+1)]$.

This completes the inductive step and we have proven our case for k>1. This includes the case $k=\frac n2$.

The odd case should be similar, except you will likely need to actually use that $n>0$ as you will likely need to multiply or divide by odd powers of n which would reverse the inequalities if $n<0$.

-

We need to prove $1\cdot 3\cdot 5\cdot \ldots \cdot (2n-1)< n^n$

For $n=1$ we have $1 < 1$, what is wrong.

For $n=2$ we have $3 < 4$ what is true.

Note that $1\cdot 3\cdot 5\cdot \ldots \cdot (2n-1) (2\cdot (n+1)-1)=n^n(2(n+1)-1)$

then prove $(n+1)^{n+1} - n^n\cdot (2\cdot (n+1)-1) > 0$

-

### Alternative solution:(Without induction)

Using $AM \ge GM$ inequality we get $$\dfrac{1+3+5+\dots+(2n-1)}{n}> [1\cdot3 \cdot 5\dots (2n-1)]^{1/n}$$ Note that $$1+3+5+\dots+(2n-1) = \sum_{i=1}^n(2i-1)\\=2 \sum_{i=1}^n i-\sum_{i=1}^n1 \\=2\cdot\dfrac{n(n+1)}{2}-n =n^2$$ So our inequality becomes $$\dfrac{n^2}{n}> [1\cdot3 \cdot 5\dots (2n-1)]^{1/n} \\ \implies n^n>1\cdot3\cdot5\cdot\ldots\cdot(2n-1)$$

-