San José State University

applet-magic.com
Thayer Watkins
Silicon Valley
& Tornado Alley
USA

The Summation of Series Using
the Anti-Differencing Operation

In the integral calculus the Riemanian integral of a function f(x) over an interval [a,b] is defined as the limit of the


abf(x)dx = lim Σ1nf(xiΔi
 

where the interval [a,b] is partitioned into [x0=a, x1, x2,...,xn=b]
and Δix=xi-xi-1

The limiting process is over n and partitions of the interval such that the maximum increment goes to zero; i.e., max (Δi) → 0.

It would be extremely cumbersome and tedious to evaluate integrals by this definition. Fortunately there is an easier way.

If F(x) is a function such that its derivative is equal to f(x);


D(F(x)) = dF/dx = f(x),
 

then (The Fundamental Theorem of Calculus)


ab>f(x)dx = F(b) - F(a)
 

The function F(x) is called the anti-derivative of f(x).

Ronald L. Graham, Donald E. Knuth and Oren Patashnik prsent an interest extension of this system for the summation of series. They call their system Finite Calculus.

Analogies exist in Finite Calculus for most concepts, operations and relations in the Differential Calculus. (Differential Calculus is a misnomer; the field should be called Derivative Calculus.)

In Finite Calculus the differencing operation


Δf = f(x+1)−f(x)
 

takes the place of the derivative. Then if F(x) is such that ΔF=f(x) then


Σab>f(x)dx = F(b) - F(a)
 

F(x) is called the anti-difference of f(x).

While it may be easy to find the anti-difference of some functions, such as bx, in general it is not easy to do so without some special tools. In the case of bx


Δbx = bx+1−bx = (b-1)bx.
 

Therefore the anti-difference of bx is bx/(b-1). This means that for b=2


Δ2x = 2x.
 

The function 2x serves the same role in the Finite Calculus as ex serves in the Differential Calculus.

The power functions xn do not have obvious anti-differences, but there is another type of function that provides a convenient basis for computing the anti-differences. This function is called the falling factorial power function. It is defined as


xm = x(x-1)(x-2)··(x-m+1)
 

Note that there are m factors in this product.

Consider now


Δxm = (x+1)x(x-1)(x-2)··(x+1-m+1)−x(x-1)(x-2)··(x-m+1)
x(x-1)(x-2)··(x-m+2)[(x+1)−(x-m+1)]
= x(x-1)(x-2)··(x-m+2)m
= mxm-1.
 

This is analogous to d(xm)/dx =mxm-1.

Since Δxm = mxm-1 the anti-diffence of xm is xm+1/(m+1).

The definition of xm may be extended beyond the positive integers. The appropriate definition of negative integers is


x−m = 1/(x+1)(x+2)··(x+m)
 

This leves x0 and x−0 to be defined. They are equal to each other and equal to 1. To justify this definition note that


x1 = xx0
 

but x1=x so x0 must be equal to 1. Likewise,


x−1 = x−0/(x+1).
 

But x−1=1/(x+1) so x−0=1.

For negative integers then


Δ(x−m) = 1/(x+2)··(x+m+1) − 1/(x+1)··(x+m)
= 1/(x+2)··(x+m)[1/(x+m+1) − 1/(x+1)]
= 1/(x+2)··(x+m)[(x+1)-(x+m+1)]/(x+1)(x+m+1)
= - m[1/(x+1)(x+2)··(x+m+1)]
= - mxm+1
 

Therefore the anti-difference of x−m is x−(m-1)/(m-1) for m≠1.

For the special case of m equal to 1 consider the harmonic function defined for positive integers as:


H(x) = 1 + 1/2 + 1/3 + ·· 1/x.

The difference ΔH is


H(x+1)−H(x) = 1/(x+1).
 

Therefore the anti-difference of x−1 is H(x). The harmonic function is the analogue in the Finite Calculus of the logarithm function in the Differential Calculus.


HOME PAGE OF applet-magic
HOME PAGE OF Thayer Watkins