# Why does this inequality hold: $4n+2\le4n\log{n}+2n\log{n}$

Why is the following true? (I came across this in an algorithm analysis book but this inequality is not related to algorithm analysis)

$$4n+2\le4n\log{n}+2n\log{n}$$

-
Are you sure that is not a 2logn on the right hand side? – Gamma Function Jun 8 '13 at 8:28
@ Jacob Mayle No, why? – Mohammad Sanei Jun 8 '13 at 8:30
Because the RHS is simply $6n\log(n)$ – Ewan Delanoy Jun 8 '13 at 8:30
If that were the case, you would simply factor the RHS to $(4n+2)\log(n)$ and observe that for large $n$, $\log(n) \geq 1$. The 2n really breaks the symmetry and as @EwanDelanoy points out, the RHS would simply be $6n \log(n)$. It may be a typo in the text, it may not be. The inequality holds either way. – Gamma Function Jun 8 '13 at 8:32

Well based on the comments, it appears there is no mistake and the OP wants to see how the following is true

$$4n + 2 \le 4n \log n + 2n \log n$$

First we notice that this is equivalent to

$$2n + 1 \le 2n \log n + n \log n = 3n \log n = \log \left( n^{3n} \right)$$

We can exponentiate both sides with base $e$ and the sign stays the same since $e^x$ is always increasing

$$\implies e^{2n+1} \le n^{3n}$$

Now we can use induction to prove this $\forall \; n \ge 3$

$$e^{2(3)+1} = e^7 = 1096.63315843 \le 19683 = 3^9 = 3^{3(3)}$$

So our base case of $n=3$ is proven. Now let us assume $e^{2n+1} \le n^{3n}$ is true and try to prove that $e^{2(n+1)+1} \le (n+1)^{3(n+1)}$ is true. It's clear that $\forall \; n \ge 3$ that

$$(n+1)^{3n+3} = (n+1)^{3(n+1)} = \left( n^3 + 3n^2 + 3n + 1\right)^{n+1} \ge n^{3n}e^2 \ge e^{2n+1}e^2 = e^{2n+3}$$

If you want a more rigorous proof of the inequality $\left( n^3 + 3n^2 + 3n + 1\right)^{n+1} \ge n^{3n}e^2$ let me know. Otherwise $e^{2n+1} \le n^{3n}$ is true which implies that the wanted statement is true for all $n \ge 3$.

-
@DannZimm Thanks! Sorry I can't vote up because I don't have enough reputation but I hope others will vote up your answer. – Mohammad Sanei Jun 8 '13 at 9:42
@MohammadSanei no problem, I hope this helped! – DanZimm Jun 8 '13 at 10:27

I suppose that it should be $$4n+2\le 4n\log n+2\log n.$$ In this case you should just do the following: $$4n+2\le \log n (4n+2).$$ So, by dividing by $(4n+2)$, you get $1\le \log n$. That should be easy now.

-
Thanks @BartekPawlik – Mohammad Sanei Jun 8 '13 at 8:54