Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
2  
Split the sum. You have one regular part for which you get a nice closed form formula, and the remaining sum from $\lfloor\sqrt{n}\rfloor^2$ to $n$. –  Daniel Fischer Feb 9 at 12:13
    
This is a nice problem ! –  Claude Leibovici Feb 9 at 14:19
    
Is this problem homework ? –  Claude Leibovici Feb 9 at 14:30
    
I'm preparing for my exams this week and doing old ones. Some are easy, but some I need help with. –  Arek Krawczyk Feb 9 at 14:31
    
Did you finish with this one ? What about your formula ? –  Claude Leibovici Feb 9 at 18:16

2 Answers 2

up vote 5 down vote accepted

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.

share|improve this answer

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.

share|improve this answer

Your Answer

 
discard

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.