2

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 09:43
  • @Robin Chapman: Yes, have done it for a=2 –  Oct 30 '10 at 09:45
  • @Robin: Sir, I don't get you properly as your comments are breaking. Are you asking me to use induction. –  Oct 30 '10 at 09:46
  • 1
    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 09:51
  • @All: Would like to see a proof! –  Oct 30 '10 at 12:45

2 Answers2

3

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.

Aryabhata
  • 82,206
  • 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. –  Oct 31 '10 at 10:49
  • If $a=n$ then $j=1,r=0$. $\sum_{k=1}^n\left\lfloor\frac kn\right\rfloor=1\ne0=n1(1-1)/2+0\cdot1.$ – Anne Bauval Feb 04 '24 at 16:43
  • $$\sum_{k=1}^{n} \left\lfloor \frac{k}{a} \right\rfloor = aj(j-1)/2 + (r\color{red}{+1})j.$$ – Anne Bauval Feb 04 '24 at 16:54
1

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.