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\;?$$


closed as off-topic by Newb, Daniel W. Farlow, anomaly, Claude Leibovici, Mario Carneiro Feb 19 '15 at 7:31

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "This question is missing context or other details: Please improve the question by providing additional context, which ideally includes your thoughts on the problem and any attempts you have made to solve it. This information helps others identify where you have difficulties and helps them write answers appropriate to your experience level." – Newb, Daniel W. Farlow, anomaly, Claude Leibovici, Mario Carneiro
If this question can be reworded to fit the rules in the help center, please edit the question.

  • $\begingroup$ I corrected your $A$ and $B$ to the $a$ and $b$ of the problem statement. I had to guess what you meant by B0(0)+B1(0)+; please leave a comment if I guessed wrong. It would also be a good idea to explain what you’re trying to do with that last line. $\endgroup$ – Brian M. Scott Feb 19 '15 at 4:44
  • $\begingroup$ I know that somehow bo, b1, b2,.... bn-1 terms should be cancelled out and the only term left is bn. How can I do this? $\endgroup$ – abcde Feb 19 '15 at 5:13
  • $\begingroup$ No problem Dr Scott, whenever you have time. No urgency. I will remove the earlier comment as it is irrelevant for the question Thanks $\endgroup$ – Satish Ramanathan Feb 19 '15 at 5:47

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


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


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)$?

  • $\begingroup$ @abcde: You’re welcome! $\endgroup$ – Brian M. Scott Feb 19 '15 at 6:53

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