Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
I probably should have pointed out this old (but still nice) classic earlier: archive.org/details/calculusoffinite032017mbp –  J. M. Aug 9 '10 at 23:12
add comment

4 Answers

up vote 6 down vote accepted

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

share|improve this answer
    
Nothing new under the sun. But I've learned something new today. Good old Bernoulli numbers. –  Guillermo Phillips Aug 6 '10 at 12:28
add comment

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.

share|improve this answer
add comment

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.

share|improve this answer
2  
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. 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. Aug 9 '10 at 2:04
add comment

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

share|improve this answer
    
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. Aug 6 '10 at 13:05
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.