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

Question

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.

Answer 1

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

Answer 2

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