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.

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.

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

2 Answers 2

up vote 36 down vote accepted

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.

share|improve this answer
7  
this is inspired. –  Sabyasachi Mar 4 at 5:51
    
I don't easily vote up answers, but this one is exceptionally beautiful. –  barto Mar 4 at 9:41

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.

share|improve this answer
    
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 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 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 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 at 16:37
    
Thanaks very much. –  MJD Mar 4 at 16:38

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.