Find a formula for $\sum\limits_{k=1}^n \lfloor \sqrt{k} \rfloor$

Question

I need to find a clear formula (without summation) for the following sum:

$$\sum\limits_{k=1}^n \lfloor \sqrt{k} \rfloor$$

Well, the first few elements look like this:

$1,1,1,2,2,2,2,2,3,3,3,...$

In general, we have $(2^2-1^2)$ $1$'s, $(3^2-2^2)$ $2$'s etc.

Still I have absolutely no idea how to generalize it for $n$ first terms...

Answer 1

Hint

We have $$p\le\sqrt k< p+1\iff p^2\le k<(p+1)^2\Rightarrow \lfloor \sqrt{k} \rfloor=p$$ so

$$\sum\limits_{k=1}^n \lfloor \sqrt{k} \rfloor=\sum\limits_{p=1}^{\lfloor \sqrt{n+1}\rfloor-1} \sum_{k=p^2}^{(p+1)^2-1}\lfloor \sqrt{k} \rfloor=\sum\limits_{p=1}^{\lfloor \sqrt{n+1}\rfloor-1}p(2p+1)$$ Now use the fact $$\sum_{k=1}^n k=n(n+1)/2$$ and $$\sum_{k=1}^n k^2=n(n+1)(2n+1)/6$$ to get the desired closed form.

Answer 2

The following is valid for $n\geq 1$

\begin{align*} \sum_{k=1}^{n}\lfloor\sqrt{k}\rfloor =n\lfloor\sqrt{n}\rfloor -\frac{1}{3}\lfloor\sqrt{n}\rfloor^3-\frac{1}{2}\lfloor\sqrt{n}\rfloor^2+\frac{5}{6}\lfloor\sqrt{n}\rfloor \end{align*}

For convenient calculations we consider two aspects:

• We introduce a variable $a=\lfloor\sqrt{n}\rfloor$. So, we have $$a\leq \sqrt{n} < 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: $n=a^2,a=\lfloor\sqrt{n}\rfloor$

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

General case: $n\geq a^2,a=\lfloor\sqrt{n}\rfloor$

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

\begin{align*} \sum_{k=1}^{n}\lfloor\sqrt{k}\rfloor&=na-\frac{1}{3}a^3-\frac{1}{2}a^2+\frac{5}{6}a\\ &\qquad\qquad\qquad\qquad\qquad\qquad\qquad\Box \end{align*}

Note: This approach can be found in Concrete Mathematics by R.L. Graham, D.E. Knuth and O. Patashnik

Note: I've also added here an answer for the general case $\sum_{k=1}^n\lfloor\sqrt[p]{k}\rfloor$ with $p\geq 1$.

Answer 3

Consider evaluation of sums of following form:

$$S_p\stackrel{def}{=}\sum_{k=1}^n\lfloor\sqrt[p]{k}\rfloor$$

where $p$ is a positive integer $\ge 2$. In the special case $p = 2$, this reduces to the sum we want to calculate.

Let $a = \lfloor \sqrt[p]{n} \rfloor$ and take a sufficiently small $\epsilon > 0$ such that $$\lfloor \sqrt[p]{k} + \epsilon \rfloor = \lfloor \sqrt[p]{k} \rfloor\quad\text{ for all } k = 1, 2, \ldots, n$$

The introduction of the $\epsilon$ piece make the function $\lfloor \sqrt[p]{x} + \epsilon\rfloor$ continuous at the jumps of $\lfloor x \rfloor$. This allows us to rewrite $\mathcal{S}_p$ as a Riemann-Stieljes integral. $$ \mathcal{S}_p = \sum_{k=1}^n \lfloor \sqrt[p]{k} \rfloor = \sum_{k=1}^n \lfloor \sqrt[p]{k} + \epsilon \rfloor = \int_{1^-}^{n^+} \lfloor \sqrt[p]{x} + \epsilon \rfloor d \lfloor x \rfloor $$

Integrate by part, we get $$ \mathcal{S}_p = \bigg[ \lfloor \sqrt[p]{x} + \epsilon \rfloor \lfloor x \rfloor \bigg]_{x=1-}^{n^+} - \int_{1^-}^{n^+} \lfloor x \rfloor d \lfloor \sqrt[p]{x} + \epsilon \rfloor = na - \int_{1+\epsilon}^{\sqrt[p]{n}+\epsilon} \lfloor (s-\epsilon)^p \rfloor d \lfloor s \rfloor $$ Convert the last integral back into a sum, we find $$ \mathcal{S}_p = na - \sum_{s=2}^a (s^p - 1) = (n+1)a - \sum_{s=1}^a s^p = (n+1)a - \frac{B_{p+1}(a+1)-B_{p+1}(0)}{p+1} $$ where $B_k(x)$ is the Bernoulli polynomial of order $k$

For the special case $p = 2$, the sum we want is $$ \bbox[8pt,border: 1px solid blue;]{ \sum_{k=1}^n \lfloor\sqrt{k}\rfloor = \mathcal{S}_2 = (n+1) a - \frac16 a(a+1)(2a+1),\quad a = \lfloor\sqrt{n}\rfloor } $$

This is equivalent to the formula in Markus Scheuer's answer.

For the case $p = 3, 4, 5$. this leads to

$$\begin{align} \sum_{k=1}^n \lfloor\sqrt[3]{k}\rfloor = \mathcal{S}_3 & = (n+1) a - \frac14\left((a+1)^4 - 2(a+1)^3 + (a+1)^2\right)\\ \sum_{k=1}^n \lfloor\sqrt[4]{k}\rfloor = \mathcal{S}_4 & = (n+1) a - \frac15\left( (a+1)^5 - \frac52(a+1)^4 + \frac53 (a+1)^3 - \frac16(a+1) \right)\\ \sum_{k=1}^n \lfloor\sqrt[5]{k}\rfloor = \mathcal{S}_5 & = (n+1) a - \frac16\left( (a+1)^6-3(a+1)^5 + \frac52 (a+1)^4 - \frac12 (a+1)^2 \right)\\ \end{align} $$ reproducing the formulas in Claude Leibovici's answer.

Answer 4

I am very bad in the area of discrete mathematics (as well in other) but I have been fascinated by the problem set in your post.

I am sure that Daniel Fisher's comment and Sami Ben Romdhane's answer are very useful; however, I have not been able to finish the work.

So, what I used is computer simulation and data regression in order to establish some relations. Later, RIES was used to identify the rational values of the obtained coefficients. As you see, this is a very empirical process but I hope it could help you.

I set the problem in the most general manner, loking for $$\sum\limits_{k=1}^n \lfloor k^{1/p} \rfloor$$.
What I found is that the sum starts with a first term which is $$(n+1) \left\lfloor \sqrt[p]{n}\right\rfloor$$ to which is added a polynomial (no constant term) of degree $(p+1)$ of a variable which is $$1+\left\lfloor \sqrt[p]{n}\right\rfloor$$ So, for the first successive values of $p$, I obtained after some simplifications (I am sure that more simplifications could be done) $$ (n+1) \left\lfloor \sqrt{n}\right\rfloor +\frac{1}{3} \left(-\left(\left\lfloor \sqrt{n}\right\rfloor +1\right)^3+\frac{3}{2} \left(\left\lfloor \sqrt{n}\right\rfloor +1\right)^2-\frac{1}{2} \left(\left\lfloor \sqrt{n}\right\rfloor +1\right)\right) $$ $$ (n+1) \left\lfloor \sqrt[3]{n}\right\rfloor +\frac{1}{4} \left(-\left(\left\lfloor \sqrt[3]{n}\right\rfloor +1\right)^4+2 \left(\left\lfloor \sqrt[3]{n}\right\rfloor +1\right)^3-\left(\left\lfloor \sqrt[3]{n}\right\rfloor +1\right)^2\right) $$ $$ (n+1) \left\lfloor \sqrt[4]{n}\right\rfloor +\frac{1}{5} \left(-\left(\left\lfloor \sqrt[4]{n}\right\rfloor +1\right)^5+\frac{5}{2} \left(\left\lfloor \sqrt[4]{n}\right\rfloor +1\right)^4-\frac{5}{3} \left(\left\lfloor \sqrt[4]{n}\right\rfloor +1\right)^3+\frac{1}{6} \left(\left\lfloor \sqrt[4]{n}\right\rfloor +1\right)\right) $$ $$ (n+1) \left\lfloor \sqrt[5]{n}\right\rfloor +\frac{1}{6} \left(-\left(\left\lfloor \sqrt[5]{n}\right\rfloor +1\right)^6+3 \left(\left\lfloor \sqrt[5]{n}\right\rfloor +1\right)^5-\frac{5}{2} \left(\left\lfloor \sqrt[5]{n}\right\rfloor +1\right)^4+\frac{1}{2} \left(\left\lfloor \sqrt[5]{n}\right\rfloor +1\right)^2\right) $$

I do not know how this will be of any use to you; however, I must confess that I had a great time with this problem.

Answer 5

Hint in the form of an example: If you start the sum at $0$, you can write

$$\begin{align} \lfloor\sqrt0 \rfloor+\lfloor\sqrt1 \rfloor+\lfloor\sqrt2 \rfloor+\cdots+\lfloor\sqrt{11} \rfloor&=0+1+1+1+2+2+2+2+2+3+3+3\\ &=3+3+3+3+3+3+3+3+3+3+3+3\\ &\quad-1-1-1-1-1-1-1-1-1\\ &\quad-1-1-1-1\\ &\quad-1\\ &=12\cdot3-(1+4+9)\\ &=(11+1)\lfloor\sqrt{11}\rfloor-(1^2+2^2+\cdots+\lfloor\sqrt{11}\rfloor^2) \end{align}$$

Remark: The main reason for including the unnecessary term $0$ is that it makes it easier to describe the pattern of what's being subtracted. (Note, there are not $11$ terms in $1^2+2^2+\cdots+\lfloor\sqrt{11}\rfloor^2$, but only $\lfloor\sqrt{11}\rfloor=3$ terms.) Properly understood, the pattern explains the generalization to $\lfloor\sqrt[p]n\rfloor$ in Claude Leibovici's answer.

Answer 6

The way I approached this problem is dividing the sum into two halves. Where the first half contains all the numbers starting from $1$ and reaching upto $m$ such that $\sqrt{m}$ is greatest integer $<\lfloor\sqrt{n}\rfloor$, and second half contains the leftover numbers. Intuitively $m$ can be calculated by using simple formula $\lfloor\sqrt{n}\rfloor - 1$Mathematically:

$\displaystyle\sum_{k=1}^n\lfloor\sqrt{k}\rfloor = \underbrace{\displaystyle\sum_{p=1}^{\lfloor\sqrt{n}\rfloor-1}p\times(2p + 1)}^{\text{first part}} + \underbrace{(n - {\lfloor\sqrt{n}\rfloor}^2 + 1)\times{\lfloor\sqrt{n}\rfloor}}^{\text{second part}}$

The same can be resolved using the following identities.

$\displaystyle\sum_{x = 1}^n x = \frac{x\times(x+1)}{2}$

and

$\displaystyle\sum_{x = 1}^n x^2 = \frac{x\times(x+1)\times(2 \times x+1)}{6}$

I didn't tested this solution with every value, but the solution seems convincing.

I am taking an example to demonstrate it, taking $n = 5$
The answer should contain $\underbrace{1+1+1+2+2}+2+2+2+3+... = 7$

The $\lfloor\sqrt{5}\rfloor-1 = 1$(upper limit for the first part)
So, our first part is calculated as $1\times (2+1) = 3$
Similarly second part is calculated as
$(5-{\lfloor\sqrt{5}\rfloor}^2)\times \lfloor\sqrt{5}\rfloor = (5 - 2^2+1)\times 2 = (2)\times 2 = 4$
So we get $4 + 3 = 7$ as our answer, which is correct.

The same intuition can be used to derive formula for $\displaystyle\sum_{k=1}^n\lfloor\sqrt[x]{k}\rfloor$.
i.e.

$\displaystyle\sum_{k=1}^n\lfloor\sqrt[x]{k}\rfloor = \displaystyle\sum_{p=1}^{\lfloor\sqrt[x]{p}\rfloor}p\times ((p+1)^x-p^x)+(n - (\rfloor\sqrt[x]{n}\rfloor)^x + 1)\times\lfloor\sqrt[x]{n}\rfloor$

P.S. This is just an intuition, if anything wrong, feel free to comment.