How to prove a formula involving polynomial sequences and their recursive representation If we have a sequence defined by the polynomial $a_n=\displaystyle \sum_{k=0}^{m}c_kn^k$, then how can we prove that $a_n=\displaystyle \sum_{k=1}^{m+1}\binom{m+1}{k} (-1)^{k-1}a_{n-k}$?
*Edited to fix the typo, and also simplified
 A: The LHS is $$a_n = \sum_{k=0}^m c_k  n^k$$ and the RHS is (typo in the
leading term corrected)
$$(-1)^{m} a_{n-m-1}
+\sum_{p=1}^m {m+1\choose p} (-1)^{p-1} a_{n-p}.$$
Following @MartyCohen we merge these two to get
$$\sum_{p=1}^{m+1} {m+1\choose p} (-1)^{p-1} a_{n-p}.$$
This is
$$\sum_{p=1}^{m+1} {m+1\choose p} (-1)^{p-1} 
\sum_{k=0}^m c_k (n-p)^k
\\ = \sum_{k=0}^m c_k
\sum_{p=1}^{m+1} {m+1\choose p} (-1)^{p-1} (n-p)^k.$$
Working with the inner sum we introduce
$$(n-p)^k =
\frac{k!}{2\pi i}
\int_{|z|=\epsilon} \frac{1}{z^{k+1}} \exp((n-p)z) \; dz.$$
This yields for the double sum
$$\sum_{k=0}^m c_k
\frac{k!}{2\pi i}
\int_{|z|=\epsilon} \frac{1}{z^{k+1}}
\sum_{p=1}^{m+1} {m+1\choose p} (-1)^{p-1} \exp((n-p)z) \; dz
\\ = -\sum_{k=0}^m c_k
\frac{k!}{2\pi i}
\int_{|z|=\epsilon} \frac{1}{z^{k+1}} \exp(nz)
\sum_{p=1}^{m+1} {m+1\choose p} (-1)^{p} \exp(-pz) \; dz.$$
The inner sum is
$$(1-\exp(-z))^{m+1} - 1.$$
We thus require
$$k! [z^k] \exp(nz) (1-\exp(-z))^{m+1} - k! [z^k] \exp(nz).$$
There   are   two  pieces   here.    Since  $1-\exp(-z)   =   z   -
\frac{1}{2}z^2+\cdots$ the exponentiated  component of the first piece
starts at $z^{m+1}.$ But $k\le m$ so we have a contribution of zero.
The second piece yields $$-n^k.$$
The result then becomes
$$\sum_{k=0}^m c_k n^k = a_n$$
which is the claim.
A: Let $\langle a_n:n\in\Bbb Z\rangle$ be a bi-infinite sequence. For $n\in\Bbb Z$ let $\nabla a_n=a_n-a_{n-1}$; $\nabla$ is the backward difference operator, and it’s not hard to see that it’s linear. Then
$$\nabla^ma_n=\sum_{k=0}^m\binom{m}k(-1)^ka_{n-k}$$
for all $m\in\Bbb Z^+$ and $n\in\Bbb Z$. This is easily proved by induction on $m$; the induction step is
$$\begin{align*}
\sum_{k=0}^m\binom{m}k(-1)^k(a_{n-k}-a_{n-k-1})&=\sum_{k=0}^m\binom{m}k(-1)^ka_{n-k}-\sum_{k=0}^m\binom{m}k(-1)^ka_{n-(k+1)}\\
&=\sum_{k=0}^m\binom{m}k(-1)^ka_{n-k}+\sum_{k=1}^{m+1}\binom{m}{k-1}(-1)^ka_{n-k}\\
&=\sum_{k=0}^{m+1}\left(\binom{m}k+\binom{m}{k-1}\right)(-1)^ka_{n-k}\\
&=\sum_{k=0}^{m+1}\binom{m+1}k(-1)^ka_{n-k}\;.
\end{align*}$$
Next note that
$$\begin{align*}
\nabla n^k&=n^k-(n-1)^k\\
&=n^k-\sum_{\ell=0}^k\binom{k}\ell(-1)^\ell n^{k-\ell}\\
&=\sum_{\ell=1}^k\binom{k}\ell(-1)^{\ell+1}n^{k-\ell}\\
&=kn^{k-1}+\sum_{\ell=2}^k(-1)^{\ell+1}n^{k-\ell}\;,
\end{align*}$$
and an easy proof by induction shows that $\nabla^kn^k=k!$, and $\nabla^mn^k=0$ for $m>k$.
Now let
$$a_n=\sum_{k=0}^mc_kn^k\;;$$
$a_n$ is a polynomial of degree $m$ in $n$, so
$$0=\nabla^{m+1}a_n=\sum_{k=0}^{m+1}\binom{m+1}k(-1)^ka_{n-k}\;,$$
and
$$a_n=\sum_{k=1}^{m+1}\binom{m+1}k(-1)^{k-1}a_{n-k}\;.$$
A: Here is a proof
based on 
the start of
Marko Riedel's proof
that only uses
standard algebra
and the fact that
the $m$-th difference
of $x^k$ is zero
if
$m> k$.
The LHS is $$a_n = \sum_{k=0}^m c_k  n^k$$ and the RHS is (typo in the
leading term corrected
and the term
$p=m+1$ placed in the sum)
$s_n
=\sum_{p=1}^{m+1} {m+1\choose p} (-1)^{p-1} a_{n-p}
$.
The sum is
$\begin{array}\\
s_n
&=\sum_{p=1}^{m+1} {m+1\choose p} (-1)^{p-1} 
\sum_{k=0}^m c_k (n-p)^k\\
&= \sum_{k=0}^m c_k
\sum_{p=1}^{m+1} {m+1\choose p} (-1)^{p-1} (n-p)^k\\
&= \sum_{k=0}^m c_k
\sum_{p=1}^{m+1} {m+1\choose p} (-1)^{p-1} \sum_{j=0}^k \binom{k}{j}n^j(-p)^{k-j}\\
&= \sum_{k=0}^m c_k
\sum_{p=1}^{m+1} {m+1\choose p} (-1)^{p-1} \sum_{j=0}^k \binom{k}{j}n^j(-1)^{k-j}p^{k-j}\\
&= \sum_{k=0}^m c_k 
\sum_{j=0}^k \binom{k}{j}(-1)^{k-j}n^j
\sum_{p=1}^{m+1} {m+1\choose p} (-1)^{p-1} p^{k-j}\\
&=\sum_{j=0}^m 
\sum_{k=j}^m c_k \binom{k}{j}(-1)^{k-j}n^j
\sum_{p=1}^{m+1} {m+1\choose p} (-1)^{p-1} p^{k-j}\\
&=\sum_{j=0}^m n^j
\sum_{k=j}^m c_k \binom{k}{j}(-1)^{k-j}
\sum_{p=1}^{m+1} {m+1\choose p} (-1)^{p-1} p^{k-j}\\
&=\sum_{j=0}^m n^j
\sum_{k=0}^{m-j} c_{k+j} \binom{k+j}{j}(-1)^{k}
\sum_{p=1}^{m+1} {m+1\choose p} (-1)^{p-1} p^{k}\\
\end{array}
$
so we are done if
we can show that
$c_j
=\sum_{k=0}^{m-j} c_{k+j} \binom{k+j}{j}(-1)^{k}
\sum_{p=1}^{m+1} {m+1\choose p} (-1)^{p-1} p^{k}
$
or,
splitting this
into the
cases $k=0$
and $k > 0$,
$ \sum_{p=1}^{m+1} {m+1\choose p} (-1)^{p-1} 
= 1
$
and
$ \binom{k+j}{j}(-1)^{k}
\sum_{p=1}^{m+1} {m+1\choose p} (-1)^{p-1} p^{k}
= 0
$.
The case $k=0$ is
$\begin{array}\\
0
&=1+\sum_{p=1}^{m+1} {m+1\choose p} (-1)^{p}\\
&=\sum_{p=0}^{m+1} {m+1\choose p} (-1)^{p}\\
&=(1-1)^{m+1}
\end{array}
$
which is true.
The case $k>0$
is true if
$ 0
=\sum_{p=1}^{m+1} {m+1\choose p} (-1)^{p-1} p^{k}
$
which is true if
$ 0
=\sum_{p=0}^{m+1} {m+1\choose p}(-1)^p p^{k}
$
since $p^k = 0$
for $p=0$ and $k > 0$.
But this is true
since it states that
the $m+1$ difference
of $x^k$
is zero,
and this is true since
$k \le m$.
