Question

A) Basis Step b) Inductive Step

Answer 1

Basis step: Let $n=2$. Then

$2! = 2\cdot1 = 2$

and

$2^2 = 4$

so $2! < 2^2$.

Inductive step: Assume $k! < k^k$. We want to show that $(k+1)! < (k+1)^{k+1}$.

Now

$(k+1)! = (k+1) \cdot k! \\\\ ~~~~~~~~~~~ < (k+1) \cdot k^k \\\\ ~~~~~~~~~~~ < (k+1) \cdot k^{k+1} \\\\ ~~~~~~~~~~~ < (k+1) \cdot (k+1)^{k+1}$

where the first inequality follows from the induction hypothesis; the second follows from multiplying the right side by some $k>2$; and the third from adding the remaining terms to complete the binomial expansion $(k+1)^{k+1}$, all of which are positive since they are some power of $k>2$.

QED