# Evaluation of the sum $\sum_{i=1}^{\lfloor na \rfloor} \left \lfloor ia \right \rfloor$

Let $$a$$ be a positive proper fraction and $$n$$ is any integer then evaluate the following sum, $$\sum_{i=1}^{\left \lfloor na \right \rfloor\atop} \left \lfloor ia \right \rfloor$$

I think that probably some counting argument will give us a solution of the problem but I can't find it. Any help is appreciated.

Actually the question aroused due to my efforts in trying to find out a simple formula for calculating the Legendre Symbol. Following is my approach to finding a closed form for the sum $$\sum_{i=1}^{\frac{p-1}{2}} \left \lfloor \dfrac{ia}{p} \right \rfloor$$ where $$\operatorname{gcd}(a,p)=1$$ and $$a$$ is odd.

My Try

I have tried to approach the above problem in the following manner. Consider a rectangle in the Cartesian Plane with coordinates of the vertices $$A(0,0)$$, $$B(\dfrac{p}{2},0)$$, $$C(\dfrac{p}{2},\dfrac{a}{2})$$ and $$D(0,\dfrac{a}{2})$$.

Now draw the two diagonals $$AC$$ and $$BD$$. Let them intersect at $$O$$. Denote the number of lattice points in region $$R$$ with no lattice point (if any) on the boundaries is counted by $$\Lambda(R)$$.

Then using this notation we have, $$\Lambda(\triangle AOB)+\Lambda(\triangle BOC)+\Lambda(\triangle COD)+\Lambda(\triangle DOA)=\Lambda(\square ABCD)$$

But since $$\triangle AOB \equiv \triangle COD$$ and $$\triangle BOC \equiv \triangle DOA$$, we get $$\Lambda(\triangle AOB)=\Lambda(\triangle COD)$$ and $$\Lambda(\triangle BOC)=\Lambda(\triangle DOA)$$

Therefor our expression reduces to, $$2(\Lambda(\triangle AOB)+\Lambda(\triangle BOC)=\Lambda(\square ABCD) \implies 2\Lambda(\triangle ABC)=\Lambda(\square ABCD)$$

But, $$\Lambda(\triangle ABC)=\sum_{i=1}^{\frac{p-1}{2}} \left \lfloor \dfrac{ia}{p} \right \rfloor$$ and $$\Lambda(\square ABCD)=\left(\dfrac{p-1}{2} \right)\left \lfloor \dfrac{a}{2} \right \rfloor$$ hence we have, $$2\sum_{i=1}^{\frac{p-1}{2}} \left \lfloor \dfrac{ia}{p} \right \rfloor=\left(\dfrac{p-1}{2} \right)\left(\dfrac{a-1}{2} \right )$$

But from this I can't interpret the given sum. What is the mistake? There must be a mistake because the parity of both side of the inequality doesn't hold if $$p \equiv a \equiv 3$$ $$(\operatorname{mod}4)$$. Can anyone help me in this respect?

## 2 Answers

Let $a = \displaystyle\frac{p}{q}$ where $(p,q) = 1$ and $p < q$. Then:

$$\sum_{i=1}^{\lfloor na\rfloor} \lfloor ia \rfloor = \sum_{i=1}^{\lfloor na\rfloor} ia - \sum_{i=1}^{\lfloor na\rfloor} \lbrace ia \rbrace$$

Where $\lbrace x\rbrace$ is the fractional part of $x$.

Note that:

$$\sum_{i=1}^{\lfloor na\rfloor} \lbrace ia \rbrace = \frac{1}{q}\sum_{i=1}^{\lfloor na\rfloor} ip\text{ mod }q$$

We can get some interesting results from that depending on $n \text{ mod }q$.

• Could you elaborate on how you got to the second summation involving mod q. Aug 19, 2014 at 20:00
• @KBusc Using integer division we have $ip = cq + r$ where $0 \leq r < q$ (in fact, $r = ip \mod q$ and $c = \lfloor ia\rfloor$) so $\frac{ip}{q} = c + \frac{r}{q} = \lfloor ai\rfloor + \frac{ip\mod q}{q}$ Aug 19, 2014 at 20:23
• Ahh thank you very much, that makes sense. Aug 20, 2014 at 12:10
• Can't there be obtained any closed form of the sum?
– user170039
Aug 20, 2014 at 12:37
• @user170039 that depends on the divisibility of $n$ by $q$ and on wether $q$ is prime or not. Aug 20, 2014 at 12:39

Not quite an answer but I couln't get this to look correct as comment. But I think $$0 <\sum_{i=1}^{\left \lfloor na \right \rfloor} \left \lfloor ia \right \rfloor < a\cdot {\left \lfloor na \right \rfloor}\frac{{\left \lfloor na \right \rfloor} + 1}{2}$$

Should be true.

• Sorry for the terrible syntax but I am not sure how to do the fraction correctly Aug 19, 2014 at 18:02
• Try \frac{ numerator } { denominator } or just { numerator \over denominator } Aug 19, 2014 at 18:02
• You are missing a factor of $a$. Since $\lfloor ia \rfloor \leq ia$ we have $\sum \lfloor ia \rfloor \leq a \cdot \frac{\lfloor na \rfloor(\lfloor na \rfloor + 1)}{2}$. Aug 19, 2014 at 18:06