Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

How do we prove that $\Big[\sqrt n \Big]+ \sum_{j=1}^n \bigg[ \dfrac nj\bigg]$ is an even integer for all $ n \in \mathbb N$ ? (where $\Big[ \space \Big]$ denotes the "greatest integer" function)

share|cite|improve this question

marked as duplicate by Claude Leibovici, Davide Giraudo, Hakim, amWhy algebra-precalculus Nov 6 '14 at 12:23

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.

    
It looks like it is integer by definition... – Bach Mar 15 '14 at 14:06
    
@Bach: Yes , it is an integer ... – Souvik Dey Mar 15 '14 at 14:10
    
Sorry, I missed the even in your question. – Bach Mar 15 '14 at 14:13
    
This is INMO 2014 Question 2: olympiads.hbcse.tifr.res.in/subjects/mathematics/… – barto Apr 5 '15 at 21:12
up vote 6 down vote accepted

$\left[\frac{n}{j}\right]$ is the number of positive integers $k$ such that $k\cdot j \leqslant n$. Thus

$$\sum_{j=1}^n \left[\frac{n}{j}\right] = \sum_{j\cdot k \leqslant n} 1 = \sum_{m = 1}^n \left(\sum_{j\cdot k = m} 1\right) = \sum_{m=1}^n \tau(m),$$

where $\tau(m)$ is the number of divisors of $m$. Every positive integer that is not a perfect square has an even number of divisors, while a perfect square has an odd number of divisors. There are $\left[\sqrt{n}\right]$ perfect squares $\leqslant n$. Hence

$$\sum_{j=1}^n \left[\frac{n}{j}\right] \equiv \left[\sqrt{n}\right] \pmod{2}.$$

share|cite|improve this answer

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