2
$\begingroup$

$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.

Thanks

2 Answers 2

4

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)$

  • 0
    @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$2012-12-01
0

$\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)$

  • 0
    it's complic$a$ted $b$ut thanks. Did you use that formula?Relevant equations2012-11-30