Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

For any real number $a$ and a positive integer $n$, there is a concise formula to calculate

$$a + 2a + 3a + \cdots + na = \frac{n(n+1)}{2} a.$$

The proof for the same is given in Mathematical literature.

Is there any such formula to calculate:

$$\lfloor a\rfloor + \lfloor 2a\rfloor + \lfloor 3a\rfloor + \cdots + \lfloor na\rfloor $$

and

$$\lceil a\rceil + \lceil 2a\rceil + \lceil 3a\rceil + \cdots + \lceil na\rceil $$

for any whole number $n$ and $ 0 < a < 1$ ? Also, provide the proof for the same.

share|improve this question
1  
Have you tried calculating any, looking for patterns? –  Gerry Myerson Oct 5 '12 at 7:21
    
Yes, tried calculating for both things. There is a pattern for particular numbers like 0.2, 0.4, 0.8. But, how to generalize the pattern for any real number like 0.39856, 0.0009843, etc? Of course, finding general patterns helps in providing a formula. There doesn't seem having a general pattern among all real numbers. –  Neeraj T Oct 5 '12 at 7:45
    
For rational $a$, your sums come up in some of the early proofs of quadratic reciprocity --- see, e.g., Eisenstein's proof en.wikipedia.org/wiki/Proofs_of_quadratic_reciprocity –  Gerry Myerson Oct 5 '12 at 13:19
add comment

2 Answers

There is a closed form solution to the sum $\sum_{0\le k<n} \left\lfloor \frac {pk} q \right\rfloor$ when $n$ is a multiple of $q$. The sum in question is similar to one in Knuth's The Art of Computer Programming (Section 1.2.4 problem 37). Knuth's suggestion is to focus on the fractional parts instead of the integral parts of the terms. $$ \sum_{0\le k<n} \left\lfloor \frac {pk} q \right\rfloor = \sum_{0\le k<n} \frac {pk} q + \sum_{0\le k<n} \left\lbrace \frac {pk} q \right\rbrace = \frac p q \frac {n(n-1)} 2 + \sum_{0\le k<n} \left\lbrace \frac {pk} q \right\rbrace $$ The fractional part function $\lbrace pk /q\rbrace$ is periodic with period $q/d$, where $d=gcd(p,q)$. We might want $d\ne 1$ because of the restriction that $n$ is a multiple of $q$. $$ \sum_{0\le k<n} \left\lbrace \frac {pk} q \right\rbrace = \frac n q d \sum_{0\le k<q/d} \left\lbrace \frac {pk} q \right\rbrace = \frac n q d \sum_{0\le k<q/d} \left\lbrace \frac {p/d} {q/d} k \right\rbrace $$ There is a bit of number theory required for the next step. $gcd(p/d,q/d)=1$, so $(p/d)k=j\;(\text{mod}\;q/d)$ has a solution, unique modulo $q/d$, for every integer $j$, $0\le j<q/d$. Using this fact, the terms of the sum can be reordered in a way that leads to a radical simplification: $$ \sum_{0\le k<n} \left\lbrace \frac {pk} q \right\rbrace = \frac n q d \sum_{0\le k<q/d} \left\lbrace \frac {1} {q/d} k \right\rbrace = \frac n q d \sum_{0\le k<q/d} \frac {1} {q/d} k = n\left(1-\frac d q \right) $$ Putting the pieces together $$ \sum_{0\le k<n} \left\lfloor \frac {pk} q \right\rfloor = \frac p q \frac {n(n-1)} 2 + n \left(1-\frac d q \right) $$ Changing the limits of summation $$ \sum_{1\le k\le n} \left\lfloor \frac {pk} q \right\rfloor = \frac p q \frac {n(n+1)} 2 + n \left(1-\frac d q \right) $$

share|improve this answer
add comment

There seems no exact formula for the sum, considering that the sum depends highly sensitively on the fraction part of $a$. But we can give an asymptotic formula:

Case 1. If $a$ is rational, write $a = p/q$ where $p$ and $q$ are positive coprime integers. Then $kp \ \mathrm{mod} \ q$ attains every value in $\{0, 1, \cdots, q-1\}$ exactly once whenever $k$ runs through $q$ successive integers. Thus if we write $n = mq + r$,

$$ \begin{align*} \sum_{k=1}^{n} (ka - \lfloor ka \rfloor) &= \sum_{k=1}^{mq} (ka - \lfloor ka \rfloor) + \sum_{k=1}^{r} (ka - \lfloor ka \rfloor) \\ &= \frac{m(q-1)}{2} + O(1) = \frac{n(q-1)}{2q} + O(1). \end{align*}$$

This gives

$$ \sum_{k=1}^{n} \lfloor ka \rfloor = \frac{1}{2}n\left(n+\frac{1}{q}\right) + O(1). $$

Case 2. If $a$ is irrational, then the fractional parts $\langle ka \rangle := ka - \lfloor ka \rfloor$ is equidistributed on $[0, 1]$ by Weyl's criterion. Thus $$ \lim_{n\to\infty} \frac{1}{n} \sum_{k=1}^{n} \langle ka \rangle = \int_{0}^{1} x \, dx = \frac{1}{2} \quad \Longrightarrow \quad \sum_{k=1}^{n} \langle ka \rangle = \frac{n}{2} + o(n) $$ and we have $$ \sum_{k=1}^{n} \lfloor ka \rfloor = \frac{n^2}{2} + o(n). $$

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.