Closed forms for certain types of sums

[late-enthusiast]

Hi

I'm trying to figure out how to derive the closed form for the
following types of sums

(a) Sum[a <= k <= b](floor(k/m))
(b) Sum[a <= k <= b](ceiling(k/m))
(c) Sum[a <= k <= b](k mod m)

I'm not asking for a ready made formula that you happen to know. I'm
asking for a step-by-step derivation.

Note: A typical method for deriving the sum of a sequence of integers
from 0 to n is

{using commutativity: a + b = b + a}
S = Sum[0 <= k <= n](k) = Sum[0 <= k <= n](n-k)
{add the two sums to eliminate k}
=> 2·S = Sum[0 <= k <= n](k + (n-k))
= Sum[0 <= k <= n](n)
{factor out n}
= Sum[0 <= k <= n](1) · n
{adding 1s evaluates to the range}
= (n + 1) · n
{algebra}
=> S = (1/2) · (n + 1) · n

This closed form, however, is not as revealing when you replace the
boundaries 0..n with a..b. A more transparent formula is:

Sum[a <= k <= b](k)
= (b - a + 1) · (b + a)/2

where the first factor is the range, the second factor is the average
of the max and min values of the range.

For (a), I tried

(floor(b/m) - ceiling(a/m) + 1) · (floor(b/m) + ceiling(a/m))/
2

which didn't work (as was expected): it comes close, but always
deviates by some small quantity.

Thanks in advance
-- K

P.S. If the method you suggest applies to all 3 sums I'm asking, just
describe it for one, and leave the answer for the others out, please.

[Patrick Coilland]

late-enthusiast a �crit :

> Hi
>
> I'm trying to figure out how to derive the closed form for the
> following types of sums
>
> (a) Sum[a <= k <= b](floor(k/m))
> (b) Sum[a <= k <= b](ceiling(k/m))
> (c) Sum[a <= k <= b](k mod m)
>
> I'm not asking for a ready made formula that you happen to know. I'm
> asking for a step-by-step derivation.
>

For the first one, the classical method is to write :

Sum[m(n-1)<= k <mn] (floor(k/m))=m(n-1)

So Sum[0<= k <mn] (floor(k/m))=m Sum[0<= i < n] (i)=mn(n-1)/2

So Sum[0<= k <=a] (floor(k/m))=m floor((a+1)/m)( floor((a+1)/m)-1)/2 +
floor((a+1)/m)(a+1-m floor((a+1)/m)

And you compute Sum[0<= k <=a] (floor(k/m)) as Sum[0<= k <=b]
(floor(k/m)) - Sum[0<= k <=a-1] (floor(k/m))