This is what I have so far. How do I continue the induction step?

For n=6, this is true since $720\leq 729$ Suppose $n!\leq(\frac{n}{2})^n$ holds for all $n\geq 6$ Want to prove that it holds for n+1, That is $(n+1)!\leq(\frac{n+1}{2})^{n+1}$ for all $n\geq 6$


First, we check the base case. That is, as you showed, the statement is true for $n=6$. Indeed: $$ 6! \leq (\frac{6}{2}^6) $$ $$ \implies 720 \leq 3^6 = 729 $$ Now we assume that the given statement is true for an arbitrary element $k$ in the set of Natural Numbers $\mathbb N$. So we suppose

$$ k! \leq (\frac{k}{2})^k \ \ k \geq 6$$

is a true statement. Now, if we show this statement also holds for $n = k+1$ then we are done. That is, we want to show

$$ (k+1)! \leq (\frac{k+1}{2})^{k+1} $$

Now remember, for example, we can write $5!$ as $5 \cdot 4!$. Therefore, we can write

$$ (k+1)! = k!\cdot (k+1) $$

Now what do we know about $k!$? Well we assumed $k! \leq (\frac{k}{2})^k$. So we can write

$$(k+1)! = k! \cdot (k+1) \leq (\frac{k}{2})^k \cdot (k+1)$$

The last thing we need to do is to show $(\frac{k}{2})^k \leq \frac{(k+1)^k}{2^{k+1}}$. I will leave this to you, but you could convince yourself it is the case. Keep in mind $k \geq 6$.

Putting the pieces together, it follows $$(k+1)! \leq (\frac{k+1}{2})^{k+1}$$

This shows the statement is true by mathematical induction.


Hint: So as $n! \leq(\frac{n}{2})^n$ (from the induction assumption), we have $(n+1)! = n! (n+1)\leq(\frac{n}{2})^n (n+1) = \frac{n^n(n+1)}{2^n}$. Now it is enough to prove that $\frac{n^n}{2^n} \leq \frac{(n+1)^n}{2^{n+1}} \Leftrightarrow n^n \leq \frac{(n+1)^n}{2}$. Get $\log$ from two side: $$n\log(n) \leq n \log(n+1) - \log(2) \Leftrightarrow log(2) \leq n (\log(n+1)-\log(n)) = n\log(\frac{n+1}{n}) \\ \Leftrightarrow 2 \leq (1 + \frac{1}{n})^n$$.

As $(1+\frac{1}{n})^n$ increases monotonoically (you can see for $x > 0$ the derivative function of $(1+\frac{1}{x})^x$ is greater than zero) and for $n = 6$ we have $(1+\frac{1}{6})^6 > 2.5$ you can prove the inequality.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.