# Proof that common differences imply a polynomial-generated sequence

I have long been familiar with the method of common differences for finding the equation of a sequence: you subtract consecutive terms going down level by level, until you get a constant difference at level $n$. Then you infer that the sequence is generated by a polynomial of degree $n$ and find the coefficients.

I can also easily convince myself that a sequence generated by a polynomial of degree $n$ will have common differences at level $n$ (e.g. the proof given here).

However, it recently occurred to me that I have never seen a proof in the other direction: given that the differences at level $n$ are a constant (say, $C$), a polynomial of degree $n$ is the unique solution for the sequence equation.

I have thought of the following proof:

1. Prove by any means other than common differences that the sum of the $n^\text{th}$ power of the first $k$ integers is a polynomial of degree $(n+1)$ (e.g. use Gauss' trick for $n=1$, and some other trick for higher $n$, like $\sum_{i=1}^{k} i^{n+1} = \sum_{i=1}^{k} (i-1)^{n+1} + k^{n+1}$).

2. Then it's fairly easy to conclude that starting from a common difference at level $n$ and summing up at each level, you end up with a polynomial of degree $n$ at the first level.

My questions are:

1. Is my concern valid to begin with? Or should it be obvious because I'm missing something?
2. Is my proof valid?
3. Are there cleaner proofs?
4. Is this related to the issue of uniqueness of solutions to differential equations? (I guess so)
5. It says on Wikipedia that difference equations can be solved analogously to differential equations, but I can't see how. Any pointers would be appreciated!