# How do you calculate a sum over a polynomial?

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

#### Solutions Collecting From Web of "How do you calculate a sum over a polynomial?"

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.

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.