Sum of $\lfloor k^{1/3} \rfloor$

Question

I am faced with the following sum:

$$\sum_{k=0}^m \lfloor k^{1/3} \rfloor$$

Where $m$ is a positive integer. I have determined a formula for the last couple of terms such that $\lfloor n^{1/3} \rfloor^3 = \lfloor m^{1/3} \rfloor^3$. For example if the sum is from 0 to 11 I can find the sum of the terms 8 through 11. I am stuck on what formula can be applied to find the sum of the terms before the final stretch however.

Answer 1

You have $$ \begin{align*} \sum_{k=0}^m \lfloor k^{1/3} \rfloor &= \sum_{i=0}^{\lfloor m^{1/3} \rfloor} i |\{0 \leq k \leq m : \lfloor k^{1/3} \rfloor = i\}| \\ &= \sum_{i=0}^{\lfloor m^{1/3} \rfloor} i |\{0 \leq k \leq m : i^3 \leq k < (i+1)^3\}| \\ &= \sum_{i=0}^{\lfloor m^{1/3} \rfloor-1} i((i+1)^3-i^3) + \lfloor m^{1/3} \rfloor (m-\lfloor m^{1/3} \rfloor^3+1) \\ &= \sum_{i=0}^{\lfloor m^{1/3} \rfloor-1} (3i^3+3i^2+i) + \lfloor m^{1/3} \rfloor (m-\lfloor m^{1/3} \rfloor^3+1) \\ &= \frac{1}{4}(\lfloor m^{1/3} \rfloor-1)\lfloor m^{1/3} \rfloor^2(3\lfloor m^{1/3} \rfloor+1) + \lfloor m^{1/3} \rfloor (m-\lfloor m^{1/3} \rfloor^3+1). \end{align*} $$

Answer 2

Note: This answer provides a solution for the general case $\lfloor \sqrt[p]{k}\rfloor$ with $p\geq 1$.

The following is valid for $m\geq 1, p\geq 1$

\begin{align*} \sum_{k=1}^{m}\lfloor \sqrt[p]{k}\rfloor =m\lfloor \sqrt[p]{m}\rfloor^{p+1} -\frac{1}{p+1}\sum_{j=0}^{p}\binom{p+1}{j}B_j\lfloor \sqrt[p]{m}\rfloor^{p+1-j}+m\lfloor \sqrt[p]{m}\rfloor\tag{1} \end{align*}

with $B_j$ the $j$-th Bernoulli Number.

The special cases $p=1,2,3$ give

\begin{align*} \sum_{k=1}^m\lfloor k\rfloor&=\frac{1}{2}m^2+\frac{1}{2}m\\ \sum_{k=1}^m\lfloor \sqrt{k}\rfloor&= m\lfloor\sqrt{m}\rfloor -\frac{1}{3}\lfloor\sqrt{m}\rfloor^3-\frac{1}{2}\lfloor\sqrt{m}\rfloor^2+\frac{5}{6}\lfloor\sqrt{m}\rfloor\\ \sum_{k=1}^m\lfloor \sqrt[3]{k}\rfloor&=m\lfloor\sqrt[3]{m}\rfloor-\frac{1}{4}\lfloor\sqrt[3]{m}\rfloor^4 -\frac{1}{2}\lfloor\sqrt[3]{m}\rfloor^3-\frac{1}{4}\lfloor\sqrt[3]{m}\rfloor^2+\lfloor\sqrt[3]{m}\rfloor\tag{2}\\ \end{align*}

For convenient calculations we consider two aspects:

• We introduce a variable $a=\lfloor\sqrt[p]{m}\rfloor$. So, we have $$a\leq \sqrt[p]{m} < a+1$$
• We use the Iverson Bracket notation, so we can replace the expression $\lfloor x\rfloor$ by $$\lfloor x\rfloor=\sum_{j\geq 0}[1\leq j \leq x]$$

Special case: $m=a^p,a=\lfloor\sqrt[p]{m}\rfloor$

We start the calculation by conveniently assuming $m=a^p$. We obtain \begin{align*} \sum_{k=1}^{m}\lfloor\sqrt[p]{k}\rfloor&=\sum_{k=1}^m\sum_{j\geq 0}[1\leq j \leq \sqrt[p]{k}][0\leq k \leq a^p]\\ &=\sum_{j=1}^{a}\sum_{k=1}^{m}[j^p\leq k \leq a^p]\\ &=\sum_{j=1}^{a}(a^p-j^p+1)\\ &=a^{p+1}-\sum_{j=1}^{a}j^p+a\tag{3}\\ &=a^{p+1}-\frac{1}{p+1}\sum_{j=0}^{p}\binom{p+1}{j}B_j\,a^{p+1-j}+a\tag{4} \end{align*}

Comment:

• In (3) we use the known representation of the sum of $p$-th powers of natural numbers by the Bernoulli Numbers

$$\sum_{k=1}^{n}k^{p}=\frac{1}{p+1}\sum_{j=0}^{p}\binom{p+1}{j}B_j\,n^{p+1-j}$$

General case: $m\geq a^p,a=\lfloor\sqrt[p]{m}\rfloor$

In the general case we let again $a=\lfloor\sqrt[p]{m}\rfloor$ and have additionally to consider the terms for $a^p< k \leq m$. They are all equal to $a$, so they sum up to $$(m-a^p)a.$$ Adding this to (4) we get the general formula with $a=\lfloor \sqrt[p]{m}\rfloor$

\begin{align*} \color{blue}{\sum_{k=1}^{m}\lfloor\sqrt[p]{k}\rfloor}&\color{blue}{=ma-\frac{1}{p+1}\sum_{j=0}^{p}\binom{p+1}{j}B_j\,a^{p+1-j}+a}\\ &\qquad\qquad\qquad\qquad\qquad\qquad\qquad\Box \end{align*}

---

Let's finally compute the special case $p=3$. We need the Bernoulli numbers $B_0=1, B_1=\frac{1}{2}, B_2=\frac{1}{6}$ and $B_3=0$.

\begin{align*} \sum_{k=1}^{m}\lfloor\sqrt[3]{k}\rfloor&=na-\frac{1}{4}\sum_{j=0}^{3}\binom{4}{j}B_j\,a^{4-j}+a\\ &=na-\frac{1}{4}\left[\binom{4}{0}B_0a^4+\binom{4}{1}B_1a^3+\binom{4}{2}B_2a^2\right]+a\\ &=na-\frac{1}{4}a^4-\frac{1}{2}a^3-\frac{1}{4}a^2+a\\ &\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\Box \end{align*}

The other cases ($p=1,2$) from the claim (2) follow similarly.

Note: This approach ($p=2$) can be found in Concrete Mathematics by R.L. Graham, D.E. Knuth and O. Patashnik.