# Prove that $\forall n \ge 2k^2, n! \ge k^n$ (induction)

In the book I'm working out of it is recommended to first prove Part (a) and then use it as a lemma to prove Part (b). I believe I've proven Part (a) but am struggling with Part (b)... please see below for my proof of Part (a) and the prompt for Part (b).

Part (a)

Suppose $k$ is a positive integer. Prove that $\forall n \in \mathbb{N}, (k^2+n)!\ge k^{2n}$.

$Proof.$ We will prove this via mathematical induction.

Base Case. Since $k$ is positive we know $k>0$ then $k^2! > 0^2! > 1.$ Now let $n=0$ and observe that $(k^2+n)!=(k^2)! \ge 1 = k^{2(0)}=k^{2n}$.

Inductive Step. Assume $n\ge 0$ and $(k^2+n)!\ge k^{2n}$. Then

\begin{align} (k^2+(n+1))!&=(k^2+(n+1))\cdot (k^2+n)!\\ &\ge (k^2+(n+1))\cdot k^{2n} \quad\text {(by inductive hypothesis)}\\ &\ge (k^2)\cdot k^{2n} = k^{2(n+1)}. \end{align}

It follows by mathematical induction that $\forall n \in \mathbb{N}, (k^2+n)!\ge k^{2n}$. $\Box$

Part (b) Prove that $\forall n \ge 2k^2, n! \ge k^n$.

OK, so my approach here is to assume $n\ge 2k^2$ in the base case and then use Part (b) to show that $n! \ge k^n$... this is where I'm getting stuck. I see that Part (a) is structurally similar to what I'm trying to prove in Part (b) but I can't come up with an elegant way of applying Part (a) to the base case. Proceeding from here I would like to show that assuming $\forall n \ge 2k^2, n! \ge k^n \Rightarrow (n+1)! \ge k^{n+1}$ which I believe should be fairly easy given I can produce the base case.

To apply part (a) to the base case, let $n=k^2$ so you have $(k^2 + k^2)! \geq k^{2n} \geq k^n$ from (a). This is precisely $(2k^2)! \geq k^{2n}$, your base case.
Now assume $n! \geq k^n$ and call this $(\star)$.
Then $(n+1)! = (n+1)n! > \underbrace{(n+1)k^n}_{\text{by} \, (\star)} > \underbrace{kk^n}_{\text{by} \, (\dagger)} = k^{n+1}$. That is: $(n+1)! > k^{n+1}.$
Since $n \geq 2k^2 \Rightarrow n+1 > k$, call this $(\dagger)$.