8
$\begingroup$

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.

$\endgroup$
1
  • $\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, 2014 at 15:57

2 Answers 2

3
$\begingroup$

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?

$\endgroup$
1
  • $\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, 2014 at 16:22
1
$\begingroup$

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.

$\endgroup$
3
  • $\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, 2014 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$ Jun 4, 2014 at 16:54
  • $\begingroup$ I see, I'll check my working. Thank you. :) $\endgroup$
    – taninamdar
    Jun 4, 2014 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.