Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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|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 at 21:57
1  
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 at 22:02
    
thanks @MJD, I wasn't sure which code to use for it. Thanks! –  PandaMan Feb 26 at 1:37
    
@vonbrand, I don't quite understand why you meant, please clarify. thanks –  PandaMan Feb 26 at 2:18
1  
@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 at 5:04

2 Answers 2

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

share|improve this answer
1  
Gorgeous explanation! –  Steven Stadnicki Feb 25 at 22:24
    
@StevenStadnicki: Correct. –  Yiorgos S. Smyrlis Feb 25 at 22:26
    
(Thanks for the fix! I've removed the correction from my comment since that got edited in. :-) –  Steven Stadnicki Feb 25 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 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|improve this answer

Your Answer

 
discard

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.