A Nice Croatian Math Olympiad problem with $\log_k$ and $k^{th}$ roots

 For a positive integer $n \ge 2$, prove that

$$\left[\log_2 n\right] + \left[\log_3 n\right] + \dots + \left[\log_n n\right] = \left[\sqrt{n}\right] + \left[\sqrt[3]{n}\right] + \dots + \left[\sqrt[n]{n}\right]$$

$[x]$ is the integer part of $x$

Scroll down for a solution.

.

.

.

.

.

.

Solution:

We will show that this equality is basically saying that the sum of sums of rows = sum of sums of columns in a matrix, for a certain matrix.

Consider the $n \times n $ matrix $A$ such that the entry of row $m$ and column $k$ is $1$ if $$\sqrt[m]{n} \ge k$$ and $0$ otherwise.

Since $\sqrt[m]{n} \le n$,  row $m$ has exactly $$\left[\sqrt[m]{n}\right]$$ ones

Thus the sum of sum of rows is

$$ n + \left[\sqrt{n}\right] + \left[\sqrt[3]{n}\right] + \dots + \left[\sqrt[n]{n}\right]$$

Now let us try to count the number of ones in column $k$.

For $k=1$, the numbers of ones is exactly $n$, because $\sqrt[m]{n} \ge 1$ for any $m \ge 1$.

For $k \ge 2$, number of ones will be all the $m$ that satisfy $1 \le m \le n$ and

$$ \sqrt[m]{n} \ge k$$

i.e number of $1 \le m \le n$ such that

$$ \log_k n \ge m$$

Since for $2 \le k$, $\log_k n \le n$, there are exactly $$\left[\log_k n\right]$$ ones in column $k$ 

Therefore the sum of sums of columns is

$$ n + \left[\log_2 n\right] + \left[\log_3 n\right] + \dots + \left[\log_n n\right] $$

Now equating the sum of sums of rows to the sum of sums of columns gives us the result.