It is known that if $f_n = \sum\limits_{i=0}^{n} g_i \binom{n}{i}$ for all $0 \le n \le m$, then $g_n = \sum_{i=0}^{n} (-1)^{i+n} f_i \binom{n}{i}$ for $0 \le n \le m$. This sort of inversion is called binomial inversion, for obvious reasons.
Many nice elegant proofs exist (my favorite uses exponential generating functions of $f_n$ and $g_n$), and also many applications (such as proving that if polynomial $f$ of degree $n$ assumes integers values on $0,1,\cdots,n$, then $f(i) \in \mathbb{Z}$ for all integers $i$).
What I'm interested is the following:
- A nice inclusion-exclusion proof – similar to interpreting Möbius inversion as inclusion-exclusion.
- If $f_0 = g_0 = 0$ and $i | f_i$ for $i>1$, we get, by the Binomial Inversion, that $i | g_i$ (reason: $i\binom{n}{i} = n\binom{n-1}{i-1}$). Is there a nice combinatorial interpretation of this phenomena? Nice applications?
- Are there any more famous/cool inversions (I know of Möbius inversion, binomial inversion, and the discrete derivative inversion $a_i \to a_{i+1}-a_{i})$?
Best Answer
These kinds of inverse relations are equivalent to orthogonal relations between sets of numbers.
Suppose you have two triangular sets of numbers $a_{n,k}$ and $b_{n,k}$, each defined for $k = 0, 1, \ldots, n$, such that $$\sum_{k=m}^n b_{n,k} a_{k,m} = \delta_{nm}.$$ Then $a_{n,k}$ and $b_{n,k}$ are orthogonal, and they have the inverse property you are asking for in (3); i.e., if $f_n = \sum_{k=0}^n a_{n,k} g_k$ then $g_n = \sum_{k=0}^n b_{n,k} f_k$, and vice versa.
Proof: $$\sum_{k=0}^n b_{n,k} f_k = \sum_{k=0}^n b_{n,k} \sum_{m=0}^k a_{k,m} g_m = \sum_{m=0}^n \left(\sum_{k=m}^n b_{n,k} a_{k,m}\right) g_m = g_n.$$
Thus binomial inversion follows from the "beautiful identity" $$\sum_{k=m}^n (-1)^{k+m} \binom{n}{k} \binom{k}{m} = \delta_{nm}.$$
Since the orthogonal relation and the inverse relation are equivalent, perhaps the proof of this identity given by Aryabhata or the proof by Yuval Filmus can be considered a combinatorial proof of the inverse relation you describe for binomial coefficients.
Other examples
The Lah numbers $L(n,k)$ satisfy $$\sum_{k=m}^n (-1)^{k+m} L(n,k) L(k,m) = \delta_{nm},$$ and so, like the binomial coefficients, are (up to sign) self-orthogonal and have the inverse relation $$f_n = \sum_{k=0}^n L(n,k) g_k \Leftrightarrow g_n = \sum_{k=0}^n (-1)^{k+n} L(n,k) f_k.$$
The two kinds of Stirling numbers, $\left[ n \atop k \right]$ and $\left\{ n \atop k \right\}$, are orthogonal, satisfying $$\sum_{k=m}^n (-1)^{k+m} \left[ n \atop k \right] \left\{ k \atop m \right\} = \delta_{nm}$$ and $$\sum_{k=m}^n (-1)^{k+m} \left\{ n \atop k \right\} \left[ k \atop m \right] = \delta_{nm}.$$ Thus they satisfy the inverse relation $$f_n = \sum_{k=0}^n \left[ n \atop k \right] g_k \Leftrightarrow g_n = \sum_{k=0}^n (-1)^{k+n} \left\{ n \atop k \right\} f_k.$$
John Riordan wrote a paper "Inverse Relations and Combinatorial Identities" (American Mathematical Monthly 71 (5), May 1964, pp. 485--498) and devoted two of the six chapters of his text Combinatorial Identities to these kinds of inverse relations. For example, he shows how inverse relations can be derived from Chebyshev polynomials (since they are orthogonal) and Legendre polynomials (since they are also orthogonal). See the article or the book for many more examples.
Additional comments and consequences
The proof using the orthogonal relation can also be applied with respect to the upper index to obtain inverse relations based on the upper index rather than the lower. Thus, for example, we also have (provided, of course, that the sums converge) $$f_n = \sum_{k=n}^\infty \binom{k}{n} g_k \Leftrightarrow g_n = \sum_{k=n}^\infty (-1)^{k+n} \binom{k}{n} f_k,$$ as well as the same kind of thing for the Lah numbers, Stirling numbers, and the other examples.
In addition, these orthogonal relations mean that matrices consisting of orthogonal numbers are inverses. Thus, for example, if $A$ and $B$ are $n \times n$ matrices such that $A_{ij} = \binom{i}{j}$ and $B_{ij} = (-1)^{i+j} \binom{i}{j}$ then the orthogonal relationship implies that $AB = I$. This, of course, means that $BA = I$ as well, and so every orthogonal relationship goes both ways; i.e., $$\sum_{k=m}^n b_{n,k} a_{k,m} = \delta_{nm} \Leftrightarrow \sum_{k=m}^n a_{n,k} b_{k,m} = \delta_{nm}.$$ For more on inverse matrices consisting of combinatorial numbers, see my answer to the question "Stirling numbers and inverse matrices."