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

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,\, n\in \mathbb{N}$

For example. For $n=2$, we have $\lfloor 2^{1/2} \rfloor = \lfloor 1.414 \rfloor = 1$ whereas $\lfloor \log_2(2) \rfloor = 1$ while for $n=3$, we have $$\lfloor 3^{1/2} \rfloor + \lfloor 3^{1/3} \rfloor = \lfloor 1.732 \rfloor + \lfloor 1.442 \rfloor = 2= \lfloor 1.585 \rfloor + \lfloor 1 \rfloor=\lfloor \log_2(3) \rfloor + \lfloor \log_3(3) \rfloor .$$

I was thinking of using induction. So since $n=2$ is true, now assume for all $n$, this identity is true, we would like to prove that $n+1$ is true. Then

$$\lfloor n^{1/2} \rfloor + \lfloor n^{1/3} \rfloor + ... + \lfloor n^{1/n} \rfloor + \lfloor (n+1)^{1/(n+1)} \rfloor,$$ where $(n+1)^{1/(n+1)} > 1$ for all $n>1$ but it's strictly decreasing above 1 so $\lfloor (n+1)^{1/(n+1)} \rfloor = 1$

$\implies \lfloor n^{1/2} \rfloor + \lfloor n^{1/3} \rfloor +\cdots+ \lfloor n^{1/n} \rfloor + \lfloor (n+1)^{1/(n+1)} \rfloor = \lfloor n^{1/2} \rfloor + \lfloor n^{1/3} \rfloor +\cdots+ \lfloor n^{1/n} \rfloor + 1$

$= \lfloor \log_2(n) \rfloor + \lfloor \log_3(n) \rfloor + \cdots+ \lfloor \log_n(n) \rfloor + \lfloor \log_{n+1}(n+1) \rfloor$

since, $\log_{n+1}(n+1) = 1$ for all $n$.

My question is: How do we know that $(n+1)^{1/(n+1)}$ will never go below $1$? i.e., How can we prove that this function $f(x) = (x+1)^{1/(x+1)}$ is always bounded below by $1$ for $x>1$? (First, When $x=0$, $f(0)=1$, then looking at it's derivative, one can see that it's strictly increasing for $x$ between $(0,1)$ and decreasing for all $x>1$).

• You need to replace $n$ by $n + 1$ all over, not just in the last term, in the induction step. – vonbrand Feb 25 '14 at 21:57
• If $\llcorner x\lrcorner$ is supposed to mean the greatest integer not exceeding $x$, then you should probably have used $\lfloor x \rfloor$ (\lfloor … \rfloor) instead. If that's not what you mean, then what did you mean? – MJD Feb 25 '14 at 22:02
• thanks @MJD, I wasn't sure which code to use for it. Thanks! – PandaMan Feb 26 '14 at 1:37
• @vonbrand, I don't quite understand why you meant, please clarify. thanks – PandaMan Feb 26 '14 at 2:18
• @PandaMan, what you need to prove is $\lfloor (n+1)^{1/2}\rfloor + \ldots + \lfloor (n+1)^{1/(n+1)}\rfloor = \lfloor \log_2 (n+1)\rfloor +\ldots+\lfloor\log_{n+1} (n+1)\rfloor$ – vonbrand Feb 26 '14 at 5:04

## 2 Answers

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 (Всесоюзный Математический Олимпиад.)

• Gorgeous explanation! – Steven Stadnicki Feb 25 '14 at 22:24
• @StevenStadnicki: Correct. – Yiorgos S. Smyrlis Feb 25 '14 at 22:26
• (Thanks for the fix! I've removed the correction from my comment since that got edited in. :-) – Steven Stadnicki Feb 25 '14 at 22:28
• Great explanation. The wires are crossed a little though, because if $x=k$, then $y\leq n^{1/k}$, which means that the vertical count is the one that matches the fractional powers. Likewise, if $y = k$, then $k \leq n^{1/x}$, then $1\leq(\log_k n)/x$, so the horizontal count is the one that matches the logs. – Josephine Moeller Mar 1 '14 at 0:13
• Awesome solution :-) – tarit goswami Aug 1 '18 at 8:54

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