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$).
\lfloor … \rfloor
) instead. If that's not what you mean, then what did you mean? $\endgroup$ – MJD Feb 25 '14 at 22:02