8
$\begingroup$

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.

$\endgroup$
1

4 Answers 4

8
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ Nothing new under the sun. But I've learned something new today. Good old Bernoulli numbers. $\endgroup$ Commented Aug 6, 2010 at 12:28
6
$\begingroup$

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.

$\endgroup$
5
$\begingroup$

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.

$\endgroup$
3
  • 2
    $\begingroup$ 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. :) $\endgroup$ Commented Aug 6, 2010 at 17:12
  • $\begingroup$ 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. $\endgroup$ Commented Aug 8, 2010 at 22:19
  • $\begingroup$ Yes, that was one property that was exploited to the hilt by the table-makers of yesteryear. :) $\endgroup$ Commented Aug 9, 2010 at 2:04
3
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ Interesting, I smell a factorial in that equation. Something like Delta x!/(x-n)! = nx!/(x-n-1)! am I right? $\endgroup$ Commented Aug 6, 2010 at 12:25
  • $\begingroup$ 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. $\endgroup$ Commented Aug 6, 2010 at 13:05

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .