4

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 $$

delta
  • 732
  • thx! I changed to floor – delta May 29 '13 at 15:41
  • 1
    Can you think about this in terms of counting multiples of $i$ less than $n$? – Pedro May 29 '13 at 15:43
  • 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. – delta May 29 '13 at 15:57

1 Answers1

2

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

albatross
  • 443