Let $S$ be the set of all ordered pairs $(a,b)$ of positive integers greater than $1$ such that $a^b \leq n$. We count the number of elements of $S$ in two ways. First, consider all solutions to $a^b \leq n$ for a fixed $a$. This is equivalent to $ b \leq \log_a n$, so there are $\lfloor \log_a n \rfloor - 1$ solutions for each $a$ from 2 to $n$. Then consider all solutions to $a^b \leq n$ for a fixed $b$. This is equivalent to $a \leq \sqrt[b]{n}$, so there are $\lfloor \sqrt[b]{n} \rfloor - 1$ solutions for each $b$ from 2 to $n$. Summing up over all $a$ and all $b$ for each counting method shows \[\sum_{k=2}^n (\lfloor \sqrt[k]{n} \rfloor - 1) = \sum_{k=2}^n (\lfloor \log_k n \rfloor - 1),\] which is equivalent to what we want.

Shorter, given a boolean predicate $\mathcal{P}$, we shall use the notation popularized by D. Knuth $[[\mathcal{P}]] =1$ if $\mathcal{P}$ is true, while $[[\mathcal{P}]]=0$ if $\mathcal{P}$ is false. Then $\displaystyle \sum_{k=2}^n \left \lfloor \sqrt[k]{n}\right \rfloor =\sum_{k=2}^n \Big ( 1+\sum_{\ell=2}^n [[\ell^{k} \leq n]] \Big ) = \sum_{\ell=2}^n \Big ( 1+\sum_{k=2}^n [[\ell^{k} \leq n]] \Big ) = \sum_{\ell=2}^n \left \lfloor \log_{\ell} n \right \rfloor$.

No! I can't believe this! This problem is part of a Romanian book - "200 Identities with [X]" by M. Onucu-Drimbe.

Well, do believe it! The problem setters of these tests, for the last year, this year, and I fear next year(s), are just not getting their hands on any original problems. Tests are prepared mostly on the eve of the contest day, errors occur, difficulty of problems is often misjudged, grading is as poor, if not worse, etc.

Define this functions:\[f(x,y)=\left \lfloor \sqrt[x]{y} \right \rfloor,x,y\in \mathbb {N}:x,y\ge 2\]\[g(x,y)=\left \lfloor log_xy\right \rfloor,x,y\in \mathbb {N}:x,y\ge 2\]\[P(x)=\sum_{k=2}^{x}f(k,x),x\in \mathbb {N}:x\ge 2\]\[Q(x)=\sum_{k=2}^{x}g(k,x),x\in \mathbb {N}:x\ge 2\] We'll use the method of induction here. 1.By checking first a few cases, base case is true. 2.Now let for some $m\ge 2$, $P(m)=Q(m)$. 3.Let $m+1$ is a perfect power for $\alpha$ distinct positive integers. Notice that there are two choices, namely $f(k,m)+1=f(k,m+1)$ or $f(k,m)=f(k,m+1)$ occurs respectively whether $m+1$ is a perfect $k$th power or not.So\[P(m+1)=P(m)+1+1+...+1\; (\alpha \; \; times)=P(m)+\alpha \] Also notice $g(k,m)+1=g(k,m+1)$ or $g(k,m)=g(k,m+1)$ occurs respectively whether $m+1$ is a perfect power of $k$ or not.So \[Q(m+1)=Q(m)+1+1+...+1\; (\alpha \; \; times)=Q(m)+\alpha \] Therefore $P(m+1)=Q(m+1)$ as desired.

We prove the desired result by induction. First, the base case which is $n = 2$. Then we have $\lfloor\sqrt{2}\rfloor = \lfloor\log_{2} 2\rfloor = 1$, so our base case is proven. Next, for the inductive step. Assume that $$\sum_{k=2}^n \lfloor \sqrt[k]{n}\rfloor=\sum_{k=2}^n\lfloor\log_{k}n\rfloor$$is true for $n$. We prove it is true for $n+1$. Observe that $\lfloor\sqrt[k]{n}\rfloor$ can only increase by $1$ when $n$ is a perfect $kth$ power. Similarly, $\lfloor \log_{k} n\rfloor$ can only increase by $1$ when $n$ is a power of $k$. For all the $\lfloor \sqrt[k]{n+1}\rfloor$ which increases by $1$ from $\lfloor \sqrt[k]{n}\rfloor$, because $n+1 = c^{k}$ for some $c$ we have $\lfloor\log_{c} n\rfloor$ increase by $1$ as well. This implies a bijection for all $\lfloor\sqrt[k]{n}\rfloor$ that increase by $1$ to all $\lfloor\log_{k}n\rfloor$ that increase by $1$, therefore $$\sum_{k=2}^{n+1} \lfloor \sqrt[k]{n+1}\rfloor=\sum_{k=2}^{n+1}\lfloor\log_{k}n+1\rfloor$$is true as well. Our induction is complete, so we know that it is true for all $n$.