# Calculate the sum of $\left\lfloor \sqrt{k} \right\rfloor$

I'm trying to calculate for $$n\in \mathbb{N}$$ the following sum :

$$\sum_{k=1}^{n^2}\left\lfloor \sqrt{k} \right\rfloor$$.

I tried putting in the first terms, which gave me

$$\sum_{k=1}^{n^2}\left\lfloor \sqrt{k} \right\rfloor=(1+2+3+\cdots+n)+\left\lfloor \sqrt{2} \right\rfloor+\left\lfloor \sqrt{3} \right\rfloor+\left\lfloor \sqrt{5} \right\rfloor+\cdots+\left\lfloor \sqrt{n^2-1} \right\rfloor$$

$$\iff \sum_{k=1}^{n^2}\left\lfloor \sqrt{k} \right\rfloor=\frac{n(n+1)}{2}+\left\lfloor \sqrt{2} \right\rfloor+\left\lfloor \sqrt{3} \right\rfloor+\left\lfloor \sqrt{5} \right\rfloor+\cdots+\left\lfloor \sqrt{n^2-1} \right\rfloor$$.

I've been trying to somehow find a pattern between the different integer parts of the irrational numbers just like I did with the integers but I fail to success.

Is there a trick to use here or is my take wrong ?

Thank you.

• This is A174723. Standard initial attack for problems like this: compute the values for small $n$, see if it matches any familiar sequences. Of course, you might still have to prove that an apparent match continues for all $n$.
– lulu
Commented Aug 6, 2022 at 21:51
• This is exactly what I was trying to do.. Still can't find any familiar sequence... is there any trick ? What if there isn't any familiar sequence? Commented Aug 6, 2022 at 22:05
• $$n+\sum_{k=1}^{n-1}(2k+1)k$$ Because each value $k$ from $1$ to $n-1$ occurs $2k+1$ times. Commented Aug 6, 2022 at 22:20
• As a specific illustration of the comment of @ThomasAndrews, suppose that $k$ ranges from $(1)$ through $(6^2 = 36).$ For the $[(2 \times 5) + 1] = 11$ values, as $k$ ranges from $(25)$ through $(35)$, you have that $$\left\lfloor \sqrt{k} \right\rfloor = 5.$$ Commented Aug 6, 2022 at 22:53

Here's a proof using the benefits of the Iverson bracket:

\begin{align} \sum_{k=1}^{n^2}\lfloor\sqrt{k}\rfloor &= \sum_{k=1}^{n^2}\sum_{j=1}^n[\;j \le \sqrt{k}\;]\\ &= \sum_{j=1}^n \sum_{k=1}^{n^2}[\;j \le \sqrt{k}\;]\\ &= \sum_{j=1}^n \sum_{k=1}^{n^2}[\;j^2 \le k\;]\\ &= \sum_{j=1}^n \sum_{k=j^2}^{n^2}1\\ &= \sum_{j=1}^n (n^2-j^2+1)\\ &= n^3 - \frac{1}{6}n(n+1)(2n+1)+n\\ &= \frac{1}{6}n(4n^2-3n+5) \end{align}

The sum can be calculated as follows:

$$\sum_{k=1}^{n^2} \lfloor \sqrt k \rfloor = 1 + 1 + 1 + \overbrace{2 + .. + 2}^{5 \space \text{terms}}+ \overbrace{3 + .. + 3}^{7 \space \text{terms}} + \overbrace{4 + .. + 4}^{9 \space \text{terms}} + .. + n$$

That reduces to: $$3 \times 1 + 5 \times 2 + 7 \times 4 + .. + (2n-1) \times (n-1) + n$$

The above sum is: $$n + \sum_{k=1}^{n-1} (2n+1)\times n = \frac{n(4 n^2 - 3n + 5)}{6}$$

Which is gotten from the OEIS found by @lulu. I used the method given in the proof at the OEIS (given by J. M. Bergot), with insight from @Thomas Andrews and I believe the last equality is straightforward to prove by induction.

Put $$k= j^2+i$$ so that$$j,i$$ shall span $$k \in \left[ {1,n^2 } \right]\quad \Rightarrow \quad \left\{ \begin{array}{l} j \in \left[ {1,n} \right] \\ i \in \left[ {0,\left( {j + 1} \right)^2 - j^2 } \right) = \left[ {0,2j} \right] \\ \end{array} \right.$$ and clearly it is $$\left\lfloor {\sqrt k } \right\rfloor = j$$ and then the sum becomes $$\begin{array}{l} S(n) = \sum\limits_{k = 1}^{n^2 } {\left\lfloor {\sqrt k } \right\rfloor } = \sum\limits_{j = 1}^{n - 1} {\sum\limits_{i = 0}^{2j} j } + \sum\limits_{j = n}^n {\sum\limits_{i = 0}^0 j } = \\ = \sum\limits_{j = 1}^{n - 1} {j\sum\limits_{i = 0}^{2j} 1 } + \sum\limits_{j = n}^n {j\sum\limits_{i = 0}^0 1 } = \left( {\sum\limits_{j = 1}^{n - 1} {\left( {2j + 1} \right)j} } \right) + n = \left( {2\sum\limits_{j = 1}^{n - 1} {j^2 } + \sum\limits_{j = 1}^{n - 1} j } \right) + n = \\ = 2\frac{{n\left( {2n - 1} \right)\left( {n - 1} \right)}}{6} + \frac{{n\left( {n - 1} \right)}}{2} + n = \\ = \frac{{2n\left( {2n - 1} \right)\left( {n - 1} \right) + 3n\left( {n - 1} \right) + 6n}}{6} = \\ = \frac{{4n^3 - 3n^2 + 5n}}{6} \\ \end{array}$$

• Worth learning to use \begin{align}...\end{align} to format that last section. Commented Aug 7, 2022 at 0:23