Floor of Square Root Summation problem

Question

I have problem calculating the following summation: $$ S = \sum_{j=1}^{k^2-1} \lfloor \sqrt{j}\rfloor. $$

As far as I understand the mean of that summation it will be something like $$1+1+1+2+2+2+2+2+3+3+3+3+3+3+3+\cdots$$ and I suspect that the last summation number will be $(k-1)^2$, but I really can't find the pattern of the equal simpler summation.

Answer 1

Try replacing it by a sum of the form $\sum_1^k k \cdot c_k$, where $c_k$ is the number of times that $\lfloor \sqrt{j} \rfloor = k$.

Answer 2

Since the last value for $j$ is $k^2-1$, none of the terms of the sum are $k$; they are all between $1$ and $k-1$.

How many $1$'s will be in the sum? Well, we'll get $1$ when $j$ is any number between $1^2$ and $2^2-1$; then we'll get $2$ for each number between $2^2$ and $3^2-1$. Then we'll get $3$ for each number between $3^2$ and $4^2-1$. Etc.

So, if $n\leq k-1$, how many times does it show up in the sum? It shows up exactly the number of times that there are integers between $n^2$ and $(n+1)^2-1$, inclusively. This is $$(n+1)^2 - n^2 = n^2 + 2n + 1 - n^2 = 2n+1.$$ So your sum has $2(1)+1 = 3$ ones; $2(2)+1 = 5$ twos; $2(3)+1=7$ threes; etc. Up to $k-1$, which appears exactly $2(k-1)+1 = 2k-1$ times.

So we get that $$S = \sum_{r=1}^{k-1} r(2r+1) = 2\left(\sum_{r=1}^{k-1}r^2\right) + \sum_{r=1}^{k-1}r.$$

Answer 3

HINT $\ $ Your displayed sum has $\rm\ (2^2 - 1^2)\ \ 1's,\ \ (3^2-2^2)\ \ 2's,\ \ (4^2-3^2)\ \ 3's,\ \ldots $

Answer 4

Let $\lfloor \sqrt{n} \rfloor = a$, then the following sum holds:

$$\sum_{0\le k < n} \lfloor \sqrt{k} \rfloor = (n+1)a - \frac{a^3}{3} - \frac{a^2}{2} - \frac{a}{6}.$$

(Edited.)

You might also enjoy the slightly more tricky sum:

$$\sum_{0\le k < n} \lfloor k^{1/3} \rfloor = nb - \frac{b^2}{4} - \frac{b^3}{2} - \frac{b^4}{4},$$

where this time $b =\lfloor n^{1/3} \rfloor$

One way to obtain these answers is to merely apply the summation identity that I mentioned here