Sum of polynomial

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.