If $M:=\sum\limits_{k=1}^{\frac{n(n+1)}{2}}\lfloor\sqrt{2k}\rfloor$ How to Find $\frac{n^3+2n}{M}$?

Question

$$M:=\sum\limits_{k=1}^{\frac{n(n+1)}{2}}\lfloor\sqrt{2k}\rfloor$$ Find $\frac{n^3+2n}{M}$

This problem was on a problem book.

It is easy to find $M$

If $n$ is odd, $\ m=\frac{n+1}{2} $ and $$M= \frac{2(m)(m+1)(2m+1)}{3}-2m(m+1)+m -(m-1)(2m-1)+(m-1)m+\frac{2(m-1)(m)(2m-1)}{3}$$

If $n$ is even then $m=\frac{n}{2}$ and $$M= \frac{4(m)(m+1)(2m+1)}{3}-m(m+1)+m-2m^2$$

But doing the multiplications and then doing the division will take a long time so there must be some trick to solve this question quickly.

---

Here is a simple python code that calculate $M$ and tests my formula against the value of $M$

import math 
print("Enter n")
n= int(input())
print("\n")
mm=n*(n+1)//2

if n%2==0:
    m=n//2
else:
    m=(n+1)//2

z=0
for i in range (1, mm+1):
    z=z+math.floor(math.sqrt(2*i))
print(f"the sum equals {z}")
if n%2==1:
    print(f"The formula gives {math.floor((2/3)*((m)*(m+1)*(2*m+1)) -2*(m)*(m+1)+m -(m-1)*(2*m-1)+(2//3)*((m-1)*(m)*(2*m-1))+(m-1)*m)}")
else:
    print(f"The formula gives {math.floor((4/3)*((m)*(m+1)*(2*m+1)) -1*(m)*(m+1)+m -(m)*(2*m))}")

Answer 1

It doesn't get simpler than $M(n)=0, 1, 5, 13, 28, 51, 85, 131, 192, 269, 365,\ldots $ for $n\ge 0$ which has the generating function $$ \sum_{n\ge 0} M(n)x^n = \frac{x(1+2x+x^3)}{(1+x)(1-x)^4} $$ the recurrence $M(n) = 3M(n-1)-2M(n-2)-2M(n-3)+3M(n-4)-M(n-5)$ and from the partial fraction decompositon of the generating function $$ M(n) = n^3/3+n^2/4+2n/3+((-1)^n-1)/8. $$ There is no "nice" formula for $n(n^2+2)/M(n)$. Apparently in the book the terms $n^2/4$ for even $n$ and $n^2/4-1/4$ for odd n were dropped...