D

How do I prove this summation question over real a number?
35 viewed last edited 2 years ago
Anonymous
0

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
0

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.