Weak induction: $\log(n!) < n\log(n)$

Question

I'm currently stuck on the next step in proving this inequality $\log(n!) < n\log(n) \\$. These are the steps I have so far. I can't quite seem to get the LHS to the RHS. Can I get some advise on how to work trough it?

• Assume: $\log(k!) < k\log(k)$
• Prove: $\log((k+1)!) < (k+1)\log(k+1)$
• LHS = $\log((k+1)!) = \log(k!(k+1)) = \log(k!) + \log(k+1)$
• $\ < k\log(k^1) + \log(k+1)$ This is where I start to get lost
• $\ < (k+1)\log(1) + \log(k+1)$ Not sure this step is entirely correct
• Not sure what step to do next to get it to the RHS

Answer 1

$k\log(k)+\log(k+1)<k\log(k+1)+\log(k+1)=(k+1)\log(k+1)$

Answer 2

For a complete prove by induction we need to consider the base case and the induction step. In this case we have

• base case: $n=1\implies \log 1!<1\log 1$ which is true

then condider the

• induction step: assuming that $\log n!<n\log n$ is true we need to show that $\log (n+1)!<(n+1)\log (n+1)$ then

$\log (n+1)!=\log (n+1)+\log n! <\log (n+1)+n\log n <\log (n+1)+n\log (n+1)=(n+1)\log (n+1)$

Answer 3

This can be alternatively proved like this:

$k\log{(k)}=\log{(k^k)}$

${k^k\over k!}$

$={k\over k-1}\cdot{k\over k-2}\cdot\ \cdots\ \cdot{k\over1}$

$\gt1$

So, $k^k\gt k!$

Which proves that $\log (k!)\lt k\log(k)$