Indefinite Summation of Polynomials

Question

I've been experimenting with the summation of polynomials. My line of attack is to treat the subject the way I would for calculus, but not using limits.

By way of a very simple example, suppose I wish to add the all numbers between 10 and 20 inclusive, and find a polynomial which I can plug the numbers into to get my answer. I suspect its some form of polynomial with degree 2. So I do a integer 'differentiation':

diff(x^2) = x^2-(x-1)^2 = 2x-1

I can see from this that I nearly have my answer, so assuming an inverse 'integration' operation and re-arranging:

(1/2)diff(x^2+int(1)) = x

Now, I know that the 'indefinite integral' of 1 is just x, from 'differentiating' x-(x-1) = 1. So ultimately:

(1/2)(x^2+x) = int(x)

So to get my answer I take the 'definite' integral:

int(x):10,20 = (1/2)(20^2+20)-(1/2)(9^2+9) = 165 (the lower bound needs decreasing by one)

My question is, is there a general way I can 'integrate' any polynomial, in this way?

Please excuse my lack of rigour and odd notation.

Answer 1

Your "diff" is actually called (backward) finite difference.

\begin{align} \nabla_1 [ P ](x) &= P(x) - P(x-1) \\ &= P(x-1+1) - P(x-1) \\ &= \Delta_1[ P ](x-1) \end{align}

The inverse the forward finite difference is called indefinite sum. Extracted from Wikipedia, the useful formulae for polynomials is:

\begin{align} \Delta^{-1}_1 x^n &= \frac{B_{n+1}(x)}{n+1} + C \\ \Delta^{-1}_1 af(x) &= a \Delta^{-1}_1 f(x) \end{align}

(B_n+1(x) is the Bernoulli polynomial.)

The Δ^-1 can be converted back to your "int" by substituting $x \mapsto x + 1$.

Answer 2

You seem to be reaching for the calculus of finite differences, once a well-known topic but rather unfashionable these days. The answer to your question is yes: given a polynomial $f(x)$ there is a polynomial $g(x)$ (of degree one greater than $f$) such that $$f(x)=g(x)-g(x-1).$$ This polynomial $g$ (like the integral of $f$) is unique save for its constant term. Once one has $g$ then of course $$f(a)+f(a+1)+\cdots+f(b)=g(b)-g(a-1).$$

When $f(x)=x^n$ is a monomial, the coefficients of $g$ involve the endlessly fascinating Bernoulli numbers.

Answer 3

For any particular polynomial there is an easier way to do indefinite summation than using the Bernoulli numbers, going off of Greg Graviton's answer. Here we'll use the forward difference $\Delta f(x) = f(x+1) - f(x)$. Then

$\displaystyle \Delta {x \choose n} = {x \choose n-1}.$

This implies that we can perform a "Taylor expansion" on any polynomial to write it in the form $f(x) = \sum a_n {x \choose n}$ by evaluating the finite differences $\Delta^n f(0)$ at zero. For any particular polynomial $f$ it is easy to write these finite differences down by constructing a table. In general, the formula is

$\displaystyle a_n = \Delta^n f(0) = \sum_{k=0}^{n} (-1)^{n-k} {n \choose k} f(k)$

as one can readily prove by writing $\Delta = S - I$ where $S$ is the shift operator $S f(x) = f(x+1)$ and $I$ is the identity operator $I f(x) = f(x)$. Then the indefinite sum of $f$ is just $\sum a_n {x \choose n+1}$. This is the easiest way I know how to do such computations by hand, and it also leads to a fairly easy method for polynomial interpolation given the values of a polynomial at consecutive integers.

Answer 4

As other answers have noted, you are about to discover the calculus of finite differences.

For practical calculations, here a most useful fact: the rule

$\frac{d}{dx} x^n = n x^{n-1}$

corresponds to

$\Delta_1 x(x-1)(x-2)\cdots(x-(n-1)) = n x(x-1)(x-2)\cdots(x-(n-2))$