To prove that $ [n/1]+ [n/2]+[n/3]+\dots +[n/n]+[\sqrt{n}]$ is even. 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.
 A: 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.
A: 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.
