TAOCP 1.2.3 Exercise 42

Section 1.2.3: Sums and Products

Exercise 42. [M18] What is the sum of all $n^2$ elements in the inverse of the combinatorial matrix?

Verified: yes
Solve time: 35s

Solution

By Exercise 39, the inverse of the combinatorial matrix has entries

$$ b_{ij}=\frac{-y+\delta_{ij}(x+ny)}{x(x+ny)}. $$

We must compute

$$ \sum_{1\le i\le n}\sum_{1\le j\le n} b_{ij}. $$

Using Eq. (8),

$$ \sum_{i=1}^n\sum_{j=1}^n b_{ij} = \frac1{x(x+ny)} \left( \sum_{i=1}^n\sum_{j=1}^n (-y) + \sum_{i=1}^n\sum_{j=1}^n \delta_{ij}(x+ny) \right). $$

The first double sum contains exactly $n^2$ terms, each equal to $-y$; hence

$$ \sum_{i=1}^n\sum_{j=1}^n (-y)=-n^2y. $$

For the second double sum, $\delta_{ij}=1$ exactly when $i=j$, and there are exactly $n$ such pairs $(i,j)$ with $1\le i,j\le n$. Therefore

$$ \sum_{i=1}^n\sum_{j=1}^n \delta_{ij}(x+ny) = n(x+ny). $$

Substituting these values gives

$$ \sum_{i=1}^n\sum_{j=1}^n b_{ij} = \frac{-n^2y+n(x+ny)}{x(x+ny)}. $$

The numerator simplifies to

$$ -n^2y+n(x+ny)=nx. $$

Hence

$$ \sum_{i=1}^n\sum_{j=1}^n b_{ij} = \frac{nx}{x(x+ny)} = \frac{n}{x+ny}. $$

Therefore the sum of all $n^2$ elements in the inverse matrix is

$$ \boxed{\frac{n}{x+ny}}. $$