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.

Solution 1:

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.

Solution 2:

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.