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

  • $\begingroup$ Have you tried induction? It is a messy way, but would certainly work. I don't see any other way to attack the problem, though. $\endgroup$ – u1571372 Nov 9 '16 at 2:12

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


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$ is a polynomial of degree $m$ in $n$, so





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.

  • $\begingroup$ +1. This is the path I'll take about it. I don't know ( I didn't work out anything ) but maybe it's better to start with the $n^{k}$-integral representation. $\endgroup$ – Felix Marin Nov 9 '16 at 20:45

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 $


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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.