## Pascal Matrices and Binomial Inversion

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 $P_m$ is the $(m+1) \times (m+1)$ matrix containing Pascal’s triangle through row m.  For example,

$\displaystyle P_3 = \begin{bmatrix} 1 & 0 & 0 & 0 \\ 1 & 1 & 0 & 0 \\ 1 & 2 & 1 & 0 \\ 1 & 3 & 3 & 1 \end{bmatrix}.$

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,

$\displaystyle P_3^{-1} = \begin{bmatrix} 1 & 0 & 0 & 0 \\ -1 & 1 & 0 & 0 \\ 1 & -2 & 1 & 0 \\ -1 & 3 & -3 & 1 \end{bmatrix}.$

More precisely, $P_m$ is the $(m+1) \times (m+1)$ whose $(i,j)$ entry (starting with row 0 and column 0) is $\binom{i}{j}$, and $P_m^{-1}$ is the $(m+1) \times (m+1)$ matrix whose $(i,j)$ entry (again starting with row 0 and column 0) is $\binom{i}{j}(-1)^{i-j}$.

Binomial inversion is the following property: Given two sequences $\{a_n\}, \{b_n\}$, we have

$\displaystyle b_n = \sum_{k=0}^n \binom{n}{k} a_k \iff a_n = \sum_{k=0}^n \binom{n}{k} b_k (-1)^{n-k}$.

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 $\{a_n\}$ and turn its first $m+1$ entries into a column vector ${\bf a}_m$.  For example,

$\displaystyle {\bf a}_3 = \begin{bmatrix} a_0 \\ a_1 \\ a_2 \\ a_3 \end{bmatrix}$.

Now, multiply ${\bf a}_m$ by $P_m$.  This produces another vector that we can call ${\bf b}_m$.  In other words, $P_m {\bf a}_m = {\bf b}_m$.  For example,

$\displaystyle P_3 {\bf a}_3 = \begin{bmatrix} 1 & 0 & 0 & 0 \\ 1& 1 & 0 & 0 \\ 1 & 2 & 1 & 0 \\ 1 & 3 & 3 & 1 \end{bmatrix} \begin{bmatrix} a_0 \\ a_1 \\ a_2 \\ a_3 \end{bmatrix} = \begin{bmatrix} b_0 \\ b_1 \\ b_2 \\ b_3 \end{bmatrix} = {\bf b}_3$.

If we multiply both sides of this equation by $P_m^{-1}$, we get ${\bf a}_m = P^{-1}_m {\bf b}_m$.  For example,

$\displaystyle {\bf a}_3 = \begin{bmatrix} a_0 \\ a_1 \\ a_2 \\ a_3 \end{bmatrix} = \begin{bmatrix} 1 & 0 & 0 & 0 \\ -1& 1 & 0 & 0 \\ 1 & -2 & 1 & 0 \\ -1 & 3 & -3 & 1 \end{bmatrix} \begin{bmatrix} b_0 \\ b_1 \\ b_2 \\ b_3 \end{bmatrix} = P_3^{-1} {\bf b}_3$.

Let’s take a closer look at how ${\bf b}_m$ is calculated.  Entry n$b_n$, is the inner product of row n of $P_m$ and the ${\bf a}_m$ vector.  In other words,

$\displaystyle b_n = \sum_{k=0}^n \binom{n}{k} a_k$.

In addition, if we look at how entry n is calculated in ${\bf a}_m$ via the ${\bf a}_m = P^{-1}_m {\bf b}_m$ equation, we have that $a_n$ is the inner product of row n of $P_m^{-1}$ and the ${\bf b}_m$ vector.  In other words,

$\displaystyle a_n = \sum_{k=0}^n \binom{n}{k} (-1)^{n-k} b_k$.

Thus the relationship between the $\{a_n\}$ and $\{b_n\}$ sequences expressed via the Pascal matrix and its inverse is that

$\displaystyle b_n = \sum_{k=0}^n \binom{n}{k} a_k \iff a_n = \sum_{k=0}^n \binom{n}{k} (-1)^{n-k} b_k$.

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.