6
$\begingroup$

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?

$\endgroup$
5
$\begingroup$

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

$\endgroup$
4
$\begingroup$

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

$\endgroup$

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.