Inverse of the Pascal Matrix

Let $P_n$ be the $(n+1) \times (n+1)$ matrix that contains the numbers of Pascal's triangle in the upper triangle. For example in the case of $n=3$ $$ P_3 = \begin{pmatrix} 1 & 1 & 1 & 1 \\ 0 & 1 & 2 & 3 \\ 0 & 0 & 1 & 3 \\ 0 & 0 & 0 & 1 \\ \end{pmatrix} $$ or in general $$ (P_n)_{ij} = \binom{j}{i} \lfloor i \leq j \rceil ~~~\text{for}~~ i,j \in \{0,...,n \} $$ using the definition $$ \lfloor A \rceil := \begin{cases} 1 & \text{A is true} \\ 0 & \text{A is not true} \end{cases} $$ This matrix is invertible since $\det P_n = 1$. For smaller cases like $n=3$, I calulated the inverse of the matrix by hand and found $$ P_3^{-1} = \begin{pmatrix} 1 & -1 & 1 & -1 \\ 0 & 1 & -2 & 3 \\ 0 & 0 & 1 & -3 \\ 0 & 0 & 0 & 1 \\ \end{pmatrix} $$ $n=2,4$ led to similar results, so I'm guessing that the inverse should be $$ (P_n^{-1})_{ij} = (-1)^{j+i}(P_n)_{ij} = (-1)^{j+i} \binom{j}{i} \lfloor i \leq j \rceil $$ But I have not been able to prove or disprove this yet. So far I tried multiplying the two matirces which gives $$ \sum^j_{k=i} (-1)^{j+k} \binom{j}{k} \binom{k}{i} = \delta_{ij} $$ if one asumes that the result is the unit matrix. For $i=0$ and $j>0$ this gives $$ \delta_{0j} = 0 = \sum^j_{k=0} (-1)^{j+k} \binom{j}{k} \binom{k}{0} = \sum^j_{k=0} (-1)^{k} \binom{j}{k} $$ which is an identity I know to be true, so it reasures me a little bit that the above should also be true.

Solution 1:

In my opinion this is a bit simpler to prove, if we interpret the matrix $P_n$ as a linear transformation.

Consider the space $V_n$ of polynomials of degree $\le n$ (over, say $\Bbb{Q}$, but you are welcome to use reals or complex numbers, or any other field actually).

The mapping $T: f(x)\mapsto f(x+1)$ for all $f(x)\in V_n$ is obviously linear. My key point is to observe that $P_n$ is the matrix $M_{\mathcal B}(T)$ of $T$ with respect to the obvious basis $\mathcal{B}=\{1,x,x^2,\ldots,x^n\}$ of $V_n$. This is because for any $k, 0\le k\le n$ the binomial formula says that $$T(x^k)=\sum_{\ell=0}^k\binom k\ell x^\ell.$$ From this we can read the coordinates of $T(x^k)$ with respect to $\mathcal{B}$, and see that those coincide the $k$th column of $P_n$ (numbered from $0$ to $n$). That's exactly what the claim was.

It is obvious that the inverse of $T$ is given by the recipe $ T^{-1}:f(x)\mapsto f(x-1). $ A similar application of the binomial formula shows that the matrix $M_{\mathcal B}(T^{-1})$ then is exactly your prescribed inverse of $P_n$ containing binomial coefficients - this time with alternating signs.

But, by basic linear algebra $$ M_{\mathcal B}(T^{-1})=M_{\mathcal B}(T)^{-1}. $$

Solution 2:

By the suggestion of Sungjin Kim one can use \begin{equation} \binom{j}{k}\binom{k}{i} = \binom{j}{i}\binom{j-i}{k-i} \end{equation} which is useful since it leads to the sum only going over one of the binomial coefficients. It leads to \begin{align} \sum^j_{k=i} (-1)^{j+k} \binom{j}{k} \binom{k}{i} &= \sum^j_{k=i} (-1)^{j+k} \binom{j}{i}\binom{j-i}{k-i} \\ &= (-1)^j \binom{j}{i} \sum^j_{k=i} (-1)^{k} \binom{j-i}{k-i} \\ &= (-1)^{j} \binom{j}{i} \sum^{j-i}_{k=0} (-1)^{k+i} \binom{j-i}{k} \\ &= (-1)^{j+i} \binom{j}{i} (1 - 1)^{j-i} = \delta_{ij} \end{align} The identity used is easily proven by $$ \binom{j}{k}\binom{k}{i} = \frac{j!}{k!(j-k)!} \frac{k!}{i!(k-i)!} = \frac{j!}{i!(j-i)!} \frac{(j-i)!}{(j-k)!(k-i)!} = \binom{j}{i}\binom{j-i}{k-i} $$ Another way of showing the identity involving $\delta_{ij}$ is to start with $x^j$ and using the binomial thoerem twice $$ x^j = (x+0)^j = ((x+1) - 1 )^j = ~...~ = \sum^j_{i=0} \sum^j_{k=i} (-1)^{j+k} \binom{j}{k} \binom{k}{i} x^i $$ comparing coefficients of the two sides of the equation, then also leads to the desired result. You can find the whole calcultion here, along whith other examples of when adding 0 really counts.