17

There are well-known closed-form expressions for summations such as $\sum_{k=1}^{n}\lfloor k^{\frac{1}{2}} \rfloor$, $\sum_{k=1}^{n}\lfloor k^{\frac{1}{3}} \rfloor$, $\sum_{k=1}^{n}\lfloor k^{\frac{1}{4}} \rfloor$, etc. For example, we have that $$\sum_{k=1}^{n}\lfloor k^{\frac{1}{3}} \rfloor = -\frac{1}{4} \left\lfloor\sqrt[3]{n}\right\rfloor \left( \left\lfloor\sqrt[3]{n}\right\rfloor^{3} + 2 \left\lfloor\sqrt[3]{n}\right\rfloor^{2} + \left\lfloor\sqrt[3]{n}\right\rfloor - 4(n+1) \right)$$ for all $n \in \mathbb{N}$.

However, Mathematica is unable to evaluate the sum $\sum_{k=1}^{n}\lfloor k^{\frac{2}{3}} \rfloor$. Furthermore, there is no closed-form expression for this summation given in the OEIS sequence http://oeis.org/A032514 corresponding to this sum.

More generally, Mathematica is not able to evaluate summations such as $\sum_{k=1}^{n}\lfloor k^{\frac{4}{3}} \rfloor$, $\sum_{k=1}^{n}\lfloor k^{\frac{3}{4}} \rfloor$, $\sum_{k=1}^{n}\lfloor k^{\frac{3}{7}} \rfloor$, etc. Letting $q \in \mathbb{Q}$ be positive, it appears that there is a known closed-form expression for $\sum_{k=1}^{n}\lfloor k^{q} \rfloor$ if and only if $q \in \mathbb{N}$ or $q$ is of the form $q = \frac{1}{r}$ where $r \in \mathbb{N}$. So it is natural to ask:

(1) Is there a closed-form expression for $\sum_{k=1}^{n}\lfloor k^{\frac{2}{3}} \rfloor$?

(2) More generally, is there a closed-form expression for $\sum_{k=1}^{n}\lfloor k^{q} \rfloor$ for $q \in \mathbb{Q}_{> 0} \setminus \mathbb{N} \setminus \left\{ \frac{1}{2}, \frac{1}{3}, \ldots \right\}$?

John M. Campbell
  • 1,997
  • 2
    Could you provide a reference for the closed-form expression in the case where $q=1/r$ with $r\in \mathbb{N}$? – user37238 Mar 11 '16 at 13:35
  • Wolfram Alpha is able to evaluate summations of this form in the case where $q = \frac{1}{r}$ for a natural number $r$. For example: https://www.wolframalpha.com/input/?i=Sum[Floor[k^%281%2F4%29],{k,1,n}] I discovered a general formula involving Bernoulli numbers for summations of this form in the case where $q = \frac{1}{r}$, but this formula is probably already known. – John M. Campbell Mar 11 '16 at 13:39
  • 1
    Ok, but could you tell us where did you find the general formula (with Bernoulli numbers)? In a specific book? On which website? – user37238 Mar 11 '16 at 14:06
  • 2
    Thank you for your comment. I meant that I independently discovered this formula involving Bernoulli numbers based on my own research. I have not seen this formula in any mathematical literature or online, but this formula is probably already known. This formula is: $\sum_{k=0}^{n} \lfloor k^{\frac{1}{j}} \rfloor = (1+n)\lfloor n^{\frac{1}{j}} \rfloor - \frac{1}{j+1} \sum_{k=1}^{j+1}(1+\lfloor n^{\frac{1}{j}} \rfloor)^{k} \binom{j+1}{k} B_{j+1-k}$. I have not formally proven this formula. I would be interested in somehow proving this formula combinatorially. – John M. Campbell Mar 11 '16 at 14:19
  • Thank you for the formula. A mathematical proof of this formula would also be interesting. Maybe, you could ask for a proof in this question (or create a specific question for a proof of this formula). – user37238 Mar 11 '16 at 14:28
  • 1
    @user37238 check the fifth page in this article http://arxiv.org/abs/1502.07295 – Tulip Mar 17 '16 at 20:43
  • @aziiri Thanks for your comment! I recently found a proof due to Markus Scheuer of the above formula involving Bernoulli numbers, which is given in the following link: http://math.stackexchange.com/questions/1140225/sum-of-lfloor-k1-3-rfloor/1274784#1274784 It seems as if this proof cannot be directly generalized to summations of the form $\sum_{k=0}^{n} \lfloor k^{q} \rfloor$ for $q \in \mathbb{Q}{> 0}$, because if one mimics this proof with respect to the sum $\sum{k=0}^{n} \lfloor k^{q} \rfloor$, one would have to evaluate $\sum_{k'=0}^{n'} \lfloor k^{\frac{1}{q}} \rfloor$. – John M. Campbell Mar 18 '16 at 02:28

1 Answers1

3

It's unlikely that there is a closed form expression for what you want. Consider the expression $$ \sum_{k=1}^{n}\left\lfloor f(k)\right\rfloor, $$ where $f(k)$ is a monotonically increasing function with $f(1)=1$. Let $g(m)$ be the smallest integer value of $k$ such that $f(k)\ge m$; i.e., $g(m)=\left\lceil f^{-1}(m)\right\rceil$. Then the terms in the sum are at least as large as $1$ starting at $k = g(1)$, and at least as large as $2$ starting at $k= g(2)$, and so on. As long as $g(m)\le n$, each term contributes $n-g(m)+1$ to the sum. So $$ \sum_{k=1}^{n}\left\lfloor f(k)\right\rfloor = \sum_{m=1}^{\lfloor f(n)\rfloor} \left(n + 1 - \left\lceil f^{-1}(m)\right\rceil\right)=(n+1)\lfloor f(n)\rfloor - \sum_{m=1}^{\lfloor f(n)\rfloor} \left\lceil f^{-1}(m)\right\rceil. $$ This will simplify in certain cases where the inverse is integer-valued (so the ceiling function goes away) and "nice" (so the resulting sum can be evaluated). Two standard examples are when the inverse is a polynomial (e.g., $f(k)=k^{1/q}$, so $f^{-1}(m)=m^q$) and when the inverse is an exponential function (e.g., $f(k)=1+\log_b k$, so $f^{-1}(m)=b^{m-1}$). In your case you have $$ \sum_{k=1}^{n}\left\lfloor k^{2/3} \right\rfloor=(n+1)\left\lfloor n^{2/3}\right\rfloor - \sum_{m=1}^{\lfloor n^{2/3}\rfloor} \left\lceil m^{3/2}\right\rceil, $$ but this sum doesn't seem any easier to evaluate.

mjqxxxx
  • 41,358