# Evaluation of finite sum

How can one prove the following equality (for fixed positive integer $a$):

$$12\sum_{k=1}^{an^2-1}k\left\{\frac{k(an-1)}{an^2}\right\}=3a^2n^4-a^2n^2-2$$

where $\{x\}=x-\lfloor x\rfloor$ denotes the fractional part operator.

• Might help to notice that $k(6n-1)/(6n^2)=(k/n)-(1/(6n^2))$. This makes it easier to see what the fractional part is --- it's one thing if $k$ is a multiple of $n$, something else if it's not. Where does the problem come from? May 4, 2014 at 7:32
• I'm happy to hear that someone is working on Dedekind sums. Can you tell me what Dedekind sums you're trying to evaluate? May 4, 2014 at 23:43
• Doesn't the reciprocity formula for Dedekind sums help you to evaluate that one? May 4, 2014 at 23:51
• $an^2$ reduced modulo $an-1$ is $n$, so reciprocity relates the sum for $(an^2,an-1)$ to the sum for $(an-1,n)$. Then another application gets you to $(-1,n)$. May 5, 2014 at 0:02
• Let $a=2$, $n=3$. Then (in the notation of Rademacher and Grosswald, page 3) $$s(5,18)+s(18,5)=-(1/4)+(1/12)((18/5)+(1/90)+(5/18))$$ But $s(18,5)=s(3,5)$, and reciprocity again gives $$s(3,5)+s(5,3)=-(1/4)+(1/12)((5/3)+(1/15)+(3/5))$$ Then $s(5,3)=s(3-1,3)=s(-1,3)=-s(1,3)$ should be easy to evaluate. May 5, 2014 at 0:21

The Dedekind sum $s(t,u)$ can be defined by $$s(t,u)=\sum_{k=1}^{u-1}{k\over u}\left(\left\{{kt\over u}\right\}-{1\over2}\right)$$ for relatively prime integers $t,u$, where $\{x\}$ denotes the fractional part of $x$. We have $$s(t,u)=-{1\over2u}\sum k+{1\over u}\sum k\left\{{kt\over u}\right\}$$ so if we can evaluate $s(an-1,an^2)$ then we can evaluate $\displaystyle\sum_1^{u-1}k\left\{{(an-1)k\over an^2}\right\}$

The Dedekind sum satisfies these formulas (and many more):

1. $s(t,u)=s(t',u)$ if $t\equiv t'\pmod u$

2. $\displaystyle s(1,u)=-{1\over4}+{1\over6u}+{u\over12}$

3. $s(-t,u)=-s(t,u)$

4. $\displaystyle s(t,u)+s(u,t)=-{1\over4}+{1\over12}\left({t\over u}+{1\over tu}+{u\over t}\right)$

The last of these is called the reciprocity formula for the Dedekind sum, and is considerably harder to establish than the others.

Reciprocity lets us express $s(an-1,an^2)$ in terms of $s(an^2,an-1)$.

Then the first formula implies $s(an^2,an-1)=s(n,an-1)$.

Then reciprocity gives us $s(n,an-1)$ in terms of $s(an-1,n)$.

Then from the 1st and 3rd formulas we have $s(an-1,n)=s(-1,n)=-s(1,n)$, and the 2nd formula completes the evaluation.

I make it an answer only because I want to include the program code, please don't downvote. the approximation is good, but not exact. As to how to prove it, I have no clue.

for n = 10, the LHS is 1069916.8199999994 and RHS is 1076398 for n = 1000, LHS = 107999963999968.27 and RHS = 107999963999968

maybe you missed something?

In [5]: math.modf(4.5)
Out[5]: (0.5, 4.0)

In [6]: foo = lambda k,n : k*math.modf(1.0*k*(6*n-1) / (6*n**2))[0]

In [9]: bar = lambda n : 12*sum( [foo(k,n) for k in xrange(1,6*n**2)])

In [10]: bar(10)
Out[10]: 1076397.9999999993

In [11]: 1080000 - 3600 -2
Out[11]: 1076398

In [12]: g = lambda n : 108*n**4 - 36*n**2 - 2

In [13]: g(10)
Out[13]: 1076398

In [14]: bar(1000)
Out[14]: 107999963999968.27

In [15]: g(1000)
Out[15]: 107999963999998

• There is approximation and the formula is exact. For $n=10$,$lhs=rhs=1076398$; for $n=100$,$lhs=rhs=10799639998$; for $n=1000$,$lhs=rhs=107999963999998$. Could you take your code and change the $1.0$ to $1$ in $foo$ ? I suppose that $bar$ is computed on reals and that you bump on accuracy limits. Please answer. May 4, 2014 at 6:43
• hello, Claude, if if change 1.0 to 1 in foo(), the result of modf() is always 0 because in python,the divisions are by default integer divisions. Thanks to your comment, I realize the evaluation is affected by accuracy limit of floating points. Thanks May 4, 2014 at 16:40