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 Ilmavirta Nov 6 '14 at 13:14

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • 2
    $\begingroup$ 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=$ $\endgroup$ – Felix Marin Mar 4 '14 at 5:32
  • 9
    $\begingroup$ $[x]$ is also OK. Maybe a bit out of date. No real need to change. $\endgroup$ – David Mar 4 '14 at 5:34
  • $\begingroup$ Guys if it's any help, I checked the given expression on a program, it seems to evaluate to 2n. Ideas? $\endgroup$ – Guy Mar 4 '14 at 5:44
  • $\begingroup$ @Sabyasachi For $n=4$ it is $10$ not $2\times 4$ $\endgroup$ – Ewan Delanoy Mar 4 '14 at 5:46
  • 2
    $\begingroup$ 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. $\endgroup$ – 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.

  • 8
    $\begingroup$ this is inspired. $\endgroup$ – 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.

  • $\begingroup$ 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? $\endgroup$ – MJD Mar 4 '14 at 14:54
  • $\begingroup$ @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$. $\endgroup$ – Hurkyl Mar 4 '14 at 16:30
  • $\begingroup$ So you meant “Where $k|n$, each of the terms $[n/k]$ is one larger than $[(n-1)/k]$?” $\endgroup$ – MJD Mar 4 '14 at 16:35
  • $\begingroup$ @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. $\endgroup$ – Hurkyl Mar 4 '14 at 16:37
  • $\begingroup$ Thanaks very much. $\endgroup$ – MJD Mar 4 '14 at 16:38

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