My textbook mentions a problem which is as follows:
Prove the inequalities $ (n!)^2 \le n^n\cdot n! \lt (2n)! $ for all $n \in \mathbb{N}$. It also has a solution but in a intuitive way. I am thinking to prove it by mathematical induction.
Let $P(n) : (n!)^2 \le n^n \cdot n! \lt (2n)!$
$\mathbf{Base \ Case}$:
$P(1): (1!)^2 \le 1^1 \cdot 1!\lt (2\cdot1)! \implies 1 \le 1\lt 2$
Hence, $P(1)$ is true
$\mathbf{Induction \ Hypothesis}$:
Suppose $P(m)$ is true for some $m \in \mathbb{N}$.
$$\implies (m!)^2 \le m^m \cdot m! \lt (2m)!$$
Now, $$((m+1)!)^2 = (m+1)! \cdot(m+1)! = m! \cdot (m+1)(m+1)! \le m^{m*} \cdot (m+1) \cdot (m+1)! \le (m+1)^{m**} (m+1)(m+1)!$$
$$\implies ((m+1)!)^2 \le (m+1)^{m+1}(m+1)!$$
$*$ Using induction hypothesis
$** m \le m+1 \implies m^m \le (m+1) ^m$
But for the second inequality , I am stuck. Please someone help.
Thanking in advance.
In general, if you want to prove an equality $$a(n) \leq b(n) \quad \forall n \in \mathbb{N}$$ by induction it is sufficient (but not necessary) that the base case is indeed true and then $$\frac{a(n+1)}{a(n)} \leq \frac{b(n+1)}{b(n)} \quad \forall n \in \mathbb{N}.$$ The same argument works for strict inequality.
This drastically simplifies your problem: you now only need to show that $$\left(m+1\right)^2 \leq \frac{(m+1)^{m+1}}{m^m} \cdot (m+1) < (2m + 1)(2m+2) \quad \forall m \in \mathbb{N}.$$
The first inequality is equivalent to $$m+1 \leq \left(1 + \frac{1}{m}\right)^m \cdot (m + 1),$$ which is obviously true. The second one is equivalent to $$\left(1 + \frac{1}{m}\right)^m \cdot (m + 1) < 2(2m + 1)$$ $$\left(1 + \frac{1}{m}\right)^m < 4 - \frac{2}{m+1},$$ which is a little bit more tricky. Using the binomial theorem we can write $$\left(1 + \frac{1}{m}\right)^m = 1 + \sum_{k=1}^n\frac{n\cdot ... \cdot (n-k+1)}{n^k \cdot k!} < 1 + \sum_{k=1}^n \frac{1}{k!} < 1 + \sum_{k=0}^n \frac{1}{2^{k-1}} < 1 + \sum_{k=0}^\infty \frac{1}{2^{k-1}} = 1 + 2 = 3.$$ So we can use this to prove the above inequality whenever $\frac{2}{m+1} < 1$, i.e. $m > 2$. And for $m=1, 2$ you can check it by hand.
P.S. The last paragraph is basically the standart proof that number $e = \lim_{m \to \infty} \left(1 + \frac{1}{m}\right)^m$ is less than $3$. If you also know the fact that $\left(1 + \frac{1}{m}\right)^m$ is monotonously increasing then there's nothing left to show then :) However this is also proved via basically the same argument.