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