3
$\begingroup$

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.

$\endgroup$

1 Answer 1

2
$\begingroup$

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)$.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .