3
$\begingroup$

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

$\endgroup$
6
  • 1
    $\begingroup$ 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. $\endgroup$
    – Andrew
    Commented Feb 8 at 4:00
  • 2
    $\begingroup$ @Andrew there is a floor. The general denominator is 12m. The numerator should be a polynomial in n. $\endgroup$
    – Yimin
    Commented Feb 8 at 4:04
  • $\begingroup$ Oops, I mistook the floor for a square bracket. $\endgroup$
    – Andrew
    Commented Feb 8 at 4:04
  • 1
    $\begingroup$ 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. $\endgroup$
    – Yimin
    Commented Feb 8 at 6:39
  • 1
    $\begingroup$ Then it might be much easier to see there are no choices for the constant term for large $m$. $\endgroup$
    – Yimin
    Commented Feb 8 at 6:40

2 Answers 2

2
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ Many thank for your solution. $\endgroup$
    – hxthanh
    Commented Feb 14 at 16:29
  • $\begingroup$ 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$$ $\endgroup$
    – hxthanh
    Commented Feb 15 at 9:59
2
$\begingroup$

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))
$\endgroup$
2
  • 1
    $\begingroup$ Thanks bro. Great job! $\endgroup$
    – hxthanh
    Commented Feb 8 at 6:23
  • 1
    $\begingroup$ 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. $\endgroup$
    – Yimin
    Commented Feb 8 at 6:24

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .