# Induction: an inequality

• Apr 13th 2009, 06:46 PM
NonCommAlg
Induction: an inequality
Prove, by induction, that for all integers $n \geq 3: \ (n^2 - 1)! > n^{n^2}.$

Ok, I wanted to say that I like solving problems more than posting them. So, don't wait for me or Moo! Just post any problem that you think is interesting (but not easy) in this subforum!
• Jun 16th 2011, 06:42 PM
Also sprach Zarathustra
Re: Induction: an inequality
Quote:

Originally Posted by NonCommAlg
Prove, by induction, that for all integers $n \geq 3: \ (n^2 - 1)! > n^{n^2}.$

Ok, I wanted to say that I like solving problems more than posting them. So, don't wait for me or Moo! Just post any problem that you think is interesting (but not easy) in this subforum!

First say that $n^2=t$ and then the original problem becomes to be:

$(t-1)!> (\sqrt{t})^t$ or: $(t-1)!> t^{\frac{t}{2}}$ for $t \geq 9$.

Proof:

Checking for $t=9$:

$8!>9^{4.5}$

$40,320 > 19,683$

Suppose that the inequality holts for $k>9$:

$(1)$ $(k-1)!> k^{\frac{k}{2}}$

Now we will prove the inequality for $k+1$:

$k!> (k+1)^{\frac{k+1}{2}}$

We know that $(1)$:

$k!=k(k-1)!>k\cdot k^{\frac{k}{2}}$

Hence we only need to prove that:

$k\cdot k^{\frac{k}{2}}>(k+1)^{\frac{k+1}{2}}$

Or:

$(2)$ $k>\frac{(k+1)^{\frac{k+1}{2}}}{k^{\frac{k}{2}}}$

$\frac{(k+1)^{\frac{k+1}{2}}}{k^{\frac{k}{2}}}=$

$\frac{(k+1)^{\frac{k}{2\cdot }}\sqrt{k+1}}{k^{\frac{k}{2}}}=$

$(1+\frac{1}{k})^{\frac{k}{2}}\sqrt{k+1}$

$(2)$ becomes to:

$k>(1+\frac{1}{k})^{\frac{k}{2}}\sqrt{k+1}$

So,

$k>3\sqrt{k+1)$ (That is true for $k>9$)