TAOCP 1.2.6 Exercise 54

Exercise 54. [M21] Consider Pascal's triangle as a matrix. What is the inverse of that matrix?

Verified: no
Solve time: -

Solution

Let $P$ denote the infinite lower-triangular matrix whose $(i,j)$ entry is

$$ P_{i,j} = \binom{i}{j}, \qquad i,j \ge 0, $$

with the convention that $\binom{i}{j} = 0$ when $j > i$. This is the matrix form of Pascal's triangle. Our goal is to find $P^{-1}$, the inverse of $P$.

Observe that $P$ is lower-triangular with all diagonal entries $P_{i,i} = \binom{i}{i} = 1$. Hence $P$ is invertible, and $P^{-1}$ is also lower-triangular with diagonal entries equal to $1$. To determine the off-diagonal entries, we solve

$$ \sum_{k=0}^{i} P_{i,k} (P^{-1}){k,j} = \delta{i,j}, \qquad i,j \ge 0, \tag{1} $$

where $\delta_{i,j}$ is the Kronecker delta.

We make the ansatz

$$ (P^{-1})_{i,j} = (-1)^{i-j} \binom{i}{j}, \qquad i \ge j \ge 0. \tag{2} $$

To verify (2), consider

$$ \sum_{k=j}^{i} \binom{i}{k} (-1)^{k-j} \binom{k}{j} = \sum_{k=j}^{i} \binom{i}{k} \binom{k}{j} (-1)^{k-j}. \tag{3} $$

Apply the identity

$$ \binom{i}{k}\binom{k}{j} = \binom{i}{j}\binom{i-j}{k-j}, \qquad j \le k \le i, \tag{4} $$

which is valid for integers $i \ge j \ge 0$. Substituting (4) into (3) gives

$$ \sum_{k=j}^{i} \binom{i}{j} \binom{i-j}{k-j} (-1)^{k-j} = \binom{i}{j} \sum_{k'=0}^{i-j} \binom{i-j}{k'} (-1)^{k'}, \tag{5} $$

where $k' = k-j$. The inner sum is

$$ \sum_{k'=0}^{i-j} \binom{i-j}{k'} (-1)^{k'} = (1-1)^{i-j} = \begin{cases} 1, & i=j,\ 0, & i>j. \end{cases} \tag{6} $$

Hence

$$ \sum_{k=0}^{i} \binom{i}{k} (P^{-1}){k,j} = \delta{i,j}, \tag{7} $$

confirming that (2) indeed gives the inverse of $P$.

Therefore, the inverse of Pascal's triangle matrix is

$$ (P^{-1})_{i,j} = (-1)^{i-j} \binom{i}{j}, \qquad i \ge j \ge 0, $$

and $(P^{-1})_{i,j} = 0$ when $j > i$.

This completes the proof.

∎