12
$\begingroup$

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

$\endgroup$
  • $\begingroup$ You need to replace $n$ by $n + 1$ all over, not just in the last term, in the induction step. $\endgroup$ – vonbrand Feb 25 '14 at 21:57
  • 1
    $\begingroup$ 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? $\endgroup$ – MJD Feb 25 '14 at 22:02
  • $\begingroup$ thanks @MJD, I wasn't sure which code to use for it. Thanks! $\endgroup$ – PandaMan Feb 26 '14 at 1:37
  • $\begingroup$ @vonbrand, I don't quite understand why you meant, please clarify. thanks $\endgroup$ – PandaMan Feb 26 '14 at 2:18
  • 1
    $\begingroup$ @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$ $\endgroup$ – vonbrand Feb 26 '14 at 5:04
30
$\begingroup$

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

$\endgroup$
  • 3
    $\begingroup$ Gorgeous explanation! $\endgroup$ – Steven Stadnicki Feb 25 '14 at 22:24
  • $\begingroup$ @StevenStadnicki: Correct. $\endgroup$ – Yiorgos S. Smyrlis Feb 25 '14 at 22:26
  • $\begingroup$ (Thanks for the fix! I've removed the correction from my comment since that got edited in. :-) $\endgroup$ – Steven Stadnicki Feb 25 '14 at 22:28
  • 1
    $\begingroup$ 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. $\endgroup$ – John Moeller Mar 1 '14 at 0:13
  • $\begingroup$ Awesome solution :-) $\endgroup$ – tarit goswami Aug 1 '18 at 8:54
2
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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