Prove there exists $k$ s.t. $\log_2(n)-\frac{n-1}{n}\log_2(n-1)\le k $

Question

Prove for $n\ge 2$ there exists constant $k$ such that $$ \log_2(n)-\frac{n-1}{n}\log_2(n-1)\le k $$

for $n=2,\dots,8$ I see that LHS equals below values respectively

1 0.918296 0.811278 0.721928 0.650022 0.591673 0.543564

So I guess $k=1$ ? However I not good at math so I cannot prove easily. I tried proving by contradiction but failed : assume that's not the case, that means there exists $u\ge 2$ such that

$$ \log_2(u)-\frac{u-1}{u}\log_2(u-1)> 1\\ \implies \frac{1}{u\ln 2}-\frac{u-1}{u}\frac{1}{(u-1)\ln 2}+\frac{u-(u-1)}{u^2}\log_2(u-1)> 0 \\ \frac{1}{u\ln 2}-\frac{1}{u\ln 2}+\frac{1}{u^2}\log_2(u-1)> 0 \\ \frac{1}{u^2}\log_2(u-1)> 0 $$

where I derived both sides (I'll be even more clueless if I don't), but this isn't going anywhere... I'd appreciate some help.

Answer 1

Consider the real-valued function $f(x) = \log_2{x} - \frac{x - 1}{x}\log_{2}(x - 1)$. Its domain is $(1, +\infty)$. If we can prove that this function is decreasing for $x \ge 2$, then we'll be able to take $k = f(2) = 1$.

Indeed, we have

$$f'(x) = -\frac{\log_2(x - 1)}{x^2}$$

Now verify when $f'(x)$ is negative, meaning that $f(x)$ is decreasing.

Answer 2

HINT: try to start with $f(n) = \log_2(n) - \frac{n-1}{n} \log_2(n-1)$, then:

$$ 2^{f(n)} = \frac{n}{(n-1)^{\frac{n-1}{n}}} = \frac{n}{(n-1)}\times (n-1)^{1/n} $$

Prove that both of the terms are bounded.

Answer 3

At the outset, it's worth paying attention to the order of quantifiers. The question in the title is about finding a good $k$ for all $n$. Yet, you asked

Prove for $n≥2$ there exists constant $k$ such that $$\log_2(n)-\frac{n-1}{n}\log_2(n-1)\le k.$$

Which is a much simpler task, just $k=\log_2(n)-\frac{n-1}{n}\log_2(n-1)$ will do the job. Therefore, I'll assume it's about $k$ independent from $n$. Then, $$\begin{split} \log_2n-\frac{n-1}{n}\log_2(n-1)&=\log_2 \sqrt[n]{\frac{n^n}{(n-1)^{n-1}}}\\ &=\log_2 \sqrt[n]{\frac{n^{n-1}}{(n-1)^{n-1}}\times n}\\ &\le \log_2 2\sqrt[n]{n}. \end{split} $$ Whereas the last inequality comes from observation $$\Big(\frac{n}{n-1}\Big)^{\frac{n-1}{n}}\le 2,$$ which is the result of a simple observation that $x\le 2^x$, and set $x=n/(n-1)$. And finally we can say that $\sqrt[n]{n}$ is also bounded since, $\sqrt[n]{n}\to 1$.

Answer 4

Working with natural logarithms $$A_n=\log_2(n)-\frac{n-1}{n}\log_2(n-1)$$ $$A_n=\frac 1 {\log(2)}\left(\frac{\log (n)+1}{n}-\sum_{k=2}^\infty \frac 1{k(k-1)n ^k} \right)~<~\frac{\log (n)+1}{n\,\log(2)}$$

Now, you could use any upper bound of $\log(x)$ (have a look at table $(3)$ in this paper) to finish.

Answer 5

Here is another way to prove that

$\log_2n-\dfrac{n-1}n\log_2(n-1)\leqslant1\quad$ for any $\;n\in\Bbb N\,\land\,n\geqslant2\,.$

Proof :

For any $\;n\in\Bbb N\,\land\,n\geqslant2\,$ it results that

$\log_2n-\dfrac{n-1}n\log_2(n-1)=\dfrac1n\log_2\left[\dfrac{n^n}{(n-1)^{n-1}}\right]=$

$=\dfrac1n\log_2\left[\dfrac{\big((n\!-\!1)\!+\!1\big)^{\!n}}{(n-1)^{n-1}}\right]=\dfrac1n\log_2\left[\dfrac{\sum\limits_{k=0}^n\binom nk(n-1)^k}{(n-1)^{n-1}}\right]=$

$=\dfrac1n\log_2\left[\dfrac{1\!+\!n(n\!-\!1)\!+\!\sum\limits_{k=2}^{n-1}\binom nk(n\!-\!1)^k\!+\!(n\!-\!1)^n}{(n-1)^{n-1}}\right]=$

$=\dfrac1n\log_2\left[\dfrac{1\!+\!(n\!-\!1)^2\!+\!(n\!-\!1)\!+\!\sum\limits_{k=2}^{n-1}\binom nk(n\!-\!1)^k\!+\!n(n\!-\!1)^{n-1}\!-\!(n\!-\!1)^{n-1}\;}{(n-1)^{n-1}}\right]\leqslant$

$\require{cancel}\!\leqslant\!\dfrac1n\log_2\left[\dfrac{1\!+\!(n\!-\!\!1)^{n-1}\!+\!\color{#8888FF}{\cancel{\color{black}{\!(n\!-\!\!1)^{n-1}}}}\!\!+\!\!\sum\limits_{k=2}^{n-1}\!\binom nk(n\!-\!\!1)^k\!+\!n(n\!-\!\!1)^{n-1}\!-\!\!\color{#8888FF}{\cancel{\color{black}{(n\!-\!\!1)^{n-1}}}}}{(n-1)^{n-1}}\right]\!=$

$=\dfrac1n\log_2\left[\dfrac{\binom n0\!+\!\binom nn(n\!-\!1)^{n-1}\!+\!\sum\limits_{k=2}^{n-1}\binom nk(n\!-\!1)^k\!+\!\binom n1(n\!-\!1)^{n-1}\;}{(n-1)^{n-1}}\right]\leqslant$

$\leqslant\!\dfrac1n\log_2\left[\dfrac{\binom n0(n\!-\!1)^{n-1}\!+\!\binom nn(n\!-\!1)^{n-1}\!+\!\sum\limits_{k=2}^{n-1}\binom nk(n\!-\!1)^{n-1}\!+\!\binom n1(n\!-\!1)^{n-1}\;}{(n-1)^{n-1}}\right]\!=$

$=\dfrac1n\log_2\left[\dfrac{\color{#8888FF}{\cancel{\color{black}{(n-1)^{n-1}}}}\!\!\sum\limits_{k=0}^n\binom nk}{\color{#8888FF}{\cancel{\color{black}{(n-1)^{n-1}}}}}\right]=\displaystyle\dfrac1n\log_2\left[\sum\limits_{k=0}^n\binom nk\right]=$

$=\dfrac1n\log_2\bigg[\big(1+1\big)^n\bigg]=\dfrac1n\log_22^n=1\,.$