Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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} $$

share|improve this question
3  
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
2  
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

2 Answers 2

up vote 1 down vote accepted

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

share|improve this answer
1  
@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.

share|improve this answer
    
Thanks @BartekPawlik –  Mohammad Sanei Jun 8 '13 at 8:54

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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