17
$\begingroup$

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\}$?

$\endgroup$
  • 2
    $\begingroup$ Could you provide a reference for the closed-form expression in the case where $q=1/r$ with $r\in \mathbb{N}$? $\endgroup$ – user37238 Mar 11 '16 at 13:35
  • $\begingroup$ 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: 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. $\endgroup$ – John M. Campbell Mar 11 '16 at 13:39
  • 1
    $\begingroup$ Ok, but could you tell us where did you find the general formula (with Bernoulli numbers)? In a specific book? On which website? $\endgroup$ – user37238 Mar 11 '16 at 14:06
  • 2
    $\begingroup$ 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. $\endgroup$ – John M. Campbell Mar 11 '16 at 14:19
  • 1
    $\begingroup$ @user37238 check the fifth page in this article arxiv.org/abs/1502.07295 $\endgroup$ – aziiri Mar 17 '16 at 20:43
3
+200
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.