INMO Problem with even function proof.

Question

Let $n$ be a natural number. Show that $$\left[ \frac{n}{1} \right ] + \left[ \frac{n}{2} \right ] + \left[ \frac{n}{3} \right ] + \cdots + \left[ \frac{n}{n} \right ] + [\sqrt{n}]$$ is even. Here $[x]$ means the greatest integer less than or equal to $x$.

Let $$f(n) = [\sqrt{n}] + \sum_{k=1}^{n} \left[ \frac{n}{k} \right]$$

$$f(1) = [1] + [1] = 2 \checkmark$$

The statement for $f(n+1)$ is to be proved:

$$f(n+1) = [\sqrt{n+1}] + \sum_{k=1}^{n+1} \left[\frac{n+1}{k} \right]$$

I just need some hints from now?

Answer 1

Hint: Prove by induction.

When is $ \lfloor \frac{n}{k} \rfloor \neq \lfloor \frac{n+1}{k} \rfloor $?
When they are not equal, what is the difference of these 2 terms?

Ans: The terms are different if there exists some integer $i$ such that $ \frac{n}{k} < i \leq \frac{ n+1}{k}$. Multiplying throughout by $k$, we get $ n < ik \leq n+1$. Since $n$, $n+1$ are consecutive integers, this then implies that $ik = n+1$, or that $k$ is a divisor of $n+1$.
Thus, this term increases by 1 if $k \mid n+1$. Otherwise, it stays constant.

---

Hence, letting $ g(n) = \sum_{i=1}^n \lfloor \frac{n}{k} \rfloor$, we get that

$$g(n+1) - g(n) = \text{ number of divisors of } n$$

Answer 2

HINT: One way is to prove by induction on $n$ that

$$\sum_{k=1}^n\left\lfloor\frac{n}k\right\rfloor=\sum_{k=1}^nd(k)\;,$$

where $d(k)$ is the number of (positive) divisors of $k$. For what values of $n$ does this change parity?