Clarification on how to prove polynomial representations exist for infinite series With reference to this question, I would like a clarification of the comment given by @Ant (but someone else could answer instead). I basically have 2 questions:


*

*Is there any formal way to prove that there exists a polynomial representation for the sum of the first $n$ natural numbers to the $m^{th}$ power ($1^m+2^m+3^m+\cdots+n^m$) without actually finding the representation?

*Is/Are there any general method(s) used to prove whether an infinite series can be represented as a function and/or a polynomial?

 A: Proof for the first question.
We want to prove that for all $m \in \mathbb N$, 
$$\sum\limits_{i=1}^n i^m=P_{m+1}(n)$$
where $P_j(x)$ represents a polynomial of degree $j$ in $x$. We will use induction. Clearly the statement is true when $m=1$ and $m=0$. Let's assume it is true for all $m$ until some $m=k-1$. We need to show it's also true for $m=k$.
Consider the sum
$$\sum\limits_{i=1}^n i^{k+1}-(i-1)^{k+1}$$
The terms cancel out and we're left with this $n^{k+1}$. But if we simplify each term separately, we get 
$$\sum\limits_{i=1}^n 1(n^{k}+n^{k-1}(n-1)+n^{k-2}(n-2)^2 \cdots + (n-1)^k)$$ or collecting them terms together
$$\sum\limits_{i=1}^n a_kn^k+a_{k-1}n^{k-1} + \cdots  +a_0$$
Since we just rearranged the original sum, both the results must be equal. We get,
$$\sum\limits_{i=1}^n n^k=\frac{n^{k+1}-\sum\limits_{i=1}^n a_{k-1}n^{k-1} + \cdots  +a_0}{a_k}$$
By strong induction, the term on the right hand side has to be a polynomial, hence, the left hand side term is also a polynomial of degree $k+1$.
