Sum of polynomial

Question

If $p(x)$ is a polynomial of degree $m$, does the polynomial $q(x)$ of degree $m+1$ exist so that $\sum_{i=0}^{n}p(i)=q(n)$? And if so, is there an algorithm to find the expression for $q(x)$?

Answer 1

Both questions can be answered in affirmative. Falling factorials are one of the many approaches that can be used both for proving the first part and providing an algorithm for the second part at the same time.

Let $x^{\underline{n}}$ denote the falling factorial; product of $n$ numbers starting from $x$ and decreasing by $1$ in every step: $$ x^{\underline{n}}=\prod_{k=0}^{n-1}(x-k)=x(x-1)(x-2)\ldots(x-n+1)$$

Thus, for example, we have $$\begin{eqnarray} x^{\underline{0}} & & & = & 1 \\ x^{\underline{1}} & & & = & x \\ x^{\underline{2}} & = & x(x-1) & = & x^2-x\\ x^{\underline{3}} & = & x(x-1)(x-2) & = & x^3 - 3x^2 + 2x\\ \end{eqnarray}$$

Since $x^{\underline{n}}$ is a polynomial of degree $n$, it's not too difficult to see that any polynomial can be rewritten as a combination of falling factorials. For example, consider $p(x)=3x^2-x+5$:

$$p(x) = 3x^2 - x + 5 = 3x^{\underline{2}} + 2x+5 = 3x^{\underline{2}} + 2x^\underline{1} + 5 = 3x^{\underline{2}} + 2x^\underline{1} + 5x^\underline{0}$$

In each step, we eliminated the highest power of $x$, replacing it with the respective falling factorial and adjusting the remaining coefficients.

What makes the falling factorials interesting is that when it comes to summation, they behave very much like regular powers in integration:

$$\sum_{x=0}^{n-1} x^{\underline{k}} = \frac{1}{k+1}n^{\underline{k+1}}$$ (provable by a straightforward mathematical induction over $n$)

Thus, if we want to calculate $$q(n)=\sum_{i=0}^{n} p(i)$$ and we know $p(x)$'s representation using falling factorials, we just need to replace every $x^{\underline{k}}$ by $\frac{1}{k+1}(n+1)^{\underline{k}}$ (note that summing up to $n$, inclusive, yields $(n+1)$ in the result). In our example:

$$q(n)=\sum_{i=0}^n p(i)=\sum_{i=0}^n (3i^{\underline{2}} + 2i^\underline{1} + 5i^\underline{0})=(n+1)^{\underline{3}} + (n+1)^\underline{2} + 5(n+1)^\underline{1}$$

This is already sufficient to calculate the value of the sum efficiently (in fact, it can be evaluated efficiently in a way very similar to Horner's scheme), but if we really wanted, we can express it back in the standard form:

$$q(n)=(n+1)^{\underline{3}} + (n+1)^\underline{2} + 5(n+1)^\underline{1}=n^3+n^2+5n+5=(n+1)(n^2+5)$$

Since the described algorithm (express using falling factorials, "integrate", express using standard powers) works for any polynomial and the "integration" step increases the degree of the polynomial just by one, we've both proved that $q(n)$ is of degree $(m+1)$ and found an algorithm for computing it.

Answer 2

Just adding a bit of a more linear algebraic flavour. Assume we vectorize the coefficients of the polynomial like this: $$p(x) = c_0+c_1x+\cdots c_nx^n \rightarrow [c_0,c_1 \cdots c_n]^T$$

If you furthermore evaluate the polynomial in these points, call the vector $I = [p(1),p(2) \cdots]^T$. You can now write it as a matrix equation system

$$M\text{diag}(p)I = Wq$$

Where M is a triangular matrix with ones on and below the diagonal and zeros elsewhere. W is the matrix of integer monomials first row $1^0,2^0 ...$ second row $2^0, 2^1 ...$. Now we can use our knowledge of linear algebra to further manipulate and solve this. Actually may be more convenient to write it like

$$MWp = Wq$$

Well the point is anyway that both M and W matrices are very redundant. But that is like details you can probably figure out on your own. Making good choices of how to and in what order do calculations involving M and W and to solve the system probably corresponds to the great detailed answer you have already gotten.