# Find $a_n$ in terms of $b_n$ given $b_n = \sum_{k=0}^{n} {n \choose k} a_k$

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.

• Hint: Try to find $a_n$ for small $n$, for example $n=1, 2, 3$. See the pattern that is occurring Commented Oct 7, 2018 at 10:03
• @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?
– sc_
Commented Oct 7, 2018 at 10:15
• 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)$ Commented Oct 7, 2018 at 10:15
• @Jakobian You can also use ordinary generating functions, then $xB=(xA)\circ\dfrac{x}{1-x}$, so $xA=(xB)\circ\dfrac{x}{1+x}$. Commented Dec 23, 2023 at 19:43

## 2 Answers

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*}

The sequence $$(b_n)$$ is called the binomial transform of the sequence $$(a_n)$$, so $$(a_n)$$ is the inverse binomial transform of $$(b_n)$$. We can take ordinary generating functions of both sides, say, $$A(x)=\sum_{n=0}^{\infty}a_nx^n$$, $$B(x)=\sum_{n=0}^{\infty}b_nx^n$$, then $$\begin{split} B(x)&=\sum_{n=0}^{\infty}\sum_{k=0}^{n}\binom{n}{k}a_kx^n=\sum_{k=0}^{\infty}\sum_{n=k}^{\infty}\binom{n}{k}a_kx^n\\ &=\sum_{k=0}^{\infty}a_k\left(\sum_{n=k}^{\infty}\binom{n}{k}x^n\right)=\sum_{k=0}^{\infty}a_k\frac{x^k}{(1-x)^{k+1}}\\ &=\frac{1}{1-x}\sum_{k=0}^{\infty}a_k\left(\frac{x}{1-x}\right)^k=\frac{1}{1-x}A\left(\frac{x}{1-x}\right), \end{split}$$ or equivalently, $$xB(x)=\frac{x}{1-x}A\left(\frac{x}{1-x}\right)=(xA(x))\circ\left(\frac{x}{1-x}\right)$$ Note that the inverse function of $$\frac{x}{1-x}$$ is $$\frac{x}{1+x}$$, so $$xA(x)=(xB(x))\circ\left(\frac{x}{1+x}\right)=\frac{x}{1+x}B\left(\frac{x}{1+x}\right),$$ i.e. $$\begin{split} A(x)&=\frac{1}{1+x}B\left(\frac{x}{1+x}\right)=\left(\frac{1}{1-x}B\left(-\frac{x}{1-x}\right)\right)\circ(-x)\\ &=\left(\frac{1}{1-x}\sum_{k=0}^{\infty}(-1)^kb_k\left(\frac{x}{1-x}\right)^k\right)\circ(-x)\\ &=\left(\sum_{n=0}^{\infty}\sum_{k=0}^{n}\binom{n}{k}(-1)^kb_kx^n\right)\circ(-x)\\ &=\sum_{n=0}^{\infty}\sum_{k=0}^{n}\binom{n}{k}(-1)^kb_k(-x)^n\\ &=\sum_{n=0}^{\infty}\sum_{k=0}^{n}\binom{n}{k}(-1)^kb_k(-1)^nx^n\\ &=\sum_{n=0}^{\infty}\sum_{k=0}^{n}\binom{n}{k}(-1)^{n-k}b_kx^n, \end{split}$$ so $$a_n=\sum_{k=0}^{n}\binom{n}{k}(-1)^{n-k}b_k.$$