30
$\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$
  • $\begingroup$ Are you asking how sums like $\sum_{i=0}^{n} p(i)$ can be calculated in general? $\endgroup$ – Antonio Vargas Sep 11 '15 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$ – Esoemah Sep 11 '15 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$ – Antonio Vargas Sep 11 '15 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$ – Antonio Vargas Sep 11 '15 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$ – Hurkyl Sep 11 '15 at 17:01
38
$\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$
  • 8
    $\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$ – Steven Stadnicki Sep 11 '15 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$ – John Hughes Sep 14 '15 at 20:16
  • $\begingroup$ Doesn't all this procedure remind a little: integrals and derivatives? $\endgroup$ – Widawensen Jul 1 '16 at 7:53
12
$\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$
  • $\begingroup$ I think the question was about inverting the summation, rather than computing it. I asked the author about this in the comments. $\endgroup$ – Antonio Vargas Sep 11 '15 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 '15 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 '15 at 17:46
  • $\begingroup$ Brilliant. Also thanks for the Euler-Maclaurin Sum Formula. $\endgroup$ – NoChance Sep 14 '15 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.