Prove by induction that $(n!)^2\geq n^n$

Question

How does one prove by induction that $(n!)^2\geq n^n$

for all $n \geq 1$

Hint:$(1+x)^r\geq 1+rx$ , for $r\geq0$ and $x\geq-1$

Step 1 For $n=1$, the LHS=$1!^2=1$ and RHS=$1^1=1$. So LHS$\geq$ RHS.

Step 2
Suppose the result be true for $n=k$ i.e.,
$(k!)^2 \geq k^k$

Step 3
For $n=k+1$
$((k+1)!)^2 \geq (k+1)^{k+1}$

$((k+1)!)^2=(k!⋅(k+1))^2=(k!)^2(k+1)^2\geq k^k(k+1)^2$

How can I do?Thank you for help

Answer 1

Write the LHS in two rows with first row in ascending otder and the second row in descending order. So $(n!)^2$ is equal to

$$1\times 2\times3\times\cdots (n-1)\times n$$

$$\times$$

$$n\times(n-1)\times\cdots 2\times 1$$

Now multiply column wise (there will be $n$ columns. SO we get $(n!)^2 = \prod_{k=1}^n \big(k\times (n+1-k)\big)$.

Now show each term of this product is at least $n$. So the full product will be at least $n^n$.

Answer 2

Might not be the shortest answer but oh well... First we start with a few lemmas:

Lemma 1: $$ \frac{(n+1)^{n+1}}{n^n} = (\frac{n+1}{n})^n (n+1) = (1+1/n)^n (n+1) < e(n+1) \implies \\ (n+1)^{n+1} < n^n \cdot e(n+1) $$

Lemma 2: If $n \geq 2$ then $(n+1)^2 \geq e(n+1)$. Proof is trivial.

Now let's start the proof by induction :

Base step $n=1$ : $(1!)^2 = 1 = 1^1$

Inductive step : $$ ((n+1)!)^2 =(n! \cdot (n+1))^2 = (n!)^2 \cdot (n+1)^2 \overset{(**)}{\geq} n^n \cdot (n+1)^2 \overset{(***)}{\geq} n^n e(n+1) \overset{(****)}{\geq} (n+1)^{n+1} $$ $(**)$ Using inductive hypothesis

$(***)$ Using Lemma 2

$(****)$ Using Lemma 1

Answer 3

Start by showing that it works for 3 (I'm starting with 3 because 1 and 2 are trivially true):

Base Case: We have: $(3!)^2 = 6^2 = 36$ We also have: $(3)^3 = 27$. So, $36 \geq 27$. Done.

Inductive Step: Assume that it works for all n.

Prove it works for all (n+1): Let's set it up as follows:

$\begin{align} ((n+1)!) ^2 \geq (n+1)^{n+1} \end{align}$.

By the definition of factorial, we have

$((n+1)!)^2 = ((n+1)n!)^2 = (n+1)^2(n!)^2$.

So, now we have $(n+1)^2(n!)^2 \geq (n+1)^{n+1}$.

If we divide both sides by $(n+1)^2$ (which we can do because this only applies where $ n \geq 0$), we get

$(n!)^2 \geq (n+1)^{n-1}$.

So, all that's left to do is to show that $n^n \geq (n+1)^{n-1}$ because, using the inductive hypothesis we know that $\forall n$ $ (n!)^2 \geq (n)^n $. This is almost trivial because the leading coefficient of $(n+1)^{n-1}$ is going to be $n^{n-1}$. This is obviously smaller than $n^n$ Everything else can be ignored because we know that the sum of all values $(n-1)^{n-2} + (n-2)^{n-3}...$ are going to be less than $n$. So, we finally get that

$(n!)^2 \geq n^n \geq (n+1)^{n-1}$. And we're done.