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:

log2n+log3n+log4n++lognn=n+n3+n4++nn, \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 nn 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×nn \times n grid and label the columns 1 to nn from right to left, and the rows 1 to nn from top to bottom:

123n123n \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 xxth row and yyth column with the number xyx^y:

123n11112131n22122232n33132333nnn1n2n3nn \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.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.x. Observe that xlogxn=n,x^{\log_xn} = n, so columns with value logxn\log_x n and below will produce entries that are less than or equal to n.n. This gives us logxn\lfloor \log_x n \rfloor entries in the row that are less than or equal to n.n. For row 1, all nn entries are clearly less than or equal to n,n, so the total number of entries in the grid that are less than or equal to nn is n+i=2nlogin.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,y, then because (n1/y)y=n,(n^{1/y})^y = n, all rows that are of value n1/yn^{1/y} and below produce entries less than or equal to n.n. This gives us ny\lfloor \sqrt[y]{n} \rfloor total entries in column y.y. Combined with the nn entries in column 1, the total number of entries in the grid that are less than or equal to nn is n+i=2nni.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:

n+i=2nlogin=n+i=2nnii=2nlogin=i=2nni, \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

Note by Steven Yuan
1 year, 4 months ago

No vote yet
1 vote

</code>...<code></code> ... <code>.">   Easy Math Editor

MarkdownAppears as
*italics* or _italics_ italics
**bold** or __bold__ bold

- bulleted
- list

  • bulleted
  • list

1. numbered
2. list

  1. numbered
  2. list
Note: you must add a full line of space before and after lists for them to show up correctly
paragraph 1

paragraph 2

paragraph 1

paragraph 2

[example link](https://brilliant.org)example link
> This is a quote
This is a quote
    # I indented these lines
    # 4 spaces, and now they show
    # up as a code block.

    print "hello world"
# I indented these lines
# 4 spaces, and now they show
# up as a code block.

print "hello world"
MathAppears as
Remember to wrap math in </span>...<span></span> ... <span> or </span>...<span></span> ... <span> to ensure proper formatting.
2 \times 3 2×3 2 \times 3
2^{34} 234 2^{34}
a_{i-1} ai1 a_{i-1}
\frac{2}{3} 23 \frac{2}{3}
\sqrt{2} 2 \sqrt{2}
\sum_{i=1}^3 i=13 \sum_{i=1}^3
\sin \theta sinθ \sin \theta
\boxed{123} 123 \boxed{123}

Comments

There are no comments in this discussion.

×

Problem Loading...

Note Loading...

Set Loading...