Proof request: If a function satisfies a polynomial recurrence then it is a polynomial Suppose we would like to find a formula for some interesting real-valued function on the positive integers $f(n):\mathbb{Z}^+\rightarrow\mathbb{R}$, and we have the inductive equation
$$\forall n\in\mathbb{Z}^+,\quad f(n+1)=f(n)+p(n)$$
for some polynomial $p(x):\mathbb{R}\rightarrow\mathbb{R}$. It should be intuitively obvious that $f(n)$ is also a polynomial, or at least that there exists a polynomial which is equal to $f(n)$ on the positive integers. Let $q(x):\mathbb{R}\rightarrow\mathbb{R}$ be such a polynomial:
$$ \forall n\in\mathbb{Z}^+,\quad f(n)=q(n) $$
Furthermore, the degree of $q(x)$ is one more than the degree of $p(x)$:
$$ \deg q(x) = \deg p(x) + 1$$
This allows the use of polynomial interpolation with the first $d+1$ points of $f(n)$ to calculate the coefficients of $q(x)$, and thus find a formula for $f(n)$. I would like a proof for the existence of the polynomial $q(x)$.

Proposition: If $f(n):\mathbb{Z}^+\rightarrow\mathbb{R}$ is a function such that there exists a polynomial $p(x):\mathbb{R}\rightarrow\mathbb{R}$ of degree $d$ such that
  $$\forall n\in\mathbb{Z}^+,\quad f(n+1)=f(n)+p(n)$$
  then there exists a polynomial $q(x):\mathbb{R}\rightarrow\mathbb{R}$ of degree $d+1$ such that $f(n)=q(n)$ for all $n\in\mathbb{Z}^+$.

For example, let $f(n):\mathbb{Z}^+\rightarrow\mathbb{R}$ be the sum-of-squares function defined
$$f(n) = \sum_{k=1}^{n} k^2$$
For all positive integers $n\in\mathbb{Z}^+$, the function $f(n)$ satisfies the equation
$$f(n+1)=f(n)+(n+1)^2$$
Let $p(x)$ be the polynomial of degree $2$ defined $p(x)=(x+1)^2$ for all $x\in\mathbb{R}$. From the proposition, there exists a polynomial $q(x)$ of degree $3$ such that $f(n)=q(n)$ for all $n\in\mathbb{Z}^+$. Thus, we can use polynomial interpolation with the points $f(1)=1$, $f(2)=5$, $f(3)=14$, and $f(4)=30$ to calculate the coefficients of $q(x)$. This yields:
$$q(x) = \frac{1}{3}x^3 + \frac{1}{2}x^2 + \frac{1}{6}x$$
For $n\in\mathbb{Z}^+$, this matches the standard formula: $$f(n)=\frac{n(n+1)(2n+1)}{6}$$
This is a simple example, but this technique has helped me obtain formulas for complex recurrences simply by knowing what degree it will have.
 A: Since $f(n+1)-f(n)=p(n)$, we have:
$$f(n)=f(n-1)+p(n-1)=f(n-2)+p(n-2)+p(n-1)=...=f(1)+\sum_{i=1}^{n-1} p(i)$$
Thus, since $f(1)$ is a constant, we need to show $\sum_{i=1}^{n-1} p(n-1)$ is a polynomial of degree $k+1$, where $p$ is of degree $k$. Let $p(x)=\sum_{j=0}^k p_jx^j$, where $p_j$ are the coefficients of $p$. Thus, we have:
$$f(n)=f(1)+\sum_{i=1}^{n-1}\sum_{j=0}^kp_ji^j$$
Switch the order of summation:
$$f(n)=f(1)+\sum_{j=0}^k\sum_{i=1}^{n-1}p_ji^j$$
Now, by Faulhaber's Formula, $\sum_{i=1}^{n-1}p_ji^j$ is a polynomial of degree $j+1$ in terms of $n$. Thus, we are adding a polynomial of degree $0+1=1$ plus a polynomial of degree $1+1=2$ plus ... a polynomial of degree $k+1$. When we add polynomials of different degrees, the degree of the resulting polynomial is the maximum of the degree of the addends (i.e. a polynomial of degree $5$ plus a polynomial of degree $3$ is a polynomial of degree $5$). Thus, the resulting polynomial has degree $k+1$, which is exactly what we set out to prove.
A: If $f : \Bbb{Z} \to \Bbb{Z}$, let $\Delta f$ be defined by:
$$
\Delta f(n) = f(n) - f(n-1).
$$
Then, $f$ is a polynomial function of degree $d$ iff $\Delta f$ is a polynomial function of degree $d - 1$. For your recurrence relation:
$$
f(n+1) = f(n) + p(n)
$$
where $p$ is a polynomial of degree $d$, $\Delta^d f$ will be a constant function implying that $f$ is a polynomial function of degree $d+1$.
(The above is very well-known and I am amazed that I can't find a link to an online reference for it. But searches for "method of differences", which is what I call the above theory, don't hit the spot.)
A: In my opinion, 
here is the easiest way to prove that,
if $p(n)$ is a
polynomial of degree $d$,
then
$q(n)
=\sum_{k=0}^n p(k)$
is a polynomial
of degree $d+1$.
Let
$f_d(n)
=\prod_{k=0}^{d} (n-k)
$.
This is a polynomial
of degree $d+1$ in $n$.
Then
$\begin{array}\\
f_d(n+1)-f_d(n)
&=\prod_{k=0}^{d} (n+1-k)-\prod_{k=0}^{d} (n-k)\\
&=\prod_{k=0}^{d} (n+1-k)-\prod_{k=1}^{d+1} (n-(k-1))\\
&=\prod_{k=0}^{d} (n+1-k)-\prod_{k=1}^{d+1} (n+1-k)\\
&=(n+1)\prod_{k=1}^{d} (n+1-k)-(n+1-(d+1))\prod_{k=1}^{d} (n+1-k)\\
&=(n+1)\prod_{k=1}^{d} (n+1-k)-(n-d)\prod_{k=1}^{d} (n+1-k)\\
&=(n+1-(n-d))\prod_{k=1}^{d} (n+1-k)\\
&=(d+1)\prod_{k=0}^{d-1} (n+1-(k+1))\\
&=(d+1)\prod_{k=0}^{d-1} (n-k)\\
&=(d+1)f_{d-1}(n)\\
\end{array}
$
This shows that,
for this particular type of polynomial,
the difference of
a polynomial of degree $d+1$
is a polynomial of degree $d$.
This, in turn,
can be used to show
by induction
that
the difference of
a general polynomial of degree $d+1$
is a polynomial of degree $d$.
Summing this shows that
the sum of a polynomial
of degree $d$
is a polynomial of degree $d+1$.
