# Good upper bound of $\lfloor n\log_2 n\rfloor$ (or $\lfloor \frac{n\log_2 n}{2}\rfloor$)?

I am wondering if there is any good upper bound other than the trivial one for $\lfloor n\log_2 n\rfloor$ (or $\lfloor \frac{n\log_2 n}{2}\rfloor$, I am not sure which one is easier to bound) for all integers $3\le n\le 2^k-1$ (or for all $2^{k-1}<n\le 2^k-1$), where $k\ge 3$ is a positive integer (or just for all large positive integers $k$).

$\lfloor x\rfloor$ means the largest integer at most $x$. Notice the base of logarithm is of 2.

I am trying to check if $$(2^k-n)(k\cdot 2^{k-1}-1)<(2^k-2)(k\cdot 2^{k-1}-1-\lfloor \frac{n\log_2 n}{2}\rfloor)$$ holds for all integers $2^{k-1}<n\le 2^{k}-1$ and $k\ge 4$, say. Therefore a good bound of $\lfloor \frac{n\log_2 n}{2}\rfloor$ other than the trivial one is needed.

• What constitutes "good"? What's wrong with $n\log n$ as an upper bound? – Gerry Myerson Feb 14 '18 at 6:00
• I just revised it. – Connor Feb 14 '18 at 6:08
• How is this anyway related to combinatorics – Darkrai Feb 14 '18 at 10:33
• @Manthanein it can be viewed as counting problem in some sense. – Connor Feb 14 '18 at 13:50