# Closed form of $\displaystyle\sum_{k=1}^n\sum_{j=1}^k\left\lfloor\dfrac{(j-1)^2}{m}\right\rfloor$

Begin a problem:

Prove that: $$\sum_{k=1}^n\sum_{j=1}^k\left\lfloor\dfrac{(j-1)^2}{12}\right\rfloor = \left\lfloor\dfrac{(n^2-10)^2}{144}\right\rfloor$$ I try replace denominator by $$m$$, with the help a computer, i found a few identities

$$\sum_{k=1}^n\sum_{j=1}^k\left\lfloor\dfrac{(j-1)^2}{2}\right\rfloor = \left\lfloor\dfrac{(n^2-2)^2}{24}\right\rfloor$$

$$\sum_{k=1}^n\sum_{j=1}^k\left\lfloor\dfrac{(j-1)^2}{4}\right\rfloor = \left\lfloor\dfrac{(n^2-2)^2}{48}\right\rfloor$$

$$\sum_{k=1}^n\sum_{j=1}^k\left\lfloor\dfrac{(j-1)^2}{6}\right\rfloor = \left\lfloor\dfrac{(n^2-7)^2}{72}\right\rfloor$$

$$\sum_{k=1}^n\sum_{j=1}^k\left\lfloor\dfrac{(j-1)^2}{8}\right\rfloor = \left\lfloor\dfrac{(n^2-5)^2}{96}\right\rfloor$$

$$\sum_{k=1}^n\sum_{j=1}^k\left\lfloor\dfrac{(j-1)^2}{12}\right\rfloor = \left\lfloor\dfrac{(n^2-10)^2}{144}\right\rfloor$$

$$\sum_{k=1}^n\sum_{j=1}^k\left\lfloor\dfrac{(j-1)^2}{16}\right\rfloor = \left\lfloor\dfrac{(n^2-11)^2}{192}\right\rfloor$$

$$\sum_{k=1}^n\sum_{j=1}^k\left\lfloor\dfrac{(j-1)^2}{3}\right\rfloor = \left\lfloor\dfrac{(n^2-2)(n^2-3)}{36}\right\rfloor$$

$$\sum_{k=1}^n\sum_{j=1}^k\left\lfloor\dfrac{(j-1)^2}{5}\right\rfloor = \left\lfloor\dfrac{(n^2-6)(n^2-7)}{60}\right\rfloor$$

$$\sum_{k=1}^n\sum_{j=1}^k\left\lfloor\dfrac{(j-1)^2}{7}\right\rfloor = \left\lfloor\dfrac{(n^2-6)(n^2-7)}{84}\right\rfloor$$$$m=9,10,11,13,14,15$$ that form is impossible! There is something very mysterious that "prevents" the construction of a general formula!???

• There seems to be an error in your computation or a typo in your formula. The general answer should be $\frac{1}{12m} n^2 (n^2-1)$. The m can be factored out of the sum. Commented Feb 8 at 4:00
• @Andrew there is a floor. The general denominator is 12m. The numerator should be a polynomial in n. Commented Feb 8 at 4:04
• Oops, I mistook the floor for a square bracket. Commented Feb 8 at 4:04
• Regarding the coefficient of $n^2$, if it exists, then the sequence $\{(j-1)^2/m\}$ appears periodically, one can estimate the "statistical mean", say $v$, then the lost value is $n^2 v/2$, then the coefficient of $n^2$ will be $-\frac{1+6mv}{12m}$. For instance, $m=2$, the sequence mean is $v=1/4$, and for $m=3$, the mean is $v=2/9$, etc. Commented Feb 8 at 6:39
• Then it might be much easier to see there are no choices for the constant term for large $m$. Commented Feb 8 at 6:40

Exchanging the order of summation we get (notice the summand doesn't depend on $$k$$)

$$S(n,m) = \sum_{k=1}^n \sum_{j=1}^k \left\lfloor \frac{(j-1)^2}{m} \right\rfloor = \sum_{j=1}^n \sum_{k=j}^n \left\lfloor \frac{(j-1)^2}{m} \right\rfloor = \sum_{j=0}^n (n-j) \left\lfloor \frac{j^2}{m} \right\rfloor$$

(We also changed the summation index $$j \to j+1$$ and then notice we can include the boundary $$j=n$$ because the summand is $$0$$ there)

Let's use $$\lfloor y \rfloor = y - \{y\}$$ where $$\{y\}$$ is the fractional part of $$y$$. We have

$$S(n, m) = \sum_{j=0}^n (n-j)\left(\frac{j^2}{m} - \left\{\frac{j^2}{m} \right\} \right) = \frac{n^2(n^2-1)}{12m} - \sum_{j=0}^n (n-j)\left\{\frac{j^2}{m} \right\}$$

Let's study the sum $$h(n) = \sum_{j=0}^n (n-j)\left\{\frac{j^2}{m} \right\}$$. It is infact the convolution of the sequences $$f(n)=n$$ and $$g(n)=\left\{\frac{n^2}{m} \right\}$$.

The generating function of $$h$$ is the product of those of $$f$$ and $$g$$. Denote the generating functions with corresponding capital letters. We know $$F(x)=\frac{x}{(1-x)^2}$$. Let's calculate $$G(x)$$.

$$G(x)=\sum_{n=0}^\infty g(n)x^n = \sum_{k=0}^\infty \sum_{r=0}^{m-1} g(km+r)x^{km+r} = \sum_{k=0}^\infty x^{km} \sum_{r=0}^{m-1} \left \{ \frac{r^2}{m} \right\} x^r = \frac{\sum_{r=0}^{m-1} \left \{ \frac{r^2}{m} \right\} x^r}{1-x^m} = \frac{\sum_{r=0}^{m-1} (r^2 \mod m) x^r}{m(1-x^m)}$$

So

$$H(x) = \frac{\sum_{r=0}^{m-1} (r^2 \mod m) x^{r+1}}{m(1-x)^2(1-x^m)}$$

We can decompose $$H$$ into partial fractions. Notice that $$1-x^m$$ has roots $$\zeta^j$$ for $$j=0,1,\dots, m-1$$ where $$\zeta = e^{2\pi i /m}$$. We get

$$H(x) = \frac{1}{m(1-x)^3} + \frac{m-1}{2m(1-x)^2} + \frac{m^2-1}{12m(1-x)} + \sum_{j=1}^{m-1} \frac{\zeta^j}{(1-\zeta^j)^2 (\zeta^j-x)}$$

So extracting the coefficient from these (use binomial theorem) and after simplifying we get

$$h(n) = \frac{1}{m^2} \cdot \sum_{r=0}^{\min(m,n)-1} (r^2 \bmod m) \left[ \frac{n^2}{2} + \left(\frac{m}{2}-r \right)n + \frac{r(r-m)}{2} + \frac{m^2-1}{12} + \sum_{j=1}^{m-1} \frac{1}{(1-\zeta^j)^2 \zeta^{j(n-r-1)}} \right]$$

It's interesting that the inner sum involving the roots of unity seems to always be a rational number. That would need some further investigation. And one further hypothesis is that the coefficient of $$n^1$$ in the final formula will be $$0$$. Maybe that follows since the sum has quadratic residues as coefficients, there are $$\frac{m}{2}$$ of them and we have the coeffient $$\frac{m}{2} - r$$.

• Many thank for your solution. Commented Feb 14 at 16:29
• Uses computer, we have $$S(n,10)=\left\lfloor\dfrac{(n^2-14)^2}{120}\right\rfloor +\left\lfloor\dfrac{n-2}{10}\right\rfloor -\left\lfloor\dfrac{n+1}{10}\right\rfloor$$ Commented Feb 15 at 9:59

Not an answer, just to provide some clues. If the following equality

$$S(n,m):= \sum_{k=1}^n \sum_{j=1}^k \left\lfloor\frac{(j-1)^2}{m}\right\rfloor = \left\lfloor\frac{n^4+a n^3+b n^2+c n+d}{12m}\right\rfloor$$ holds, it means there is a linear programming problem for $$(a,b,c,d)$$. That is, for each n, we have

$$12mS(n,m) - n^4 \le a n^3+b n^2+c n+d\le 12mS(n,m)+(12m-1) - n^4$$.

I wrote a simple python program (with cvx) to check the first 200 $$n$$ values (see below or here). The output is the following, where $$x$$ represents the vector $$a,b,c,d$$, one can round the values to the nearest integer to get a neat form, it seems there are many more choices for $$d$$ values. The opt column means whether a feasible solution exists, zero means existence otherwise no feasible solutions.

-----------------------------------------------------------------------------------------
m         x                                                                         opt
2        [ 3.03814945e-07 -4.00005912e+00  1.87986844e-03  1.29603072e+01]          0.0
3        [ 9.04014617e-07 -5.00015688e+00  2.15788460e-03  2.01131447e+01]          0.0
4        [ 6.31527550e-07 -4.00010834e+00  1.36694856e-03  2.49847447e+01]          0.0
5        [ 5.95622595e-06 -1.30011771e+01  4.34250723e-02  4.75770167e+01]          0.0
6        [ 3.70991943e-06 -1.40005838e+01  6.53485568e-03  5.87972672e+01]          0.0
7        [ 9.15908596e-06 -1.30014679e+01  9.71668571e-03  6.35219093e+01]          0.0
8        [ 1.15279659e-05 -1.00021026e+01  4.79462285e-02  5.74116090e+01]          0.0
9        None          inf
10        None          inf
11        None          inf
12        [ 1.52415029e-05 -2.00029063e+01  9.88607611e-02  1.13437311e+02]          0.0
13        None          inf
14        None          inf
15        None          inf
16        [ 1.63227419e-05 -2.20031303e+01  1.15235060e-01  1.53520392e+02]          0.0
17        None          inf
18        None          inf
19        None          inf
20        None          inf
21        None          inf
22        None          inf
23        None          inf
24        None          inf
25        None          inf
26        None          inf
27        None          inf
28        None          inf
29        None          inf
30        None          inf
31        None          inf
32        None          inf
33        None          inf
34        None          inf
35        None          inf
36        None          inf
37        None          inf
38        None          inf
39        None          inf
-------------------------------------------


The code is the following.

import cvxpy as cp
import numpy as np

def sum_mse(n, m):
ret = 0;

for k in range(1, n+1):
for j in range(1, k+1):
ret = ret + int(np.floor((j-1)**2/m))

return ret

print("-----------------------------------------------------------------------------------------")
print("  m         x                                                                         opt")
for m in range(2, 40):

denom = 12 * m

x = cp.Variable(4) # 4 coefficients

N = 200 # test the first 200 cases.

f = np.arange(N)
t = 4
A = np.concatenate( (np.vander(f, t), -np.vander(f, t) ) ) # for both upper/lower bounds
c = f**4
upper_val = np.array( [sum_mse(u, m) for u in f])*denom + (denom - 1) - c
lower_val = np.array( [sum_mse(u, m) for u in f])*denom - c

b = np.concatenate((upper_val, -lower_val))

q = np.zeros((4, 1))
prob = cp.Problem(cp.Minimize(q.T@x),
[A @ x <= b])
prob.solve()

print('{0:3d}        {1}          {2}'.format(m, x.value, prob.value))

• Thanks bro. Great job! Commented Feb 8 at 6:23
• A hint to follow is to show there are no feasible solutions for large $m$, I ran the program for a while and it shows $16$ is the largest possible within the first 100 numbers. Commented Feb 8 at 6:24