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

  • $\begingroup$ Are you asking how sums like $\sum_{i=0}^{n} p(i)$ can be calculated in general? $\endgroup$ Sep 11, 2015 at 15:42
  • $\begingroup$ @AntonioVargas I'm asking how a polynomial can be written as a Sigma notation. So for example, the polynomial $2/3n^3+n^2+13/3n+4$ can be written as $\sum_{i=0}^n 2i^2 + 4$, but I have no idea how you would start. $\endgroup$
    – vwos
    Sep 11, 2015 at 15:46
  • $\begingroup$ Okay, maybe the last part of the question should be written a little differently then. Is this your question?: If we know that $\sum_{i=0}^{n} p(i) = 2n^3 + 4n^2 + 2$, how can we find the polynomial $p(i)$? $\endgroup$ Sep 11, 2015 at 15:48
  • 2
    $\begingroup$ Great, I've edited the question to try to clarify it. If you'd like you can also edit it by clicking the "edit" link just below the list of tags at the bottom of the question. $\endgroup$ Sep 11, 2015 at 16:00
  • 4
    $\begingroup$ Short answer:$$p(n) = \left( \sum_{i=0}^n p(i) \right) - \left( \sum_{i=0}^{n-1} p(i) \right)$$ $\endgroup$
    – user14972
    Sep 11, 2015 at 17:01

2 Answers 2


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.

  • 9
    $\begingroup$ It is, by the way, a nice exercise to show that if $q$ is a degree-$d$ polynomial, then $p(n)=q(n)-q(n-1)$ is a degree-$(d-1)$ polynomial. This operation is known as finite differencing and there are many close analogs with differentiation. $\endgroup$ Sep 11, 2015 at 16:10
  • $\begingroup$ Nice point; I've added further remarks. My test for whether things work out is that $p(0) = q(0)$ rather than that $p(-1) = 0$, but that's a tiny difference. $\endgroup$ Sep 14, 2015 at 20:16
  • $\begingroup$ Doesn't all this procedure remind a little: integrals and derivatives? $\endgroup$
    – Widawensen
    Jul 1, 2016 at 7:53

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.

  • $\begingroup$ I think the question was about inverting the summation, rather than computing it. I asked the author about this in the comments. $\endgroup$ Sep 11, 2015 at 16:01
  • $\begingroup$ Ah, I see the question has been changed. When I read it, it seemed as though the main question was the other way around: I have added a caveat to my answer. $\endgroup$
    – robjohn
    Sep 11, 2015 at 16:11
  • 1
    $\begingroup$ Now I have answered the new question. Unfortunately, there is no $q$ so that $p(n)=\sum\limits_{k=0}^nq(k)$ for this particular $p$. $\endgroup$
    – robjohn
    Sep 11, 2015 at 17:46
  • $\begingroup$ Brilliant. Also thanks for the Euler-Maclaurin Sum Formula. $\endgroup$
    – NoChance
    Sep 14, 2015 at 20:21

Your Answer

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

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