# To prove that $[n/1]+ [n/2]+[n/3]+\dots +[n/n]+[\sqrt{n}]$ is even. [duplicate]

Let $n$ be a natural number. How do you prove that

$$\lfloor n/1 \rfloor+ \lfloor n/2\rfloor+ \lfloor n/3\rfloor+\dots +\lfloor n/n]+\lfloor \sqrt{n}\rfloor$$

is even? Thanks.

## marked as duplicate by Claude Leibovici, Davide Giraudo, Joel Reyes Noche, Jean-Claude Arbaut, Joonas IlmavirtaNov 6 '14 at 13:14

• Use $\large\left\lfloor x\right\rfloor$ instead of $\large\left[x\right]$. The $\large\tt LaTeX$ code is $\large\verb=\left\lfloor x\right\rfloor=$ – Felix Marin Mar 4 '14 at 5:32
• $[x]$ is also OK. Maybe a bit out of date. No real need to change. – David Mar 4 '14 at 5:34
• Guys if it's any help, I checked the given expression on a program, it seems to evaluate to 2n. Ideas? – Guy Mar 4 '14 at 5:44
• @Sabyasachi For $n=4$ it is $10$ not $2\times 4$ – Ewan Delanoy Mar 4 '14 at 5:46
• This is question 2 from this year's Indian National Mathematical Olympiad, see olympiads.hbcse.tifr.res.in/subjects/mathematics/… (INMO 2014). This has been asked before on MSE but I can't find the link. – nbarto Mar 4 '14 at 9:47

Here is a sketch of an argument, see if you can generalise and fill in the details. We illustrate the sum $$\Bigl[\frac{n}{1}\Bigr]+\Bigl[\frac{n}{2}\Bigr]+\cdots+\Bigl[\frac{n}{n}\Bigr]$$ by a pattern of dots, where the number of dots in column $j$ is equal to $[n/j]$. If say $n=6$ it will look like this, $$\matrix{\bullet\cr \bullet\cr \bullet\cr \bullet&\bullet\cr \bullet&\bullet&\bullet\cr \bullet&\bullet&\bullet&\bullet&\bullet&\bullet\cr}$$ and for future reference we label the rows and columns as shown: $$\matrix{6&\bullet\cr 5&\bullet\cr 4&\bullet\cr 3&\bullet&\bullet\cr 2&\bullet&\bullet&\bullet\cr 1&\bullet&\bullet&\bullet&\bullet&\bullet&\bullet\cr &1&2&3&4&5&6\cr}$$

If you draw a few more examples it seems clear that the pattern is symmetric about the diagonal. To show that this is in fact true, note that there is a dot in row $i$, column $j$ if and only if $$i\le\frac{n}{j}\ ,$$ and this is the same as saying that there is a dot in row $j$, column $i$. Now ignore the dots on the diagonal, for example, $$\matrix{\bullet\cr \bullet\cr \bullet\cr \bullet&\bullet\cr \bullet&\circ&\bullet\cr \circ&\bullet&\bullet&\bullet&\bullet&\bullet\cr}$$ By symmetry, the remaining dots are even in number.

Now how many dots are there on the diagonal? There is a dot at $(i,i)$ if and only if $i\le n/i$, if and only if $i^2\le n$, if and only if $i\le[\sqrt n]$. So the number of dots on the diagonal is $[\sqrt n]$. Putting all this together shows that the number in the problem is even.

• this is inspired. – Guy Mar 4 '14 at 5:51

Let $f(n)$ be the sum. It is useful to rewrite it as

$$f(n) = [\sqrt{n}] + \sum_{k=1}^{+\infty} [n/k]$$

What is $f(n) - f(n-1)$? The differences in the two formulas are:

• Each of the terms $[n/k]$ is one larger than $[(n-1)/k]$ if and only if $k | n$. (this includes $k=n$)
• If $n$ is a perfect square, then $[\sqrt{n}]$ is one larger than $[\sqrt{n-1}]$.

The effect of the first bullet adds $1$ for every factor of $n$. Most numbers have an even number of factors (e.g. if $x$ divides $n$, then so does $n/x$). The only exceptions are the perfect squares, which have an odd number of factors, but those are precisely the times when the second bullet point adds $1$.

Thus, $f(n) - f(n-1)$ is always even.

• I am having trouble I am having trouble understanding your first bullet point. I would understand it if it said “Each of the terms $[n/k]$ where $k$ is one larger than $[(n-1)/k]$”, but the $k|n$ is confusing me. I understand $k|n$ as a proposition, not as an arithmetic term. What did you mean by that? – MJD Mar 4 '14 at 14:54
• @MJD: I assert that $[n/k] = [(n-1)/k]$ if and only if $k$ does not divide $n$. Otherwise $[n/k] = [(n-1)/k] + 1$. – Hurkyl Mar 4 '14 at 16:30
• So you meant “Where $k|n$, each of the terms $[n/k]$ is one larger than $[(n-1)/k]$?” – MJD Mar 4 '14 at 16:35
• @MJD: Ah, I see the problem. I've inserted two commas to help with parsing. Bah, but that makes the phrasing awkward too. I need to reorganize that statement. – Hurkyl Mar 4 '14 at 16:37
• Thanaks very much. – MJD Mar 4 '14 at 16:38