4
$\begingroup$

$\left \lfloor n\log_2 n^2 \right \rfloor + \left \lfloor \log_2(\left \lfloor n\log_2n^2 \right \rfloor) \right \rfloor \leq \left \lfloor (n+1)\log_2 (n+1)^2 \right \rfloor + 1$

How to show this? I tried using $\left \lfloor k \right \rfloor \leq k$, but I'm not sure that that does anything...

LHS $\leq \left \lfloor (n+1)\log_2 (n+1)^2 \right \rfloor + \left \lfloor \log_2(\left \lfloor n\log_2n^2 \right \rfloor) \right \rfloor $ < $\left \lfloor (n+1)\log_2 (n+1)^2 \right \rfloor + 1$ because...ugh...

$\left \lfloor \log_2(\left \lfloor n\log_2n^2 \right \rfloor) \right \rfloor \leq \log_2(\left \lfloor n\log_2n^2 \right \rfloor) < 1$?

I don't think the last inequality is true.

Help please?

I think it's supposed to hold for all natural numbers or at least all natural numbers after a certain index.

$\endgroup$
  • 1
    $\begingroup$ Are you trying to prove this $\forall n \in \mathbb{N}$? $\endgroup$ – Phrohlych Aug 24 '14 at 0:04
  • $\begingroup$ @Phrohlych I think it's supposed to hold for all natural numbers or at least all natural numbers after a certain index. Edited into question. Thanks for clarification. $\endgroup$ – BCLC Aug 24 '14 at 0:36
  • $\begingroup$ Okay. The smallest integer for which this makes sense is $2$, so that would be your starting point. Using induction, I was able to prove the base case (i.e. $n=2$). I haven't yet attempted the inductive step, but that might be the direction where you want to head. $\endgroup$ – Phrohlych Aug 24 '14 at 0:38
  • $\begingroup$ @Phrohlych Ayt. Will try that out. Thanks $\endgroup$ – BCLC Aug 24 '14 at 0:46
2
$\begingroup$

hint:

$\left \lfloor (n+1)\log_2 (n+1)^2 \right \rfloor + 1 =\left \lfloor (n\log_2 (n+1)^2)+\log_2 (n+1)^2 \right \rfloor +1\ge \left \lfloor (n\log_2 (n+1)^2) \right \rfloor +\left \lfloor \log_2 (n+1)^2\right \rfloor+1$

now prove:

$\left\lfloor (n\log_2 (n+1)^2) \right \rfloor \ge \left\lfloor (n\log_2 n^2) \right \rfloor$

$\left \lfloor \log_2 (n+1)^2\right \rfloor+1 \ge \left \lfloor \log_2(\left \lfloor n\log_2n^2 \right \rfloor) \right \rfloor $

$\endgroup$
  • 1
    $\begingroup$ Sigh. I did not know or forgot that property of greatest integer function. Thanks. $\endgroup$ – BCLC Aug 24 '14 at 12:49

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.