In this post we’ll look at the relationship between a Pascal matrix, its inverse, and binomial inversion. It turns out that these are the same concepts viewed from two different angles.
The Pascal matrix is the matrix containing Pascal’s triangle through row m. For example,
The inverse of a Pascal matrix turns out to be a slight variation on that Pascal matrix – one in which some of the entries are negative. For example,
More precisely, is the whose entry (starting with row 0 and column 0) is , and is the matrix whose entry (again starting with row 0 and column 0) is .
Binomial inversion is the following property: Given two sequences , we have
Binomial inversion is useful for proving sum identities involving the binomial coefficients: If you can prove one such identity, you get a second identity immediately from binomial inversion.
Let’s look at the connection between Pascal matrices and binomial inversion now. Suppose you take a sequence and turn its first entries into a column vector . For example,
Now, multiply by . This produces another vector that we can call . In other words, . For example,
If we multiply both sides of this equation by , we get . For example,
Let’s take a closer look at how is calculated. Entry n, , is the inner product of row n of and the vector. In other words,
In addition, if we look at how entry n is calculated in via the equation, we have that is the inner product of row n of and the vector. In other words,
Thus the relationship between the and sequences expressed via the Pascal matrix and its inverse is that
This is exactly binomial inversion.
Thus binomial inversion is just expressing what the inverse of a Pascal matrix is, and knowledge of the inverse of a Pascal matrix gives you the binomial inversion formula.