Question

Let $n$ be a natural number. Prove that $\left[\frac{n}{1}\right]+\left[\frac{n}{2}\right]+\left[\frac{n}{3}\right]+......\left[\frac{n}{n}\right]+\left[\sqrt{n}\right]$ is even.

(Here $\left[x\right]$ denotes the largest integer smaller than or equal to $x$)

Answer 1

Let $f\left(n\right)$ denotes the given equation.
Then $f\left(1\right)=2$ which is even.
Now suppose that f(n) is even for some $n\ge 1$.
Then, $f(n+1)=\left[\frac{n+1}{1}\right]+\left[\frac{n+1}{2}\right]+\left[\frac{n+1}{3}\right]+......\left[\frac{n+1}{n+1}\right]+\left[\sqrt{n+1}\right]$ $=\left[\frac{n}{1}\right]+\left[\frac{n}{2}\right]+\left[\frac{n}{3}\right]+\left[\frac{n}{n}\right]+\left[\sqrt{n+1}\right]+\sigma (n+1)$, where $\sigma (n+1)$ denotes the number of positive divisors of $n+1$.
This follows from $\left[\frac{n+1}{k}\right]=\left[\frac{n}{k}\right]+1$ if $k$ divides $n+1$, and $\left[\frac{n+1}{k}\right]=\left[\frac{n}{k}\right]$ otherwise.
Note that $\left[\sqrt{n+1}\right]=\left[\sqrt{n}\right]$ unless $n+1$ is a square, in which case $\left[\sqrt{n+1}\right]=\left[\sqrt{n}\right]+1$.
On the other hand $\sigma (n+1)$ is odd if and only if $n+1$ is a square. Therefore it follows that $f(n+1)=f\left(n\right)+2l$ for some integer $l$.
$\therefore f(n+1)$ is even.
Thus it follows by induction that $f\left(n\right)$ is even for all natural number $n$.