Proving $\sum\limits_{k=0}^{n-1} \Bigl[x + \frac{k}{n}\Bigr] = [nx]$

Right, this is an exercise in Apostol, which i am not being able to solve. I was able to prove this result for a small case, that is the case when $n=2$, $[x] + \Bigl[x + \frac{1}{2}\Bigr]=[2x]$, but i am struggling with the generalization.

Prove that $$\sum\limits_{k=0}^{n-1} \Biggl[x + \frac{k}{n}\Biggr] = [nx]$$, where $[ \ ]$ denotes the greatest integer function.

Can this be proved via induction, i ask this because i have shown it to bealready true for $n=2$.

-

Both sides are equal since they count the same set: the RHS counts naturals $\rm\:\le n\:x\:$. The LHS counts them in a unique mod $\rm\ n\$ representation, $\:$ viz. $\rm\ \: j \:\le\: x+k/n\: \iff \ j\:n-k \:\le\: n\:x\:,\ \ j>0 \le k < n\:$.

REMARK $\:$ That every natural has a unique representation of form $\rm \: j\:n-k \ \ \:$ where $\rm\ \ \: j>0 \le k < n\ \ \$ is simply a slight variant of the Division Algorithm where one utilizes negative (vs. positive) remainders.$\ \$ To derive this negative form, simply perform the following transformation on the positive remainder form $\rm\ q\: n + r\ \to\ (q+1)\:n + r-n\$ if $\rm\ r\ne 0\:$, i.e. inc the quotient, dec the remainder by the dividend.

Thus the result is equivalent to the Division Algorithm, whose normal proof is indeed by induction. One could give a direct inductive proof of the result if, instead of invoking the Division Algorithm by name, one unwinds or inlines this inductive proof directly into the proof of the result - much as the same way that the classic Lindenmann - Zermelo direct proof of unique factorization of naturals inlines a division / Euclidean algorithm based descent proof of the fundamental Prime Divisor property $\rm\ p|ab\ \Rightarrow\ p|a\ \ or\ \ p|b\:$.

-

It is enough to prove it for $0 < x < 1$.

Now, let $M$ be an integer such that, $\frac{M}{n} \le x < \frac{M+1}{n}$ where $0 \le M < n$

Thus $[nx] = M$.

For $0 \le k \le n-M-1$, we have that $[x+\frac{k}{n}] = 0$.

For $n-1 \ge k > n-M-1$ we have that $[x + \frac{k}{n}] = 1$.

The result follows.

I don't think induction can be used here.

-

This is one of my favourite exercises, because of the following neat solution:

Fix $n$. Let

$$f(x) := \sum\limits_{k=0}^{n-1} \Biggl[x + \frac{k}{n}\Biggr] - [nx] \,.$$

Then $f(x) =0 \forall x \in [0,\frac{1}{n})$ since all terms are zero, and it is easy to prove that $f(x+\frac{1}{n})=f(x)$.

It follows imediately that $f$ is identically 0.

-
You're right, that is a very nice solution. – robjohn Oct 20 '12 at 23:19