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{align*} 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{align*} \]

which is precisely the original claim. \(\blacksquare\)

No vote yet

1 vote

×

Problem Loading...

Note Loading...

Set Loading...

Easy Math Editor

`*italics*`

or`_italics_`

italics`**bold**`

or`__bold__`

boldNote: you must add a full line of space before and after lists for them to show up correctlyparagraph 1

paragraph 2

`[example link](https://brilliant.org)`

`> This is a quote`

Remember to wrap math in \( ... \) or \[ ... \] to ensure proper formatting.`2 \times 3`

`2^{34}`

`a_{i-1}`

`\frac{2}{3}`

`\sqrt{2}`

`\sum_{i=1}^3`

`\sin \theta`

`\boxed{123}`

## Comments

There are no comments in this discussion.