How to compute the following floor sum?

Question

I want to compute $$S = \sum_{k=0}^{m} \left\lfloor \frac{n-5k}{2}\right\rfloor.$$ This sum was motivated by the need to compute the number of solutions to $$x_1+2x_2 +5x_3 = n (*)$$ In particular we observe that the number of solutions to $x_1+2x_2=n$ is $\left\lfloor\frac{n}{2}\right\rfloor+1$ and so the number of solutions for $(*)$ is $$a(n) =\sum_{k=0}^{\lfloor n/5\rfloor} \left\lfloor \frac{n-5k}{2}\right\rfloor+1.$$ This is because we can write $(*)$ as $x_1+2x_2 = n-5x_3$ and then we can range $0\leq x_3 \leq \lfloor n/5\rfloor$ to get all solutions. We have denoted $m = \lfloor n/5\rfloor$ and so $$a(n) = S + m+1.$$ I am not sure how to start computing $S$, perhaps someone can give some indications.

Answer 1

First, suppose $n$ and $m$ are even. Then the sum of the even terms of $S$ is

$$S_2 = \sum\limits_{k=0}^{m/2}\frac{n-10k}{2} = \frac{nm}{4} - \frac{5m(m+2)}{8}.$$

and similarly, if $n$ is even and $m$ is odd, the sum of the odd terms of $S$ is

$$S_1 = \sum\limits_{k=0}^{(m-1)/2}\frac{n - 6 - 10k}{2} = \frac{(n-6)(m-1)}{4} - \frac{5(m-1)(m+1)}{8}.$$

For a general $m$, if $l := \left\lfloor\frac{m}{2}\right\rfloor$, then $$S_2 = \dfrac{nl}{2}-\dfrac{5l(l+1)}{2},$$ and similarly, with $p := \left\lfloor\frac{m-1}{2}\right\rfloor$, we have

$$S_1 = \frac{p(n-6)}{2} - \frac{5p(p+1)}{2}.$$

Now, adding those together, we have

\begin{align*}S = S_1 + S_2 &= \frac{p(n-6)-5p(p+1)+nl-5l(l+1)}{2} \\&= \frac{(p+l)n-11p-5p^2-5l^2-5l}{2}\end{align*}

But $p+l = m-1$ (if neither had been rounded down, it would sum to $\frac{2m-1}{2}$, but exactly one has been rounded down by exactly $\frac{1}{2}$, so it sums to $\frac{2m-2}{2} = m-1$), so we can do some simplifications:

$$S = \frac{(m-1)n-6p-5m-5(p^2+l^2)}{2}$$

Similarly if there were no rounding, then we would have, $p^2+l^2 = \frac{m^2+(m-1)^2}{4} = \frac{2m^2-2m+1}{4}$, but our rounding reduces this by exactly $\frac{1}{4}$, so in fact $p^2 +l^2 = \frac{m^2-m}{2}$, allowing a further simplification:

$$S = \frac{2n(m-1)-12p-15m-5m^2}{4}.$$

Now, if $m$ is odd, then $12p = 6(m-1)$, while if $m$ is even, then $12p = 6(m-2)$, so if $I_o(m)$ is $1$ when $m$ is odd and $0$ when $m$ is even, then $12p = 6m-12+6I_o(m)$

$$S = \frac{2n(m-1)-21m-5m^2+12-6I_o(m)}{4}$$

which is as nice a format as we're going to get it into.

In the case where $n$ is odd, we see that $S_2$ is reduced by $1$ in each term, so by $l$ in total, and similarly $S_1$ is increased by $1$ in each term, so by $p$ in total, so $S$ changes by $p - l$ in total, and $p - l = I_o(m) - 1$, so our final sum in this case is

$$S = \frac{2n(m-1)-21m-5m^2+8-2I_o(m)}{4}.$$