0
$\begingroup$

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

$\endgroup$
  • 3
    $\begingroup$ Are you sure that is not a 2logn on the right hand side? $\endgroup$ – Gamma Function Jun 8 '13 at 8:28
  • $\begingroup$ @ Jacob Mayle No, why? $\endgroup$ – Mo Sanei Jun 8 '13 at 8:30
  • 2
    $\begingroup$ Because the RHS is simply $6n\log(n)$ $\endgroup$ – Ewan Delanoy Jun 8 '13 at 8:30
  • $\begingroup$ 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. $\endgroup$ – Gamma Function Jun 8 '13 at 8:32
1
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ @DannZimm Thanks! Sorry I can't vote up because I don't have enough reputation but I hope others will vote up your answer. $\endgroup$ – Mo Sanei Jun 8 '13 at 9:42
  • $\begingroup$ @MohammadSanei no problem, I hope this helped! $\endgroup$ – DanZimm Jun 8 '13 at 10:27
5
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$

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.