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 nb_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.

Advertisements
This entry was posted in binomial coefficients, matrices. Bookmark the permalink.

2 Responses to Pascal Matrices and Binomial Inversion

  1. pwgdrk says:

    Nice “matrix view” of the inversion formula. Seems to work also with inversion formula for Stirling numbers.

    • mzspivey says:

      Yes, it does work with the Stirling numbers… and the Lah numbers, and any other set(s) of numbers that obey an inversion formula like binomial inversion!

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s