2

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.

sc_
  • 365
  • Hint: Try to find $a_n$ for small $n$, for example $n=1, 2, 3$. See the pattern that is occurring – Jakobian Oct 07 '18 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_ Oct 07 '18 at 10:15
  • 3
    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)$ – Jakobian Oct 07 '18 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}$. – Alexander Burstein Dec 23 '23 at 19:43

2 Answers2

2

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

Markus Scheuer
  • 108,315
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. $$

Alexander Burstein
  • 4,145