How do I prove this summation question over real a number?

35 viewed last edited 3 years ago

I need to prove the following:

\sum_{k=0}^{n\ -1}\ \ \lfloor\ x+\frac{k}{n}\ \rfloor\ =\ \ \lfloor nx\rfloor

I can see how to prove this if x is an integer.

Since we know that each \frac{k}{n}<\ 1, \ \lfloor x\ +\frac{k}{n}\rfloor\ =\ x since x is an integer and x + k/n < x + 1. The LHS becomes nx.

Since x is an integer, the RHS is also nx. Proving the same when x is an integer.

How do I prove this when x is a real number?

Vivekanand Vellanki

Lets prove this for a real number.

Let x = m + f; where m is an integer and 0 < f < 1.

Further, lets assume that k is the smallest integer such that the following is true:

x\ +\ \frac{k}{n}\ge m+1.

This implies that x\ \ge m\ +\ 1\ -\frac{k}{n}\ \Rightarrow\ x\ \ge m\ +\ \frac{n\ -\ k}{n}.

Evaluating the left hand side:

Given that k is the smallest integer with the above property, all integers from k to n - 1 also have the above property.

Also, given that k is the smallest integer with this property, we know that:

x+\frac{k-1}{n}\le m+1

Hence, in the summation, the first k elements (from 0 to k - 1) are m; and the remaining n - k elements are m + 1.

Hence, LHS = km\ +\left(n-k\right)\left(m\ +1\right)\ =\ km\ +\ nm\ +n\ -\ km\ -k\ =nm\ +\left(n\ -k\right)

Evaluating the RHS; we know that:

m+\frac{n\ -\ k}{n}\le\ x\ <\ m\ +\ \frac{n\ +\ 1\ -k}{n}

Multiplying by n, we get:

nm+n-k\ \le\ nx\ <\ nm+n+1-k

Hence, \ \lfloor nx\rfloor=mn+n-k

This proves the summation.