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.

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|improve this question

marked as duplicate by Claude Leibovici, Davide Giraudo, Hakim, amWhy 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

1 Answer 1

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|improve this answer

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