4
$\begingroup$

How to prove this summation without mathematical induction? Thanks a lot! I can't figure out a way to reduce n to $\sqrt{n}$.

$$ \sum_{i=1}^{n}\left\lfloor \frac{n}{i} \right\rfloor = 2\sum_{i=1}^{\left\lfloor \sqrt{n} \right\rfloor}\left\lfloor \frac{n}{i} \right\rfloor - \lfloor \sqrt{n} \rfloor ^2 $$


UPD: I think I got one proof, thanks to all, especially peter's idea.

let f(n) denote the numbers of n, then $\sum_{i=1}^{n}\left\lfloor \frac{n}{i} \right\rfloor=\sum_{i=1}^{n}f(i)$, because $\left\lfloor \frac{n}{i} \right\rfloor$ can be viewed as $i,2i...\left\lfloor \frac{n}{i} \right\rfloor i \leq n$, i's multiple, we can also consider i as some number's divisors, it appears the same time which is $\left\lfloor \frac{n}{i} \right\rfloor$.

then we calcuate f(n), if $a\vert n$ then $\frac{n}{a}\vert n$, it's one to one, then $f(n)=2\sum_{i\leq \sqrt{n}, i\vert n}1$. But there is one exception, that is when n is a square number, it counted twice, let's denote g(n)=1 if n is square, else g(n)=0. then:

$$ f(n) = 2\sum_{i\leq \sqrt{n}, i\vert n}1 - g(n) $$

thus we get

$$ \sum_{i=1}^{n}\left\lfloor \frac{n}{i} \right\rfloor =\sum_{i=1}^{n}f(i) =\sum_{i=1}^{n}(2\sum_{j\leq \sqrt{i}, j\vert i}1 - g(i)) =2\sum_{i=1}^{n}(\sum_{j\leq \sqrt{i}, j\vert i}1) - \sum_{i=1}^{n}g(i) $$

we do subscript changing and got:

$$ \sum_{i=1}^{n}(\sum_{j\leq \sqrt{i}, j\vert i}1) =\sum_{j=1}^{\left\lfloor \sqrt{n} \right\rfloor}\sum_{i\geq j^2,j\vert i}1 =\sum_{j=1}^{\left\lfloor \sqrt{n} \right\rfloor}\sum_{k=j}^{\left\lfloor \frac{n}{j} \right\rfloor}1 =\sum_{j=1}^{\left\lfloor \sqrt{n} \right\rfloor}(\left\lfloor \frac{n}{j} \right\rfloor-j+1)\\ =\sum_{i=1}^{\left\lfloor \sqrt{n} \right\rfloor}\left\lfloor \frac{n}{i} \right\rfloor-\sum_{i=1}^{\left\lfloor \sqrt{n} \right\rfloor}(i-1) =\sum_{i=1}^{\left\lfloor \sqrt{n} \right\rfloor}\left\lfloor \frac{n}{i} \right\rfloor-\left\lfloor \sqrt{n} \right\rfloor(\left\lfloor \sqrt{n} \right\rfloor-1)/2 $$

so we got:

$$ 2\sum_{i=1}^{n}(\sum_{j\leq \sqrt{i}, j\vert i}1) - \sum_{i=1}^{n}g(i) =2(\sum_{i=1}^{\left\lfloor \sqrt{n} \right\rfloor}\left\lfloor \frac{n}{i} \right\rfloor-\left\lfloor \sqrt{n} \right\rfloor(\left\lfloor \sqrt{n} \right\rfloor-1)/2)-\left\lfloor \sqrt{n} \right\rfloor\\ =2\sum_{i=1}^{\left\lfloor \sqrt{n} \right\rfloor}\left\lfloor \frac{n}{i} \right\rfloor - \lfloor \sqrt{n} \rfloor ^2 $$

$\endgroup$
  • $\begingroup$ thx! I changed to floor $\endgroup$ – delta May 29 '13 at 15:41
  • 1
    $\begingroup$ Can you think about this in terms of counting multiples of $i$ less than $n$? $\endgroup$ – Pedro Tamaroff May 29 '13 at 15:43
  • $\begingroup$ Ah, yes! I got one. consider f(n) as the number of divisors of n, then if ab=n,a<=b, then a<=$\sqrt{n}$ , so $f(n)=2\sum_{i\leq \sqrt{n},i\vert n}1$ if n is not a square, else we should minus 1, which lead to the $-\sqrt{n}$, then sum it up we get the answer. $\endgroup$ – delta May 29 '13 at 15:57
2
$\begingroup$

You can see why this holds from the graph of the hyperbola:

enter image description here

The sum $$\sum_{i=1}^{n}\left\lfloor \frac{n}{i} \right\rfloor$$ counts the area under this curve while the sum $$2\sum_{i=1}^{\left\lfloor \sqrt{n} \right\rfloor}\left\lfloor \frac{n}{i} \right\rfloor - \lfloor \sqrt{n} \rfloor ^2$$ counts the area below the square and one leg of the hyperbola twice, then takes away the square which was double counted.


The prove this notice we can write the sum as a sum over divisors $$\sum_{i \le n} d(i) = \sum_{i \le n} \sum_{d|i} 1 = \sum_{dk \le n} 1 = \sum_{i \le n}\left\lfloor \frac{n}{i} \right\rfloor$$

it is the second last form which shows the same symmetry we noticed geometrically, so we can use that one to prove the identity: Just split the sum up like this $$\sum_{dk \le n} = \sum_{\begin{array}{c}d \le \lfloor \sqrt{n} \rfloor \\ dk \le n\end{array}}+\sum_{\begin{array}{c}k \le \lfloor \sqrt{n} \rfloor \\ dk \le n\end{array}}-\sum_{\begin{array}{c}d \le \lfloor \sqrt{n} \rfloor \\ k \le \lfloor \sqrt{n} \rfloor\end{array}}$$ and we are done

$\endgroup$
  • $\begingroup$ Thanks! Using graph is brilliant! It makes it easy to see. $\endgroup$ – delta May 29 '13 at 16:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.