What is the value of the following sum? $$\sum_{i = 1}^n \left\lfloor \dfrac{3n-i}{2}\right\rfloor.$$ Especially how to handle the sums with floors? This sum appeared while solving this problem.

My work: I tried ignoring floor and assuming that it will count an extra $\frac12$ for exactly $\left\lfloor \tfrac n2 \right\rfloor$ times, but the values do not match for the small test cases that I solve with hand.

  • $\begingroup$ Your correction is almost right; however sometimes it should be $\lceil \frac{n}{2}\rceil$. Try different $n$ and see. $\endgroup$ – vadim123 Jun 4 '14 at 15:57

This answer is only for $n$ even. For $n$ odd, it can be done similarly.

Write $n=2k$ for some integer $k$. Then \begin{align} \sum_{i = 1}^n \left\lfloor \dfrac{3n-i}{2}\right\rfloor&=\sum_{i = 1}^{2k} \left\lfloor \dfrac{6k-i}{2}\right\rfloor\\ &=\sum_{i \textrm{ even}}^{2k} \left\lfloor \dfrac{6k-i}{2}\right\rfloor+\sum_{i \textrm{ odd}}^{2k} \left\lfloor \dfrac{6k-i}{2}\right\rfloor\\ &=\sum_{i=1}^{k} \left\lfloor \dfrac{6k-2i}{2}\right\rfloor+\sum_{i=1}^{k} \left\lfloor \dfrac{6k-(2i-1)}{2}\right\rfloor\\ &=\sum_{i=1}^{k} \left\lfloor 3k-i\right\rfloor+\sum_{i=1}^{k} \left\lfloor 3k-i+\frac12\right\rfloor\\ &=\sum_{i=1}^{k} ( 3k-i)+\sum_{i=1}^{k} (3k-i)\\ &=2\sum_{i=1}^{k} ( 3k-i). \end{align}

I am sure from this point you can continue by yourself, can't you?

  • $\begingroup$ Thanks! Just to verify my work, is the answer for the odd case $2\sum\limits_{i= 1}^k (3k - i + 1)$, where $n = 2k + 1$? $\endgroup$ – taninamdar Jun 4 '14 at 16:22

We start with a special case of the Hermite Identity, which states that $\forall x \in \Bbb R, \left\lfloor x \right\rfloor + \left\lfloor x+ \frac {1}{2}\right\rfloor = \left\lfloor2x\right\rfloor.$ Substituting $x=\frac{3n-(i+1)}{2}$, we obtain $$\left\lfloor \frac{3n-i}{2}\right\rfloor+\left\lfloor \frac{3n-(i+1)}{2}\right\rfloor=\left\lfloor3n-(i+1)\right\rfloor=3n-(i+1).$$

Now check the cases when $n$ is odd or even.

  • $\begingroup$ I get for the even case from the other answer. Can you verify whether the answer for the odd case is $2\sum\limits_{i= 1}^k (3k - i + 1)$ such that $2k+1 = k$? $\endgroup$ – taninamdar Jun 4 '14 at 16:45
  • $\begingroup$ Nope, I am finding the sum to be $5k^{2} + 4k +1$ where $2k+1=n$, but your's is coming out to be $5k^{2}+k.$ $\endgroup$ – Indrayudh Roy Jun 4 '14 at 16:54
  • $\begingroup$ I see, I'll check my working. Thank you. :) $\endgroup$ – taninamdar Jun 4 '14 at 18:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.