$P(n)$ is the statement $n! < n^n$, where $n$ is an integer greater than $1$.
I found a solution online here (https://people.cs.umass.edu/~barring/cs2... But I don't understand how they got from one step to the next.
One user gave me the explanation:
So we start with: $(k+1)! = (k+1) \cdot k!$
Now, since $P(k)$ is true, $k! < k^k$, therefore: $(k+1) \cdot k! < (k+1) \cdot k^k $
Obviously, $k < (k+1)$, therefore: $(k+1) \cdot k^k < (k+1) \cdot (k+1)^k$
And finally: $(k+1) \cdot (k+1)^k = (k+1)^1 \cdot (k+1)^k = (k+1)^{k+1} $.
What I don't understand is how they got from the 2nd step to the third step.
Please explain it.
The steps, and their justifications, are as follows.
$$\begin{align} 1:\; & (k+1)! = (k+1)\cdot k! & \text{by definition} \\ 2:\; & (k+1)! < (k+1)\cdot k^k & \text{assuming: }P(n) \\ 3:\; & (k+1)! < (k+1)\cdot(k+1)^k & \text{since: } k^k < (k+1)^k\text{ for all }k>0 \\ 4:\; & (k+1)! < (k+1)^{k+1} & \text{because: } a\cdot a^k = a^{k+1} \\ \hline \therefore\quad & \forall k>0 \;( P(k)\to P(k+1)) &\text{giving us the iterative step} \\[2ex]0:\; & 2!<2^2 & \text{the base case: } P(2) \\ \hline \therefore \quad& \forall k\geq 2 \; ( P(k) )& \text{by induction } \\ & & \Box \end{align}$$