Double Counting on the Floor

Hey, Brilliant!

Today, I went to an AIME preparation day camp, and the instructor showed us a really neat proof of the following assertion:

\[ \lfloor \log_2 n \rfloor + \lfloor \log_3 n \rfloor + \lfloor \log_4 n \rfloor + \cdots + \lfloor \log_n n \rfloor = \lfloor \sqrt{n} \rfloor + \lfloor \sqrt[3]{n} \rfloor + \lfloor \sqrt[4]{n} \rfloor + \cdots + \lfloor \sqrt[n]{n} \rfloor, \]

where $n$ is a positive integer greater than 1. If you want, you can stop reading right here and see if you can come up with a proof of the statement yourself. The proof I was shown begins after the line break below.

.

.

.

.

.

.'

.

.

.

.

.

.

OK, so here's the proof. First, let’s draw an $n \times n$ grid and label the columns 1 to $n$ from right to left, and the rows 1 to $n$ from top to bottom:

$\begin{array}{c|c|c|c|c|c} & 1 & 2 & 3 & \cdots & n \\ \hline 1 & & & & & \\ \hline 2 & & & & & \\ \hline 3 & & & & & \\ \hline \vdots & & & & & \\ \hline n & & & & & \\ \end{array}$

We fill the entry on the $x$th row and $y$th column with the number $x^y$:

$\begin{array}{c|c|c|c|c|c} & 1 & 2 & 3 & \cdots & n \\ \hline 1 & 1^1 & 1^2 & 1^3 & \cdots & 1^n \\ \hline 2 & 2^1 & 2^2 & 2^3 & \cdots & 2^n \\ \hline 3 & 3^1 & 3^2 & 3^3 & \cdots & 3^n \\ \hline \vdots & \vdots & \vdots & \vdots & \ddots & \vdots \\ \hline n & n^1 & n^2 & n^3 & \cdots & n^n \\ \end{array}$

Now, we will count the total number of entries in this grid that are less than or equal to $n.$ We will do this in two different ways: counting row by row, and counting column by column.

For the row by row method, let’s focus on a specific row $x.$ Observe that $x^{\log_xn} = n,$ so columns with value $\log_x n$ and below will produce entries that are less than or equal to $n.$ This gives us $\lfloor \log_x n \rfloor$ entries in the row that are less than or equal to $n.$ For row 1, all $n$ entries are clearly less than or equal to $n,$ so the total number of entries in the grid that are less than or equal to $n$ is $n + \displaystyle \sum_{i = 2}^n \lfloor \log_i n \rfloor.$

The column by column method works the same way. If we choose a specific column $y,$ then because $(n^{1/y})^y = n,$ all rows that are of value $n^{1/y}$ and below produce entries less than or equal to $n.$ This gives us $\lfloor \sqrt[y]{n} \rfloor$ total entries in column $y.$ Combined with the $n$ entries in column 1, the total number of entries in the grid that are less than or equal to $n$ is $n + \displaystyle \sum_{i = 2}^n \lfloor \sqrt[i]{n} \rfloor.$

Since both methods counted the same thing, we can equate the final expressions we got:

$\begin{aligned} n + \displaystyle \sum_{i = 2}^n \lfloor \log_i n \rfloor &= n + \displaystyle \sum_{i = 2}^n \lfloor \sqrt[i]{n} \rfloor \\ \displaystyle \sum_{i = 2}^n \lfloor \log_i n \rfloor &= \displaystyle \sum_{i = 2}^n \lfloor \sqrt[i]{n} \rfloor, \end{aligned}$

which is precisely the original claim. $\blacksquare$