# Indefinite summation of polynomials

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': $$\mathrm{diff}\left(x^{2}\right)=x^{2}-\left(x-1\right)^{2}=2x-1$$

I can see from this that I nearly have my answer, so assuming an inverse 'integration' operation and re-arranging: $$\frac{1}{2}\mathrm{diff}\left(x^{2}+\mathrm{int}\left(1\right)\right)=x$$

Now, I know that the 'indefinite integral' of 1 is just x, from 'differentiating' $x-(x-1) = 1$. So ultimately: $$\frac{1}{2}\left(x^{2}+x\right)=\mathrm{int}\left(x\right)$$

So to get my answer I take the 'definite' integral: $$\mathrm{int}\left(x\right):10,20=\frac{1}{2}\left(20^{2}+20\right)-\frac{1}{2}\left(9^{2}+9\right)=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 the odd notation.

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}

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

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

• Nothing new under the sun. But I've learned something new today. Good old Bernoulli numbers. – Guillermo Phillips Aug 6 '10 at 12:28

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.

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.

• The finite-difference analog of the Taylor series is the Newton series, which comes in forward- and backward-difference flavors. Personally I prefer writing the series using rising/falling factorials (which are of course trivially related to the binomial coefficient), but I guess I'm just an old softie. :) – J. M. is a poor mathematician Aug 6 '10 at 17:12
• For me using Newton polynomials has one major advantage: f(x) takes integer values at the integers if and only if the coefficients a_n are integers. – Qiaochu Yuan Aug 8 '10 at 22:19
• Yes, that was one property that was exploited to the hilt by the table-makers of yesteryear. :) – J. M. is a poor mathematician Aug 9 '10 at 2:04

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))$

• Interesting, I smell a factorial in that equation. Something like Delta x!/(x-n)! = nx!/(x-n-1)! am I right? – Guillermo Phillips Aug 6 '10 at 12:25
• Actually, what crops up frequently in finite-difference calculus are the so-called "rising" and "falling" factorials, which are in fact generalizations of the normal factorial. They satisfy identities related to the finite-difference operator much similar to the identities involving differentiation and the power function. – J. M. is a poor mathematician Aug 6 '10 at 13:05