From: rusin@vesuvius.math.niu.edu (Dave Rusin)
Newsgroups: sci.math
Subject: Re: Summation problem
Date: 7 Oct 1997 20:53:23 GMT
In article <151@stt.win-uk.net>, Iain Davidson wrote:
>
>I was wondering if there is an exact closed formula for
>
>SUM INT(ax + b), x = 0, 1,...,n
>
>when INT(y) is the greatest integer less than y and a,b are real
>numbers.
Define "closed formula".
Think of the sum as a function of a and b. The inclusion of INT makes
it a step function, which, as a and b vary, changes value by 1
whenever (a,b) crosses one of the lines ma + b = k (where m is
an integer between 0 and n, and k is any integer.) For each fixed m,
these lines form a set of parallels which are 1 unit apart in the
direction of the b axis.
So for each of finitely-many values of m we draw a family of parallel
lines across the plane (with bounded non-positive integer slopes) and so
partition the plane into lots of little polygons. The value of your sum
is constant on each polygon, and increases by 1 when we pass from one
polygon to a neighbor to its northeast. You can even mark off a
rectangle at the origin such that the division of the plane is can be
found by dividing this one rectangle and then tiling the plane with
copies of the partitioned rectangle.
I cannot imagine what you would accept as a "closed formula" whose
graph would look like this.
I'm also aware that you probably meant to keep a and b fixed and
then let n vary, so this model is sure to be singularly unhelpful.
Of course since z-1 < int(z) <= z, the sum above is between
S0 = SUM (ax+b) = a*(n^2+n)/2 + b*(n+1) and S0 - (n+1), so we can
get an estimate which is pretty good for large a and b.
(BTW, your definition of INT makes e.g. INT(3)=2; is that what you want?)
dave