Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

$$S_k=\sum_{n=1}^{k^2-1}\lfloor\sqrt{n}\rfloor $$

Can somebody give me an idea about the steps I should follow? Initially I thought
$$n^{1/2}\log(n) \leq n^{1/2}\leq n^{3/2}$$

so $\Theta(f(n))=S_k $ but I am not sure if it is the strict bound.


share|cite|improve this question

I would count: How many copies are there of each term in the sum? For example the $\lfloor\sqrt n\rfloor$ is $5$ for $25\le n < 36$, that is, 11 times.

In general $\lfloor\sqrt n\rfloor$ is $j$ when $j^2\le n<(j+1)^2=j^2+2j+1$, which is $2j+1$ times, so if we group like terms together we find $$ S_k = \sum_{n=1}^{k^2-1} \lfloor\sqrt n\rfloor = \sum_{j=1}^{k-1} j(2j+1)$$ Now it's just a summed polynomial, and there are (fairly well known) formulas for calculating such a thing exactly. But when we're only interested in asymptotic growth rates, only the degree of the polynomial matters, and the sum is one degree higher than the general term. So the answer is $$S_k = \Theta(k^3)$$

share|cite|improve this answer
can you explain how did you found the sum ∑j(2j+1) – Lee Dec 1 '12 at 12:38
@Nikos: I'm regrouping $$1+1+1+2+2+2+2+2+3+3+3+3+3+3+3+\cdots+\lfloor\sqrt n\rfloor$$ into (ealling each value of $\lfloor\sqrt n\rfloor=j$) $$(1+1+1)+(2+2+2+2+2)+(3+3+3+3+3+3+3)+\cdots+(j+j+\cdots+j)+\cdots$$ or in other words $$1\cdot 3 + 2\cdot5+3\cdot7+\cdots+j(2j+1)+\cdots$$ – Henning Makholm Dec 1 '12 at 13:36

$$\sqrt{k} - 1 < \left \lfloor \sqrt{k} \right \rfloor \leq \sqrt{k}$$ Hence, $$\sum_{k=1}^{n} \left(\sqrt{k} - 1 \right) < \sum_{k=1}^{n} \left(\left \lfloor \sqrt{k} \right \rfloor \right) \leq \sum_{k=1}^{n} \left(\sqrt{k} \right)$$

Now us the fact that $$\sum_{k=1}^n \sqrt{k} = \dfrac23 n^{3/2} + \dfrac{\sqrt{n}}2 + \dfrac1{24} \dfrac1{\sqrt{n}} + \zeta(-1/2) + \mathcal{O}(1/n)$$

$$\dfrac23 n^{3/2} - n + \mathcal{O}(n^{1/2}) < \sum_{k=1}^{n} \left(\left \lfloor \sqrt{k} \right \rfloor \right) \leq \dfrac23 n^{3/2} + \mathcal{O}(n^{1/2})$$

$$\dfrac23 n^{3} - n^2 + \mathcal{O}(n) < \sum_{k=1}^{n^2} \left(\left \lfloor \sqrt{k} \right \rfloor \right) \leq \dfrac23 n^{3} + \mathcal{O}(n)$$

share|cite|improve this answer
it's complicated but thanks. Did you use that formula?Relevant equations – Lee Nov 30 '12 at 19:31

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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