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

Question

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!???

Answer 1

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)

UPDATED answer

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$.

Answer 2

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))