Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

This question is actually from a programming question that a formula is required to compute maths faster. (Please note that computer frequently rounds down to the nearest integer, thus the floor function is involved even if it is not explicitly stated in the question in the link)

So here is the formula I needed for the question:

For any positive integer $n$, Let $k=\lfloor\sqrt{n}\rfloor$. Prove that: $$ \sum_{i=1}^n \bigg\lfloor\frac{n}{i}\bigg\rfloor = 2\sum_{i=1}^k \bigg\lfloor\frac{n}{i}\bigg\rfloor - k^2 $$ I've verified this for $n$ up to $10000$ (by a computer) and got a (very) informal proof (which relies heavily on not-so-obvious assumptions). However, I wasn't able to obtain even a semi-informal proof, thus I've asked for help here.

P.S. I would like to have someone format the formula. I don't know how to do it. Thank you.

Edit: Thank you avraham for formatting that. Formatting a summation is much easier than I've expected!

share|improve this question
    
Please, consider editing your post to make it more visually appealing, perhaps formatting the math appropriately using $\LaTeX$ (see this page). Then you will probably get the response you are hoping for. Welcome to Math.SE! –  David Čepelík Sep 8 '13 at 15:07

1 Answer 1

up vote 0 down vote accepted

The sum of the floor function counts the integer points lying on or below a branch of the rectangular hyperbola $xy=n$ (for $x,y\gt 0$). Sketch this and add the square with corners $(0,0),(0,\sqrt n), (\sqrt n, 0), (\sqrt n, \sqrt n)$ (the last of these points lies on the hyperbola).

$k^2$ counts the points in the square, and the tails are symmetrical about $x=y$. The sum taken once counts the points in the tail, plus the points in the square (which are therefore counted twice when the sum is multiplied by $2$).

You should be able to turn these observations into a formal proof.

This is now the fourth time (at least) that a different form of question about this sum has been posed recently. The sum is equivalent to the sum of the divisor function $d(n)$, which counts the number of divisors of $n$.


Further note

If $(a,b)$ is below the hyperbola xy=n, so is $(b,a)$. Look at the sum on the right-hand side, taken once. It counts the number of points $(x,y)$ on the line $x=1$ with $0\lt xy \le n$ i.e. $\left\lfloor \frac n1 \right\rfloor$, the points with $x=2$ i.e. $\left\lfloor \frac n2 \right\rfloor$, up to the points with $x=k$ ie $\left\lfloor \frac nk \right\rfloor$.

Note that the points $(a,b)$ with $a,b \le k$ are all counted in this sum. No points with $a \gt k$ are counted.

The sum also counts the points in a similar way for $y=1, 2 \dots k$. This also has the points $(a,b)$ with $a,b\le k$ - we note there are $k^2$ of these, but has no points with $b\gt k$.

If we count the sum twice, we have counted all the points under the hyperbola, but there are $k^2$ points we have counted twice, so we subtract $k^2$ to avoid double-counting.

For other questions see this, and this.

share|improve this answer
    
Your "proof" is pretty much what I had for my informal proof and it's very hard to turn it into a formal proof. Also, if there are other questions about this sum, please post a link to at least one of them. I also don't understand what you said about d(n). –  Theemathas Chirananthavat Sep 9 '13 at 12:10
    
Have you drawn the diagram? I put a further note, which may help. I will try to find the links. –  Mark Bennet Sep 9 '13 at 17:38
    
Thanks. I've already drawn the diagram before asking this question. But for some reason, I wasn't able to get this proof! –  Theemathas Chirananthavat Sep 10 '13 at 10:59

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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