Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

share|cite|improve this question
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
up vote 29 down vote accepted

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.

$$ {} $$

enter image description here

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

share|cite|improve this answer
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. – John Moeller Mar 1 '14 at 0:13

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

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.