Recovering the coefficients $b_r$ of the binomial sum $\sum_{r=0}^n\binom{n}rb_r$

70 Views Asked by At

Suppose that the sequences of real numbers $a_0,a_1,a_2,a_3,\ldots$ and $b_0,b_1,b_2,b_3,\ldots$ satisfy the relation $$a_n=\sum_{r=0}^n\binom{n}rb_r\;.$$ Then prove that $$(-1)^nb_n=\sum_{s=0}^n\binom{n}s(-1)^sa_s\;.$$

After substituting the formula for $a_s$ into $\sigma\binom{n}s(-1)^sa_s$, how can I get $$b_0(0)+b_1(0)+b_2(0)+\ldots+(-1)^nb_n=(-1)^nb_n\;?$$

1

There are 1 best solutions below

1
On BEST ANSWER

Extended HINT: You seem to have had in mind making the substitution

$$\begin{align*} \sum_{s=0}^n\binom{n}s(-1)^sa_s&=\sum_{s=0}^n\binom{n}s(-1)^s\sum_{r=0}^s\binom{s}rb_r\\\\ &=\sum_{s=0}^n\sum_{r=0}^s(-1)^s\binom{n}s\binom{s}rb_r\;; \end{align*}$$

there’s a much easier proof using exponential generating functions, but this approach will also work.

For each $r=0,\ldots,n$ you want to gather together all of the terms containing $b_r$, so you need to reverse the order of summation. The summation $\sum_{s=0}^n\sum_{r=0}^s\ldots$ runs over all pairs $\langle s,r\rangle$ such that $0\le r\le s\le n$. The possible values of $r$ are $0,\ldots,n$, and for each choice of $r$ the possible values of $s$ are $r,r+1,\ldots,n$, so we sum the same values with $\sum_{r=0}^n\sum_{s=r}^n\ldots\;$. This is a very useful standard technique, very similar to reversing the order of integration of an iterated integral; if you don’t already know it, you should learn it. We now have

$$\begin{align*} \sum_{s=0}^n\binom{n}s(-1)^sa_s&=\sum_{s=0}^n\binom{n}s(-1)^s\sum_{r=0}^s\binom{s}rb_r\\\\ &=\sum_{s=0}^n\sum_{r=0}^s(-1)^s\binom{n}s\binom{s}rb_r\\\\ &=\sum_{r=0}^n\sum_{s=r}^n(-1)^s\binom{n}s\binom{s}rb_r\\\\ &=\sum_{r=0}^nb_r\sum_{s=r}^n(-1)^s\binom{n}s\binom{s}r\;, \end{align*}$$

and we want to show that this is equal to $(-1)^nb_n$. In other words, we want to show that

$$\sum_{s=r}^n(-1)^s\binom{n}s\binom{s}r=0\tag{1}$$

if $0\le r\le n-1$, and

$$\sum_{s=r}^n(-1)^s\binom{n}s\binom{s}r=(-1)^n\tag{2}$$

if $r=n$. $(2)$ is trivial to verify. $(1)$ is a bit tricky if you’re not accustomed to this kind of manipulation.

  • Figure out how to write $\binom{n}s\binom{s}r$ as the product of $\dbinom{n}r$ and another binomial coefficient. $\binom{n}r$ does not depend on $s$, so you can pull it out of the summation $(2)$.

  • Apply the binomial theorem to the remaining summation.


If by any chance you’re familiar with exponential generating functions, consider the functions

$$\begin{align*} A(x)&=\sum_{n\ge 0}a_n\frac{x^n}{n!}\;,\\ B(x)&=\sum_{n\ge 0}b_n\frac{x^n}{n!}\;,\text{ and}\\ e^x&=\sum_{n\ge 0}\frac{x^n}{n!}\;. \end{align*}$$

In particular, what is $e^xB(x)$?