How to prove a formula involving polynomial sequences and their recursive representation

Question

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

Answer 1

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}\;.$$

Answer 2

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.

Answer 3

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$.