Summing minimums with floor function

63 Views Asked by At

Prove that for any positive integers $x, m, n$:

$$\sum_{i=1}^n\min\left(\left\lfloor\frac{x}{i} \right\rfloor,m\right)=\sum_{i=1}^m\min\left(\left\lfloor\frac{x}{i}\right\rfloor,n\right)$$

Intuitively this kind of sounds like it would be correct, but I am not sure how to write the proof to put it into words. I was thinking of doing casework on when $\min(\lfloor \frac{x}{i}\rfloor,m)$ changes to $m$, but then I got stuck.

1

There are 1 best solutions below

0
On BEST ANSWER

On a $yz$-plane (not reusing the letter $x$), consider the region

$$\begin{cases} 0 < y \le m\\ 0 < z \le n\\ yz \le x\\ \end{cases}$$

and count the number of integer lattice points inside that region. Counting points along the $y$ or $z$ directions give the two sides of the equation:

  • When adding the lattice points for each $y$, the region can also be written as:

    $$\begin{cases} 0 < y \le m\\ 0 < z \le \min\left(\frac x y, n\right)\\ \end{cases}$$

    So the sum is $\sum_{y = 1}^m \min\left(\left\lfloor\frac x y\right\rfloor, n\right)$.

  • Similarly, when adding the lattice points for each $z$, the region can be written as: $$\begin{cases} 0 < z \le n\\ 0 < y \le \min\left(\frac x z, m\right)\\ \end{cases}$$

    So the sum is $\sum_{z = 1}^n \min\left(\left\lfloor\frac x z\right\rfloor, n\right)$.

The same sum represented in the two ways is equal.