Re: Induction: an inequality

Quote:

Originally Posted by

**NonCommAlg** Prove, by induction, that for all integers $\displaystyle 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 $\displaystyle n^2=t$ and then the original problem becomes to be:

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

Proof:

Checking for $\displaystyle t=9$:

$\displaystyle 8!>9^{4.5}$

$\displaystyle 40,320 > 19,683$

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

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

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

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

We know that $\displaystyle (1)$:

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

Hence we only need to prove that:

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

Or:

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

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

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

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

$\displaystyle (2)$ becomes to:

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

So,

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