Given sequences $a_n$ and $b_n$ satifying $$b_n = \sum_{k=0}^{n} {n \choose k} a_k$$

I am required to find $a_n$ in terms of $b_n$

My attempt:

The generating fuction for $b_n$ will be \begin{align} B(x) &= \sum_{n=0}^{\infty} \left( \sum_{k=0}^{n} {n \choose k} a_k \right)\\ &= \sum_{n=0}^{\infty} \left( \sum_{k=0}^{n} {n \choose n-k} a_k \right) \end{align} This looks like the product of two generating functions $A(x)$ ( for $a_n$ ) and $C(x)$. Hence the given sequence $b_n$ is an convolution of two $a_n$ and some $c_n$.

If now I can find $c_n$, and a closed form for $C(x)$ (which I believe exists), the sequence $a_n$ can be found since $$A(x) = \frac{B(x)}{C(x)}$$

My question:

I am unable to find the sequence $c_n$. I tried using $c_k = {n \choose k}$ but I am quite sure that it is incorrect.

  • $\begingroup$ Hint: Try to find $a_n$ for small $n$, for example $n=1, 2, 3$. See the pattern that is occurring $\endgroup$ – Jakobian Oct 7 '18 at 10:03
  • $\begingroup$ @Jakobian Thanks for the hint. I've obtained that $a_n = \sum_{k=0}^{n} (-1)^k {n \choose k} b_{n-k}$. Proving by induction will make sure that the answer is correct. Can the question be solved by generating functions? $\endgroup$ – sc_ Oct 7 '18 at 10:15
  • 2
    $\begingroup$ Yes, another way would be to consider exponential generating functions i. e. $B(x) = \sum \frac{b_nx^n}{n!}$ and $A(x) = \sum \frac{a_nx^n}{n!}$, then $B(x) = e^xA(x)$ $\endgroup$ – Jakobian Oct 7 '18 at 10:15

Here we are looking for so-called binomial inverse pairs. To show the relationship we multiply exponential generating functions (egfs). Let $A(x)=\sum_{n\ge0}a_{n}\frac{x^n}{n!}$ and $B(x)=\sum_{n\ge0}b_{n}\frac{x^n}{n!}$ egfs with $B(x)=A(x)e^x$. Comparing coefficients gives the following

Binomial inverse pair \begin{align*} B(x)&=A(x)e^x&A(x)&=B(x)e^{-x}\\ b_n&=\sum_{k=0}^{n}\binom{n}{k}a_k&a_n&=\sum_{k=0}^{n}\binom{n}{k}(-1)^{n-k}b_k \end{align*}


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.