# proving $\sum\limits_{k=1}^{n} \Bigl\lfloor{\frac{k}{a}\Bigr\rfloor} =\Bigl\lfloor{\frac{(2n+b)^{2}}{8a}\Bigr\rfloor}$

There was a problem in Apostol's book namely, to prove that: $$\sum\limits_{k=1}^{n} \Biggl\lfloor{\frac{k}{2}\Biggr\rfloor} = \Biggl\lfloor{\frac{n^{2}}{4}\Biggr\rfloor}$$

which i could solve. The following probelm is eluding me:

• If $a =1,2, \cdots, 7$, prove that there exists an integer $b$ depending on $a$ such that $$\sum\limits_{k=1}^{n} \Biggr\lfloor{\frac{k}{a}\Biggr\rfloor} =\Biggl\lfloor{\frac{(2n+b)^{2}}{8a}\Biggr\rfloor}$$
-
So, you've done it for $a=2$? Have you done it for any other values of $a$. For instance $a=1$ shouldn't be difficult. There's only a few to try :-) – Robin Chapman Oct 30 '10 at 9:43
@Robin Chapman: Yes, have done it for a=2 – anonymous Oct 30 '10 at 9:45
@Robin: Sir, I don't get you properly as your comments are breaking. Are you asking me to use induction. – anonymous Oct 30 '10 at 9:46
Chandru, I am not a knight of the realm. As you only have to prove it for seven different values of $a$, you can do it individually for each of them. – Robin Chapman Oct 30 '10 at 9:51
@All: Would like to see a proof! – anonymous Oct 30 '10 at 12:45

You should be able to use the fact that

If $\displaystyle n = aj+r$, where $0 \le r < a$ then

$\displaystyle \sum_{k=1}^{n} \left\lfloor \frac{k}{a} \right\rfloor = aj(j-1)/2 + rj$

Multiplying and dividing the RHS by $8a$ and using $aj = n-r$ would help, I think.

(Note: I haven't worked out the remaining details myself).

Hope that helps.

-
nice answer. For those interested in details, it seems one way to prove the above fact is to use the telescoping sum i mentioned below. – user1709 Oct 31 '10 at 10:49

It seems that as of now, doing individual cases might be a good way to get a feel for things. However, the outline below is motivated by 1.2.4 from TAOCP Volume 1.

Recall that $$\sum_{k=1}^n c_k = n c_n - \sum_{k=1}^{n-1} k (c_{k+1}-c_k)$$

I tried this identity for the case where $c_k = \lfloor k/2\rfloor$, and it rapidly leads to the alleged proof. I have not worked out the details, but it seems that the other cases that you mention above should also follow similarly, noting for example that when $a=3$, then

$$c_{k+1}-c_k = \left\lfloor \frac{k+1}{3}\right\rfloor - \left\lfloor \frac{k}{3}\right\rfloor,$$ which is zero for all $k$, except for $k=3j-1$, as $j=1,2,\ldots$, in which case it equals $1$.

Using these ideas, the latter sum in the identity above can be greatly simplified, which should help prove your claims.

-