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

3 Answers 3

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
1
$\begingroup$

\begin{align*} \sum_{k=1}^n\left\lfloor\dfrac{3n-k}{2}\right\rfloor&=\sum_{k=1}^n \left(n+\left\lfloor\dfrac{n-k}{2}\right\rfloor\right)\\ &=n^2+\sum_{k=0}^{n-1}\left\lfloor\dfrac{k}{2}\right\rfloor\\ &=n^2+\left\lfloor\dfrac{(n-1)^2}{4}\right\rfloor \end{align*}

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .