1
$\begingroup$

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.

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

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

$\endgroup$
  • $\begingroup$ 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) $\endgroup$ – model_checker Jan 11 at 10:45
  • $\begingroup$ I tried this with $n=10.$ I get a negative value according to your formula. $\endgroup$ – model_checker Jan 11 at 10:45

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.