Prove that: $\lfloor n^{1/2}\rfloor+\cdots+\lfloor n^{1/n}\rfloor=\lfloor \log_2n\rfloor +\cdots+\lfloor \log_nn \rfloor$, for $n > 1$

Solution 1:

This is a classic exercise and one with a very elegant solution.

The idea of the proof is to count the number $N$ of the points (see figure below) with integer coordinates, which lie in the region $$ U=\big\{(x,y): 0<x\le n \,\,\,\text{and}\,\,\, 1<y\le n^{1/x}\big\}, $$ and in particular, the red points, in two ways: horizontally and vertically.

Horizontal counting: $$ N=\lfloor n^{1/2}\rfloor+\lfloor n^{1/3}\rfloor+\cdots+\lfloor n^{1/n}\rfloor, $$ since on the horizontal line $\,y=k\,$ lie exactly $\,\lfloor n^{1/k}\rfloor\,$ red points.

Vertical counting: $$ N=\lfloor \log_2 n\rfloor+\lfloor\log_3 n\rfloor+\cdots+\lfloor \log_n n\rfloor, $$ since on the vertical line $\,x=k\,$ lie exactly $\,\lfloor \log_k n\rfloor\,$ red points.

$$ {} $$

Note that the curve in the figure above is of the function $y=n^{1/x}$.

This problem was first asked in a Soviet Mathematics Olympiad in 1982 (Всесоюзный Математический Олимпиад.)

Solution 2:

Fix $b>1$. Then the derivative of $b^x$ is $\ln(b) b^x$; $\ln(b)$ is positive and $b^x$ is as well for all $x$, showing that that $b^x$ is a strictly increasing function. Next, $b^0=1$, showing that $b^x>1$ for all $x>0$.

Next, since $n+1>1$ and $1/(n+1)>0$, we have that $(n+1)^{1/(n+1)}>1$.