Prove inversion formula involving binomial coefficients

Question

Let's say that we have such an equation:

$$f_k = \sum_{i=0}^{k}{k \choose i}g_i$$

Prove that in that case we can express $g_k$ like this:

$$g_k = \sum_{i=0}^{k}(-1)^{k-i}{k \choose i}f_i$$

In order to prove that, count how many $f$'s and $g$'s there are on the right and on the left.

Answer 1

This is basically just an exercise in manipulating binomial coefficients and summations.

$$\begin{align*} \sum_{i=0}^k(-1)^{k-i}\binom{k}if_i&=\sum_{i=0}^k(-1)^{k-i}\binom{k}i\sum_{j=0}^i\binom{i}jg_j\\ &\overset{(1)}=\sum_{j=0}^k\sum_{i=j}^k(-1)^{k-i}\binom{k}i\binom{i}jg_j\\ &\overset{(2)}=\sum_{j=0}^k\sum_{i=j}^k(-1)^{k-i}\binom{k}j\binom{k-j}{k-i}g_j\\ &=\sum_{j=0}^k\binom{k}jg_j\sum_{i=0}^{k-j}(-1)^i\binom{k-j}i\,. \end{align*}$$

Step $(1)$ is just reversing the order of summation, and $(2)$ is applying a standard binomial coefficient identity: $\binom{k}i\binom{i}j$ and $\binom{k}j\binom{k-j}{k-i}$ are both the number of ways to split $k$ things into three sets of cardinalities $j$, $i-j$, and $k-i$.

Now by the binomial theorem

$$\sum_{i=0}^{k-j}(-1)^i\binom{k-j}i=\begin{cases} 1,&\text{if }k=j\\ 0,&\text{otherwise,} \end{cases}$$

since $\binom00=1$, so

$$\sum_{i=0}^k(-1)^{k-i}\binom{k}if_i=\binom{k}kg_k=g_k\,,$$

as desired.

Answer 2

The computations given by Brian M. Scott are the rigorous way of doing things.

Let me bring a supplementary light by a linear algebra explanation.

Consider the matrices associated resp. with the first and second (infinite) set of equations As infinite matrices aren't easy to deal with, let us consider that we are in a process where these infinite matrices are replaced by increasing size $n \times n$ submatrices extracted from them (like russian dolls). For example, when $n=5$ we would have:

$$P_5=\left(\begin{array}{rrrrr}1&0&0&0&0\\1&1&0&0&0\\1&2&1&0&0\\1&3&3&1&0\\1&4&6&4&1\end{array}\right) \ \ \text{with} \ \ F = P_5 G$$

where $F$, resp. $G$ is the column vector of $f_k$s, resp. $g_k$s.

$$Q_5=\left(\begin{array}{rrrrr}1&0&0&0&0\\-1&1&0&0&0\\1&-2&1&0&0\\-1&3&-3&1&0\\1&-4&6&-4&1\end{array}\right) \ \ \text{with} \ \ G = Q_5 F$$

The first one is the so-called "Pascal matrix" ; see here where you will see mentionned its inverse... which is $Q_5$. What we have done for index $n=5$ is in fact valid for any $n$.

Answer 3

Consider the transformation $T_{\lambda}$ on sequences defined by

$$T_{\lambda} \colon (a_n)_n \mapsto (b_n)_n$$

with $$b_n = \sum_{i\ge 0} \binom{n}{i} \lambda^{n-i} a_i$$

Notice that $T_{\lambda}$ maps the sequence $(\alpha^n)$ to the sequence $((\alpha + \lambda)^n)$. We conclude that

$$T_{\lambda} \circ T_{\mu} = T_{\lambda + \mu}$$

Note also that $T_0 = \operatorname{Id}$, so $T_{-\lambda} = T_{\lambda}^{-1}$.

Let's now examine the behavior of generating functions and exponential generating functions under the transformation $T_{\lambda}$.

The sequence $(\alpha^n)$ has the generating function $$f_{\alpha}(x) = \sum_{n\ge 0} \alpha^n x^n= \frac{1}{1-\alpha x}$$

Now notice that

$$\frac{1}{1- \lambda x} f_{\alpha}\left(\frac{x}{1- \lambda x}\right) = \frac{1}{1-(\alpha + \lambda) x}= f_{\alpha + \lambda}(x)$$

Therefore, at the level of generating functions, the transformation $T_{\lambda}$ has the form $$f(x) \mapsto \frac{1}{1-\lambda x} f\left( \frac{x}{1-\lambda x}\right)$$

Now let's consider exponential generating functions. The sequence $(\alpha^n)$ has $$F(x) = \sum_{n\ge 0} \frac{ \alpha^n}{n!} x^n = \exp (\alpha x)$$ Therefore, at the level of exponential geneerating functions the maps $T_{\lambda}$ acts as

$$F(x) \mapsto \exp(\lambda x) \cdot F(x)$$