An integer-valued polynomial is a polynomial with complex coefficients taking values in $\mathbb{Z}$ when all the variables take integer values. For example, $\frac{x^2+3x}{2}$ and $\frac{13x^3+5xy^2}{6}$ are integer-valued polynomials. Clearly, the set of integer-valued polynomials with variables $x_1,x_2,\ldots,x_n$ form a subring of $\mathbb{Q}\left[x_1,x_2,\ldots,x_n\right]$. A result by Polya states that the ring of integer-valued polynomials in one variable $x$ is a free abelian group with basis elements $\binom{x}{k}=\frac{x(x-1)(x-2)\cdots(x-k+1)}{k!}$ for $k=0,1,2,\ldots$.
To answer your question, $x^k$ is an integer-valued polynomial. Therefore, $x^k=\sum_{r=0}^k \,a_r\binom{x}{r}$ for some $a_0,a_1,\ldots,a_n\in\mathbb{Z}$ (obviously, $a_n\neq 0$). Now, $\sum_{m=0}^n\,m^k=\sum_{m=0}^n\,\sum_{r=0}^k\,a_r\binom{m}{r}=\sum_{r=0}^k\,a_k\,\sum_{m=0}^n\,\binom{m}{r}$. By the Hockey-Stick Identity (see http://www.artofproblemsolving.com/wiki/index.php/Combinatorial_identity#Hockey-Stick_Identity), $\sum_{m=0}^n\,m^k=\sum_{r=0}^k\,a_k\,\binom{n+1}{r+1}$. Hence, $\sum_{m=0}^n\,m^k$ is a polynomial in $n$ of degree $k+1$, as the coefficient of $n^{k+1}$ is $\frac{a_k}{(k+1)!}\neq 0$. (In fact, $a_k=k!$, so we know that $\sum_{m=0}^n\,m^k=\frac{n^{k+1}}{k+1}+\mathcal{O}\left(n^k\right)$.)
Best Answer
Use a specific example.
Let $A = 1^3 + 3^3 + 5^3 + 7^3 + 9^3.$
Let $B = 2^3 + 4^3 + 6^3 + 8^3.$
Let $C = 1^3 + 2^3 + 3^3 + 4^3.$
Assume that you want to evaluate $A$.
You can use the formula to evaluate $(A + B)$, so the problem is reduced to evaluating $B$.
This can be done by using the formula to evaluate $C$, and then reasoning that $8C = B$.