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

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