# If $a_n = \sum\limits_{r=0}^n \binom{n}{r} b_r$, prove $(-1)^n b_n = \sum\limits_{s=0}^n \binom{n}{s} (-1)^s a_s$

Suppose that sequences of real numbers satisfy:

\begin{align*} a_n &= \sum\limits_{r=0}^n \binom{n}{r} b_r \\ \end{align*}

Prove that:

\begin{align*} (-1)^n b_n &= \sum\limits_{s=0}^n \binom{n}{s} (-1)^s a_s \\ \end{align*}

My work:

The $n=0$ case:

\begin{align*} a_0 &= b_0 \\ b_0 &= a_0 \\ \end{align*}

Then $n=1$ case:

\begin{align*} a_1 &= \binom{1}{0} b_0 + \binom{1}{1} b_1 = b_0 + b_1 \\ -b_1 &= \binom{1}{0} a_0 - \binom{1}{1} a_1 = a_0 - a_1 \\ b_1 &= a_1 - a_0 = b_0 + b_1 - a_0 = b_1 \\ \end{align*}

The inductive step:

\begin{align*} (-1)^{n+1} b_{n+1} &= \sum\limits_{s=0}^{n+1} \binom{n+1}{s} (-1)^s a_s \\ \end{align*}

I'm not sure where to go from here. I tried substituting $a_s$ into that last equation and it didn't help. Any ideas?

See binomial transform for more details. Here's a proof using (exponential) generating series.

Let

$$B(x) = \sum_{n = 0}^\infty b_n \frac{x^n}{n!}$$

be the exponential generating series for $(b_n)$.

Then

\begin{align} e^x B(x) &= \left( \sum_{i = 0}^\infty \frac{x^i}{i!} \right)\left( \sum_{j = 0}^\infty b_j \frac{x^j}{j!} \right) \\ &= \sum_{n = 0}^\infty \left( \sum_{i + j = n} b_j \frac{x^i}{i!}\frac{x^j}{j!} \right) \\ &= \sum_{n = 0}^\infty \left( \sum_{k = 0}^n b_k \frac{x^{n - k}}{(n - k)!}\frac{x^{k}}{k!} \right) \\ &= \sum_{n = 0}^\infty \left( \sum_{k = 0}^n b_k \frac{n!}{(n - k)!k!} \right) \frac{x^{n}}{n!} \\ &= \sum_{n = 0}^\infty a_n \frac{x^n}{n!} = A(x). \end{align}

Where $A(x)$ is the exponential generating series for $(a_n)$. That is,

$$\color{purple}{A(x) = e^x B(x)}$$

and conversely,

$$B(x) = e^{-x} A(x). \tag{*}$$

The product $e^{-x} B(x)$ can be written as

\begin{align} e^{-x} A(x) &= \left( \sum_{i = 0}^\infty (-1)^{i}\frac{x^i}{i!} \right)\left( \sum_{j = 0}^\infty a_j \frac{x^j}{j!} \right) \\ &= \sum_{n = 0}^\infty \left( \sum_{i + j = n} (-1)^i a_j \frac{x^i}{i!}\frac{x^j}{j!} \right) \\ &= \sum_{n = 0}^\infty \left( \sum_{k = 0}^n (-1)^{n - k}a_k \frac{x^{n - k}}{(n - k)!}\frac{x^{k}}{k!} \right) \\ &= \sum_{n = 0}^\infty \left( (-1)^n \sum_{k = 0}^n (-1)^{k}a_k \frac{n!}{(n - k)!k!} \right) \frac{x^{n}}{n!} \\ &= B(x) = \sum_{n = 0}^\infty b_n \frac{x^n}{n!} \tag{by ($*$)} \end{align}

Comparing the coefficient of $x^n/n!$ on both sides in $(*)$ gives us

$$b_n = (-1)^n \sum_{k = 0}^n (-1)^{k}a_k \frac{n!}{(n - k)!k!}$$

or equivalently,

$$\color{blue}{(-1)^n b_n = \sum_{k = 0}^n \binom{n}{k}(-1)^{k}a_k.}$$

Here is a direct proof that uses only $\sum\limits_{s=0}^{m} (-1)^{s}\binom{m}{s} =1$ when $m=0$ and $=0$ when $m \ge 1$, This last is from the expansion $0 =(1-1)^m =\sum\limits_{s=0}^{m} (-1)^{s}\binom{m}{s}$.

$\begin{array}\\ \sum\limits_{s=0}^n \binom{n}{s} (-1)^s a_s &=\sum\limits_{s=0}^n \binom{n}{s} (-1)^s \sum\limits_{r=0}^s \binom{s}{r} b_r \\ &=\sum\limits_{r=0}^n\sum\limits_{s=r}^n \binom{n}{s} (-1)^s \binom{s}{r} b_r \\ &=\sum\limits_{r=0}^nb_r\sum\limits_{s=r}^n \binom{n}{s} (-1)^s \binom{s}{r} \\ &=\sum\limits_{r=0}^nb_r\sum\limits_{s=r}^n (-1)^s \binom{n}{s} \binom{s}{r} \\ &=\sum\limits_{r=0}^nb_r\sum\limits_{s=r}^n (-1)^s \dfrac{n!s!}{s!(n-s)!r!(s-r)!}\\ &=\sum\limits_{r=0}^nb_r\sum\limits_{s=r}^n (-1)^s \dfrac{n!}{(n-s)!r!(s-r)!}\\ &=\sum\limits_{r=0}^nb_r\dfrac{n!}{r!}\sum\limits_{s=r}^n (-1)^s \dfrac{1}{(n-s)!(s-r)!}\\ &=\sum\limits_{r=0}^nb_r\dfrac{n!}{r!(n-r)!}\sum\limits_{s=r}^n (-1)^s \dfrac{(n-r)!}{(n-s)!(s-r)!}\\ &=\sum\limits_{r=0}^nb_r\dfrac{n!}{r!(n-r)!}\sum\limits_{s=0}^{n-r} (-1)^{s+r} \dfrac{(n-r)!}{(n-(s+r))!(s+r-r)!}\\ &=\sum\limits_{r=0}^nb_r\binom{n}{r}\sum\limits_{s=0}^{n-r} (-1)^{s+r} \dfrac{(n-r)!}{(n-s-r)!s!}\\ &=\sum\limits_{r=0}^nb_r(-1)^r\binom{n}{r}\sum\limits_{s=0}^{n-r} (-1)^{s}\binom{n-r}{s}\\ &=(-1)^nb_n\\ \end{array}$

To rephrase the last statement in terms of the sum, $\sum\limits_{s=0}^{n-r} (-1)^{s}\binom{n-r}{s} =1$ when $n=r$ and $=0$ when $n > r$.