How to compute the following floor sum?

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.

• Compute the sum without the floors, and then the difference. – Yuval Filmus Jan 11 at 9:26
• Difference of what, I do not understand? – model_checker Jan 11 at 9:28
• The difference between the sum without the floors and your sum. – Yuval Filmus Jan 11 at 9:28
• The sum without floors is $$S ' = \frac{(2n-5m)(m+1)}{4}.$$ You want me to find $S'-S?$ – model_checker Jan 11 at 9:38
• Yes, exactly. Half the summands would be zero, and the other half 1/2. – Yuval Filmus Jan 11 at 9:54

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}.$$

• def check_sum(n): # Choose m to be floor of n/5 m = math.floor(n/5) s = 0 for k in range(m): s += math.floor((n-5*k)/2) k = m%2 guess = 0 if n % 2 == 0: guess = (2*n*(m-1)-21*m-5*m**2+8-2*k)/4 else: guess = (2*n*(m-1)-21*m-5*m**2+12-6*k)/4 print("Guess", guess) print("Actual", s) – model_checker Jan 11 at 10:45
• I tried this with $n=10.$ I get a negative value according to your formula. – model_checker Jan 11 at 10:45