How do you calculate a sum over a polynomial?

$\begingroup$

I know that given a polynomial $p(i)$ of degree $d$, the sum $\sum_{i=0}^n p(i)$ would have a degree of $d + 1$. So for example

$$ \sum_{i=0}^n \left(2i^2 + 4\right) = \frac{2}{3}n^3+n^2+\frac{13}{3}n+4. $$

I can't find how to do this the other way around. What I mean by this, is how can you, when given a polynomial, calculate the polynomial which sums to it?

For example, if we know that

$$ \sum_{i=0}^{n} p(i) = 2n^3 + 4n^2 + 2,$$

how can we find the polynomial $p(i)$?

$\endgroup$ 9

2 Answers

$\begingroup$

To rephrase, I believe the question is this:

Suppose that polynomials $p$ and $q$ have the property that $$ \sum_{i=0}^n p(i) = q(n) $$ If you're given $q$, how can you find $p$?

First, this is a lovely question. I'd never really considered it, because we almost always study instead "if you know $p$, how do you find $q$?"

To answer though, turns out to be fairly simple. Write the following: \begin{align} q(n-1) &= p(0) + p(1) + \ldots + p(n-1) \\ q(n) &= p(0) + p(1) + \ldots + p(n-1) + p(n) \\ \end{align}

Now subtract the top from the bottom to get \begin{align} q(n) - q(n-1) &= p(n) \end{align}

As an example, in your case if we knew $$ q(n) = 2n^3 + 4n^2 + 2 $$ we'd find that $$ p(n) = q(n) - q(n-1) = 2n^3 + 4n^2 + 2 - [2(n-1)^3 + 4(n-1)^2 + 2], $$ which you simplifies to $$ p(n) = 6n^2 +2n - 2. $$

Let's do an example: we know that for $p(n) = n$, we have $q(n) = \frac{n(n+1)}{2}$. So suppose we were given just $q$. We'd compute \begin{align} q(n) - q(n-1) &= \frac{n(n+1)}{2} - \frac{(n-1)(n)}{2} \\ &= \frac{n^2 + n}{2} - \frac{n^2 - n}{2} \\ &= \frac{n^2 + n-(n^2 - n)}{2} \\ &= \frac{n^2 + n- n^2 + n}{2} \\ &= \frac{2n}{2} \\ &= n, \end{align} so that $p(n) = n$, as expected.

Note: As written, I've assumed that $p$ and $q$ are both polynomials. But the solution shows that if $q$ is a polynomial, then $p$ must also be a polynomial, which is sort of pleasing.

Post-comment remarks

As @Antonio Vargas points out, though, there's an interesting subtlety:

I've given a correct answer to my revised question, which was "If there are polynomials $p$ and $q$ satisfying a certain equality, then how can one find $p$ given $q$."

But suppose that there is no such polynomial $p$. My answer still computes an expression which $p$, if it existed, would have to match. But since no such $p$ exists, the computed expression has no value.

Or maybe I should say that it has a limited value: you can take the polynomial $p$ and compute its sum using inductive techniques and see whether you get $q$. If so, that's great; if not, then there wasn't any answer in the first place.

Fortunately, you can also do that "Does it really work" check much more simply. You just need to check the the $n = 0$ case: if $$ \sum_{i = 0}^0 p(i) = q(0) $$ then all higher sums will work as well. And this check simplifies to just asking: is $$ p(0) = q(0)? $$ In our example, $p(0) = -2$, while $q(0) = +2$, so it doesn't work out.

$\endgroup$ 3 $\begingroup$

Which Polynomials Can Be Written as a Sum

By summing a Telescoping Series, we get $$ \begin{align} \sum_{k=0}^n(p(k)-p(k-1)) &=\sum_{k=0}^np(k)-\sum_{k=0}^np(k-1)\\ &=\sum_{k=0}^np(k)-\sum_{k=-1}^{n-1}p(k)\\ &=p(n)-p(-1) \end{align} $$ It turns out that not every polynomial can be written as a sum of other polynomials. To be written as a sum of polynomials $$ p(n)=\sum_{k=0}^nq(k) $$ we must have $p(-1)=0$, and if that condition holds, then $q(k)=p(k)-p(k-1)$.

---

Finite Differences

$q(k)=p(k)-p(k-1)=\Delta p(k)$ is the first Backward Finite Difference of $p$.

Using the Binomial Theorem, we get the first backward finite difference of $x^n$ to be $$ \Delta x^n=x^n-(x-1)^n=\sum_{k=0}^{n-1}(-1)^{n-k-1}\binom{n}{k}x^k $$ This shows that the first backward finite difference of a degree $n$ polynomial is a degree $n-1$ polynomial.

Thus, for $$ p(k)=2k^3+4k^2+2 $$ we have $$ \begin{align} \Delta p(k) &=2\overbrace{\left[3k^2-3k+1\right]}^{\Delta k^3}+4\overbrace{\left[\vphantom{k^2}2k-1\right]}^{\Delta k^2}+2\overbrace{\left[\vphantom{k^2}\ \ \ 0\ \ \ \right]}^{\Delta 1}\\ &=6k^2+2k-2 \end{align} $$ However, since $p(-1)=4$, we have $$ \sum_{k=0}^n(6k^2+2k-2)=2n^3+4n^2-2 $$ which is not $p(n)$. That is,

There is no polynomial $q(n)$ so that $\sum\limits_{k=0}^nq(k)=2n^3+4n^2+2$

---

Previous Question

The answer below was posted before the question was changed. It was

The other way around however, I'm still a bit lost. For example, given the polynomial $p(i) = 2i^3 + 4i^2 + 2$, how would you find $\sum_{i=0}^n p(i)$?

So what follows may seem to be off-topic.

---

There are several ways to approach this problem.

Binomial Polynomials

One is by writing the polynomial as a binomial polynomial: $$ 2k^3+4k^2+2=12\binom{k}{3}+20\binom{k}{2}+6\binom{k}{1}+2\binom{k}{0} $$ Then use the formula $$ \sum_{k=0}^n\binom{k}{m}=\binom{n+1}{m+1} $$ to get $$ \begin{align} \sum_{k=0}^n\left(2k^3+4k^2+2\right) &=12\binom{n+1}{4}+20\binom{n+1}{3}+6\binom{n+1}{2}+2\binom{n+1}{1}\\ &=\frac{3n^4+14n^3+15n^2+16n+12}6 \end{align} $$

---

Euler-Maclaurin Sum Formula

In most cases, the Euler-Maclaurin Sum Formula is an asymptotic approximation, but in the case of polynomials, it is exact. $$ \sum_{k=0}^nf(k)\sim C+\int_0^nf(x)\,\mathrm{d}x+\frac12f(n)+\frac1{12}f'(n)-\frac1{720}f'''(n)+\frac1{30240}f^{(5)}(n)+\dots $$ where subsequent terms involve higher derivatives, which for polynomials will eventually vanish. In the case at hand, this gives the same answer as above.

$\endgroup$ 4

Your Answer

Sign up or log in

Sign up using Google Sign up using Facebook Sign up using Email and Password Submit

Post as a guest

Post Your Answer Discard

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy