Exercises from Section 1.2.3

1. [10] The text says that

a_{1} + a_{2} + \dots + a_{0} = 0

. What then, is

a_{2} + \dots + a_{0}

The identities

\sum_{1 \leq k \leq 0} a_{k} = 0 = a_{1} + \sum_{2 \leq k \leq 0} a_{k}

imply that

\sum_{2 \leq k \leq 0} a_{k} = a_{2} + \dots + a_{0} = - a_{1} .

2. [01] What does the notation

\sum_{1 \leq j \leq n} a_{j}

mean, if

n = 3.14

The notation $\sum_{1 \leq j \leq n} a_{j}$ if $n = 3.14$ represents the sum of all $a_{j}$ such that $1 \leq j \leq n = 3.14$ , or equivalently, $j \in {1, 2, 3}$ . That is,

\sum_{1 \leq j \leq n} a_{j} = a_{1} + a_{2} + a_{3} .

For the ﬁrst notation,

\sum_{0 \leq n \leq 5} \frac{1}{2 n + 1} = \frac{1}{1} + \frac{1}{3} + \frac{1}{5} + \frac{1}{7} + \frac{1}{9} + \frac{1}{11},

while for the second notation,

\sum_{0 \leq n^{2} \leq 5} \frac{1}{2 n^{2} + 1} = \frac{1}{9} + \frac{1}{3} + \frac{1}{1} + \frac{1}{3} + \frac{1}{9} .

The two results are diﬀerent, in spite of rule (b), as $P (n) = n^{2}$ is not a permutation, since $P$ is neither one-to-one ( $- 1^{2} = 1^{2}$ serves as a counterexample) nor onto (there is no integer $n$ such that $n^{2} = 3$ ).

4. [10] Without using the

\sum

-notation, write out the equivalent of each side of Eq. (10) as a sum of sums for the case

n = 3

For $n = 3$ , the equivalent of the left side of Eq. (10) is

\sum_{i = 1}^{3} \sum_{j = 1}^{i} a_{i j} = (a_{11}) + (a_{21} + a_{22}) + (a_{31} + a_{32} + a_{33})

and of the right side is

\sum_{j = 1}^{3} \sum_{i = j}^{3} = (a_{11} + a_{21} + a_{31}) + (a_{22} + a_{32}) + (a_{33}) .

▸

5. [HM20] Prove that rule (a) is valid for arbitrary inﬁnite series, provided the series converge.

Proposition. The distributive law, for the products of sums $(\sum_{R (i)} a_{i}) (\sum_{S (j)} b_{j}) = \sum_{R (i)} (\sum_{S (j)} a_{i} b_{j})$ holds for arbitrary inﬁnite series, provided the sums converge.

Proof. Assume that we have two inﬁnite series $a_{i}$ , $b_{j}$ whose sums converge; that is, that

\sum_{R (i)} a_{i} = (\lim_{n \to \infty} \sum_{\begin{array}{c} R (i) \\ 0 \leq i < n \end{array}} a_{i}) + (\lim_{n \to \infty} \sum_{\begin{array}{c} R (i) \\ - n \leq i < 0 \end{array}} a_{i}) = α

and

\sum_{S (j)} b_{j} = (\lim_{n \to \infty} \sum_{\begin{array}{c} S (j) \\ 0 \leq j < n \end{array}} b_{j}) + (\lim_{n \to \infty} \sum_{\begin{array}{c} S (j) \\ - n \leq j < 0 \end{array}} b_{j}) = β

for arbitary limits $α$ , $β$ . We must show that

(\sum_{R (i)} a_{i}) (\sum_{S (j)} b_{j}) = \sum_{R (i)} (\sum_{S (j)} a_{i} b_{j}) .

But

\begin{array}{l} (\sum_{R (i)} a_{i}) (\sum_{S (j)} b_{j}) & = \lim_{n \to \infty} ((\sum_{\begin{array}{c} R (i) \\ 0 \leq i < n \end{array}} a_{i} + \sum_{\begin{array}{c} R (i) \\ - n \leq i < 0 \end{array}} a_{i}) (\sum_{\begin{array}{c} S (j) \\ 0 \leq j < n \end{array}} b_{j} + \sum_{\begin{array}{c} S (j) \\ - n \leq j < 0 \end{array}} b_{j})) \\ = \lim_{n \to \infty} ((\sum_{\begin{array}{c} R (i) \\ 0 \leq i < n \end{array}} a_{i}) (\sum_{\begin{array}{c} S (j) \\ 0 \leq j < n \end{array}} b_{j} + \sum_{\begin{array}{c} S (j) \\ - n \leq j < 0 \end{array}} b_{j}) + (\sum_{\begin{array}{c} R (i) \\ - n \leq i < 0 \end{array}} a_{i}) (\sum_{\begin{array}{c} S (j) \\ 0 \leq j < n \end{array}} b_{j} + \sum_{\begin{array}{c} S (j) \\ - n \leq j < 0 \end{array}} b_{j})) \\ = \lim_{n \to \infty} (\sum_{\begin{array}{c} R (i) \\ 0 \leq i < n \end{array}} a_{i} (\sum_{\begin{array}{c} S (j) \\ 0 \leq j < n \end{array}} b_{j} + \sum_{\begin{array}{c} S (j) \\ - n \leq j < 0 \end{array}} b_{j}) + \sum_{\begin{array}{c} R (i) \\ - n \leq i < 0 \end{array}} a_{i} (\sum_{\begin{array}{c} S (j) \\ 0 \leq j < n \end{array}} b_{j} + \sum_{\begin{array}{c} S (j) \\ - n \leq j < 0 \end{array}} b_{j})) \\ = \lim_{n \to \infty} (\sum_{\begin{array}{c} R (i) \\ 0 \leq i < n \end{array}} (\sum_{\begin{array}{c} S (j) \\ 0 \leq j < n \end{array}} a_{i} b_{j} + \sum_{\begin{array}{c} S (j) \\ - n \leq j < 0 \end{array}} a_{i} b_{j}) + \sum_{\begin{array}{c} R (i) \\ - n \leq i < 0 \end{array}} (\sum_{\begin{array}{c} S (j) \\ 0 \leq j < n \end{array}} a_{i} b_{j} + \sum_{\begin{array}{c} S (j) \\ - n \leq j < 0 \end{array}} a_{i} b_{j})) \\ = \lim_{n \to \infty} (\sum_{\begin{array}{c} R (i) \\ 0 \leq i < n \end{array}} (\sum_{S (j)} a_{i} b_{j}) + \sum_{\begin{array}{c} R (i) \\ - n \leq i < 0 \end{array}} (\sum_{S (j)} a_{i} b_{j})) \\ = \sum_{R (i)} (\sum_{S (j)} a_{i} b_{j}) \end{array}

as we needed to show. □

6. [HM20] Prove that rule (d) is valid for an arbitrary inﬁnite series, provided that any three of the four sums exist.

Proposition. Manipulating the domain, $\sum_{R (j)} a_{j} + \sum_{S (j)} a_{j} = \sum_{R (j) \lor S (j)} a_{j} + \sum_{R (j) \land S (j)} a_{j}$ is valid for arbitrary inﬁnite series, provided that any three of the four sums exist.

Proof. Assume that $R$ and $S$ are arbitrary inﬁnite series. We must show that if any three of the sums $\sum_{R (j)} a_{j}$ , $\sum_{S (j)} a_{j}$ , $\sum_{R (j) \lor S (j)} a_{j}$ , $\sum_{R (j) \land S (j)} a_{j}$ exist, then we may manipulate the domain so that $\sum_{R (j)} a_{j} + \sum_{S (j)} a_{j} = \sum_{R (j) \lor S (j)} a_{j} + \sum_{R (j) \land S (j)} a_{j}$ . It is suﬃcient to show that the convergence of three sums is suﬃcient for the convergence of the fourth.

Case 1. [ $\sum_{R (j)} a_{j}$ , $\sum_{S (j)} a_{j}$ , $\sum_{R (j) \lor S (j)} a_{j}$ converge.] We must show that $\sum_{R (j) \land S (j)} a_{j}$ converges. But if the sums $\sum_{R (j)} a_{j}$ , $\sum_{S (j)} a_{j}$ exist, then clearly their conjunction $\sum_{R (j) \land S (j)} a_{j}$ exists.

Case 2. [ $\sum_{R (j)} a_{j}$ , $\sum_{S (j)} a_{j}$ , $\sum_{R (j) \land S (j)} a_{j}$ converge.] We must sow that $\sum_{R (j) \lor S (j)} a_{j}$ converges. But if the sums $\sum_{R (j)} a_{j}$ , $\sum_{S (j)} a_{j}$ exist, then clearly their disjunction $\sum_{R (j) \lor S (j)} a_{j}$ exists.

Case 3. [ $\sum_{R (j)} a_{j}$ , $\sum_{R (j) \lor S (j)} a_{j}$ , $\sum_{R (j) \land S (j)} a_{j}$ converge.] We must show that $\sum_{S (j)} a_{j}$ converges. But if the conjunction $\sum_{R (j) \land S (j)} a_{j}$ exists, then clearly the single sum $\sum_{S (j)} a_{j}$ exists.

Case 4. [ $\sum_{S (j)} a_{j}$ , $\sum_{R (j) \lor S (j)} a_{j}$ , $\sum_{R (j) \land S (j)} a_{j}$ converge.] We must show that $\sum_{R (j)} a_{j}$ converges. But if the conjunction $\sum_{R (j) \land S (j)} a_{j}$ exists, then clearly the single sum $\sum_{R (j)} a_{j}$ exists.

Therefore, in all cases, we have shown that the convergence of three sums is suﬃcient for the convergence of the fourth. □

7. [HM23] Given that

c

is an integer, show that

\sum_{R (j)} a_{j} = \sum_{R (c - j)} a_{c - j}

, even if both series are inﬁnite.

Proposition. $\sum_{R (j)} a_{j} = \sum_{R (c - j)} a_{c - j}$ , even if both series are inﬁnite.

Proof. Assume that $R$ is an arbitrary relation. We must show that $\sum_{R (j)} a_{j} = \sum_{R (c - j)} a_{c - j}$ , even if both series are inﬁnite. Since $R^{'} (j) = c - j$ is a permutation of the integers, proving the ﬁnite case, we must show the inﬁnite case. But

\begin{array}{l} \sum_{R (j)} a_{j} & = (\lim_{n \to \infty} \sum_{\begin{array}{c} R (j) \\ 0 \leq j < n \end{array}} a_{j}) + (\lim_{n \to \infty} \sum_{\begin{array}{c} R (j) \\ - n \leq j < 0 \end{array}} a_{j}) \\ = (\lim_{n \to \infty} \sum_{\begin{array}{c} R (c - j) \\ 0 \leq c - j < n \end{array}} a_{c - j}) + (\lim_{n \to \infty} \sum_{\begin{array}{c} R (c - j) \\ - n \leq c - j < 0 \end{array}} a_{c - j}) \\ = \sum_{R (c - j)} a_{c - j} \end{array}

as we needed to show. □

An example of an inﬁnite series in which $\sum_{R (i)} \sum_{S (j)} a_{i j} \neq \sum_{S (j)} \sum_{R (j)} a_{i j}$ is given by

a_{i j} = \{\begin{matrix} - 1 & if i - 1 = j \\ 1 & if i + 1 = j \\ 0 & otherwise \end{matrix}

for $S (i) \equiv i \geq 0$ , $R (j) \equiv j \geq 0$ . Then

\begin{array}{l} \sum_{R (i)} \sum_{S (j)} a_{i j} & = \lim_{n \to \infty} \sum_{0 \leq i < n} \sum_{0 \leq j < n} a_{i j} \\ = \lim_{n \to \infty} (\sum_{0 \leq i < 1} \sum_{0 \leq j < n} a_{i j} + \sum_{1 \leq i < n} \sum_{0 \leq j < n} a_{i j}) \\ = \lim_{n \to \infty} (a_{01} + \sum_{1 \leq i < n} \sum_{0 \leq j < n} a_{i j}) \\ = \lim_{n \to \infty} (- 1 + \sum_{1 \leq i < n} \sum_{0 \leq j < n} a_{i j}) \\ = - 1 \end{array}

and

\begin{array}{l} \sum_{S (j)} \sum_{R (i)} a_{i j} & = \lim_{n \to \infty} \sum_{0 \leq j < n} \sum_{0 \leq i < n} a_{i j} \\ = \lim_{n \to \infty} (\sum_{0 \leq j < 1} \sum_{0 \leq i < n} a_{i j} + \sum_{1 \leq j < n} \sum_{0 \leq i < n} a_{i j}) \\ = \lim_{n \to \infty} (a_{10} + \sum_{1 \leq j < n} \sum_{0 \leq i < n} a_{i j}) \\ = \lim_{n \to \infty} (1 + \sum_{1 \leq j < n} \sum_{0 \leq i < n} a_{i j}) \\ = 1 . \end{array}

No, the derivation for Eq. (14) is not valid if $n = - 1$ , since the application of rule (d) assumes $n \geq 0$ . That is, if $n = - 1$

\sum_{0 \leq j \leq - 1} a x^{j} \neq a + \sum_{1 \leq j \leq - 1} a x^{j}

(depsite the fact that $\sum_{0 \leq j \leq - 1} a x^{j} = 0 = a (\frac{1 - x^{- 1 + 1}}{1 - x})$ ).

No, the derivation for Eq. (14) is not valid if $n = - 2$ , since the application of rule (d) assumes $n \geq 0$ . That is, if $n = - 2$

\sum_{0 \leq j \leq - 2} a x^{j} \neq a + \sum_{1 \leq j \leq - 2} a x^{j} .

In the case $x = 1$

\begin{array}{l} \sum_{0 \leq j \leq n} a x^{j} & = \sum_{0 \leq j \leq n} a {(1)}^{j} \\ = \sum_{0 \leq j \leq n} a \\ = (n + 1) a . \end{array}

12. [10] What is

1 + \frac{1}{7} + \frac{1}{49} + \frac{1}{343} + \dots + {(\frac{1}{7})}^{n}

The sum $1 + \frac{1}{7} + \frac{1}{49} + \frac{1}{343} + \dots + {(\frac{1}{7})}^{n}$ is simply a geometric progression whose closed form is given by Eq. (14) with $a = 1$ and $x = \frac{1}{7}$ . This yields

\begin{array}{l} \sum_{0 \leq j \leq n} (1) {(\frac{1}{7})}^{j} & = (1) (\frac{1 - {(\frac{1}{7})}^{n + 1}}{1 - \frac{1}{7}}) \\ = \frac{1 - {(\frac{1}{7})}^{n + 1}}{6 ∕ 7} \\ = \frac{7}{6} (1 - 1 ∕ 7^{n + 1}) . \end{array}

13. [10] Using Eq. (15) and assuming that

m \leq n

, evaluate

\sum_{j = m}^{n} j

Since

\sum_{m \leq j \leq n} j = \sum_{0 \leq j \leq n} j - \sum_{0 \leq j \leq m - 1} j

we can use Eq. (15) with $a = 0$ and $b = 1$ to evaluate each term on the right-hand side as

\begin{array}{l} \sum_{m \leq j \leq n} j & = \sum_{0 \leq j \leq n} j - \sum_{0 \leq j \leq m - 1} j \\ = \frac{1}{2} n (n + 1) - \frac{1}{2} (m - 1) m \\ = \frac{1}{2} (n (n + 1) - m (m - 1)) . \end{array}

14. [11] Using the result of the previous exercise, evaluate

\sum_{j = m}^{n} \sum_{k = r}^{s} j k

Since $\sum_{m \leq j \leq n} j = \frac{1}{2} (n (n + 1) - m (m - 1))$ , we can evaluate the sum as

\begin{array}{l} \sum_{m \leq j \leq n} \sum_{r \leq k \leq s} j k & = (\sum_{m \leq j \leq n} j) (\sum_{r \leq k \leq s} k) \\ = (\frac{1}{2} (n (n + 1) - m (m - 1))) (\frac{1}{2} (s (s + 1) - r (r - 1))) \\ = \frac{1}{4} ((n (n + 1) - m (m - 1)) (s (s + 1) - r (r - 1))) . \end{array}

▸

15. [M22] Compute the sum

1 \times 2 + 2 \times 2^{2} + 3 \times 2^{3} + \dots + n \times 2^{n}

for small values of

n

. Do you see the pattern developing in these numbers? If not, discover it by manipulations similar to those leading up to Eq. (14).

We can manipulate the sum as

\begin{array}{l} \sum_{0 \leq k \leq n} k 2^{k} & = 0 + \sum_{1 \leq k \leq n} k 2^{k} \\ = \sum_{1 \leq k \leq n} k 2^{k} \\ = 2 \sum_{1 \leq k \leq n} k 2^{k - 1} \\ = 2 \sum_{0 \leq k \leq n - 1} (k + 1) 2^{k} \\ = 2 (\sum_{0 \leq k \leq n - 1} k 2^{k} + \sum_{0 \leq k \leq n - 1} 2^{k}) \\ = 2 (\sum_{0 \leq k \leq n} k 2^{k} - n 2^{n} + \sum_{0 \leq k \leq n - 1} 2^{k}) \\ = 2 (\sum_{0 \leq k \leq n} k 2^{k} - n 2^{n} - (1 - 2^{n})) \\ = 2 \sum_{0 \leq k \leq n} k 2^{k} - n 2^{n + 1} - (2 - 2^{n + 1}) . \end{array}

Comparing the ﬁrst with the last yields

\begin{array}{l} \sum_{0 \leq k \leq n} k 2^{k} & = n 2^{n + 1} + 2 - 2^{n + 1} \\ = 2 (n 2^{n} - 2^{n} + 1) . \end{array}

Proposition. $\sum_{0 \leq j \leq n} j x^{j} = \frac{n x^{n + 2} - (n + 1) x^{n + 1} + x}{{(x - 1)}^{2}}$ if $x \neq 1$ .

Proof. Assume that $x \neq 1$ , $n \geq 0$ . Then

\begin{array}{l} \sum_{0 \leq j \leq n} j x^{j} & = 0 + \sum_{1 \leq j \leq n} j x^{j} \\ = \sum_{1 \leq j \leq n} j x^{j} \\ = x \sum_{1 \leq j \leq n} j x^{j - 1} \\ = x \sum_{0 \leq j \leq n - 1} (j + 1) x^{j} \\ = x (\sum_{0 \leq j \leq n - 1} j x^{j} + \sum_{0 \leq j \leq n - 1} x^{j}) \\ = x (\sum_{0 \leq j \leq n} j x^{j} - n x^{n} + \sum_{0 \leq j \leq n - 1} x^{j}) \\ = x (\sum_{0 \leq j \leq n} j x^{j} - n x^{n} + \frac{1 - x^{n}}{1 - x}) \\ = x \sum_{0 \leq j \leq n} j x^{j} - n x^{n + 1} + x \frac{1 - x^{n}}{1 - x} . \end{array}

Comparing the ﬁrst relation with the last, we have

(1 - x) \sum_{0 \leq j \leq n} j x^{j} = - n x^{n + 1} + x \frac{1 - x^{n}}{1 - x};

hence we obtain the formula

\begin{array}{l} \sum_{0 \leq j \leq n} j x^{j} & = \frac{- (1 - x) n x^{n + 1}}{{(1 - x)}^{2}} + x \frac{1 - x^{n}}{{(1 - x)}^{2}} \\ = \frac{- n x^{n + 1} + n x^{n + 2} + x - x^{n + 1}}{{(1 - x)}^{2}} \\ = \frac{n x^{n + 2} - (n + 1) x^{n + 1} + x}{{(1 - x)}^{2}} \end{array}

as we needed to show. □

$\sum_{j \in S} 1$ is the cardinality—the number of elements—of $S$ ; that is,

\sum_{j \in S} 1 = | S | .

18. [M20] Show how to interchange the order of summation as in Eq. (9) given that

R (i)

is the relation “

n

is a multiple of

i

” and

S (i, j)

is the relation “

1 \leq j < i

.”

In Eq. (9), we have

\sum_{R (i)} \sum_{S (i, j)} a_{i j} = \sum_{S^{'} (j)} \sum_{R^{'} (i, j)} a_{i j}

for $S^{'} (j) \equiv (\exists i) (R (i) \land S (i, j))$ and $R^{'} (i, j) \equiv R (i) \land S (i, j)$ .

In the case that $R (i) \equiv (\exists k) (k i = n)$ and $S (i, j) \equiv 1 \leq j < i$ , we ﬁnd

\begin{array}{l} S^{'} (j) & \equiv (\exists i) (R (i) \land S (i, j)) \\ \equiv (\exists i) ((\exists k) (k i = n) \land 1 \leq j < i) \\ \equiv 1 \leq j < n & for i \leq n, k \geq 1 \end{array}

and

\begin{array}{l} R^{'} (i, j) & \equiv R (i) \land S (i, j) \\ \equiv (\exists k) (k i = n) \land 1 \leq j < i \\ \equiv (\exists k) (k i = n) \land j < i; \end{array}

that is, $S^{'} (j)$ the relation “ $1 \leq j < n$ ” and $R^{'} (i, j)$ the relation “ $n$ is a multiple of $i$ and $i > j$ .”

We have that

\begin{array}{l} \sum_{m \leq j \leq n} (a_{j} - a_{j - 1}) & = \sum_{m \leq j \leq n} a_{j} - \sum_{m \leq j \leq n} a_{j - 1} \\ = \sum_{m \leq j \leq n} a_{j} - \sum_{m - 1 \leq j \leq n - 1} a_{j} \\ = \sum_{m \leq j \leq n} a_{j} - a_{m - 1} - \sum_{m \leq j \leq n} a_{j} + a_{n} \\ = a_{n} - a_{m - 1} \end{array}

assuming $m \leq n$ .

The remarkable sequence of formulas observed by Dr. I. J. Matrix are analyzed below.

a.

The good doctor’s great discovery in terms of the

\sum

-notation is

(10 - 1) \sum_{0 \leq k \leq n} (n - k) 1 0^{k} + n + 1 = \sum_{0 \leq k \leq n} 1 0^{k} .

b.

The above formula may be generalized for perhaps any base

b

(b - 1) \sum_{0 \leq k \leq n} (n - k) b^{k} + n + 1 = \sum_{0 \leq k \leq n} b^{k} .

c.

We may prove the above formula.

Proposition. $(b - 1) \sum_{0 \leq k \leq n} (n - k) b^{k} + n + 1 = \sum_{0 \leq k \leq n} b^{k}$ .

Proof. Assume an arbitrary base $b \geq 2$ , and $n \geq 0$ . We must show that

(b - 1) \sum_{0 \leq k \leq n} (n - k) b^{k} + n + 1 = \sum_{0 \leq k \leq n} b^{k} .

But

\begin{array}{l} (b - 1) \sum_{0 \leq k \leq n} (n - k) b^{k} + n + 1 \\ = (b - 1) (n \sum_{0 \leq k \leq n} b^{k} - \sum_{0 \leq k \leq n} k b^{k}) + n + 1 \\ = (b - 1) (n (\frac{1 - b^{n + 1}}{1 - b}) - \sum_{0 \leq k \leq n} k b^{k}) + n + 1 & by Eq. (14) \\ = (b - 1) (n (\frac{1 - b^{n + 1}}{1 - b}) - (\frac{n b^{n + 2} - (n + 1) b^{n + 1} + b}{{(b - 1)}^{2}})) + n + 1 & by exercise 16 \\ = n (b^{n + 1} - 1) + \frac{b (b^{n} (- n b + n + 1) - 1)}{b - 1} + n + 1 \\ = \frac{b^{n + 1} + n - b (n + 1)}{b - 1} + n + 1 \\ = \frac{1 - b^{n + 1}}{1 - b} \\ = \sum_{0 \leq k \leq n} b^{k} & by Eq. (14) \end{array}

as we needed to show. □

We may derive rule (d) for manipulating the domain

\sum_{R (j)} a_{j} + \sum_{S (j)} a_{j} = \sum_{R (j) \lor S (j)} a_{j} + \sum_{R (j) \land S (j)} a_{j}

from Eq. (8)

\sum_{R (i)} (b_{i} + c_{i}) = \sum_{R (i)} b_{i} + \sum_{R (i)} c_{i}

and Eq. (17)

\sum_{R (j)} a_{j} = \sum_{j} a_{j} [R (j)] .

Given that $[p] + [q] = [p \lor q] + [p \land q]$ , as evidenced by the following table

$[p]$	$[q]$	$[p] + [q]$	$[p \lor q]$	$[p \land q]$	$[p \lor q] + [p \land q]$

$0$	$0$	$0$	$0$	$0$	$0$
$0$	$1$	$1$	$1$	$0$	$1$
$1$	$0$	$1$	$1$	$0$	$1$
$1$	$1$	$2$	$1$	$1$	$2$

we have

\begin{array}{l} \sum_{R (j)} a_{j} + \sum_{S (j)} a_{j} & = \sum_{j} a_{j} [R (j)] + \sum_{j} a_{j} [S (j)] & by Eq. (17) \\ = \sum_{j} (a_{j} [R (j)] + a_{j} [S (j)]) & by Eq. (8) \\ = \sum_{j} a_{j} ([R (j)] + [S (j)]) \\ = \sum_{j} a_{j} ([R (j) \lor S (j)] + [R (j) \land S (j)]) \\ = \sum_{j} a_{j} [R (j) \lor S (j)] + \sum_{j} a_{j} [R (j) \land S (j)] & by Eq. (8) \\ = \sum_{R (j) \lor S (j)} a_{j} + \sum_{R (j) \land S (j)} a_{j} . & by Eq. (17) \end{array}

▸

22. [20] State the appropriate analogs of Eqs. (5), (7), (8), and (11) for products instead of sums.

We have the following analogs for products: change of variable:

\prod_{R (i)} a_{i} = \prod_{R (j)} = \prod_{R (p (j))} a_{p (j)};

interchanging order of production:

\prod_{R (i)} \prod_{S (j)} a_{i j} = \prod_{S (j)} \prod_{R (i)} a_{i j};

a special case of the above:

\prod_{R (i)} (b_{i} c_{i}) = (\prod_{R (i)} b_{i}) (\prod_{R (i)} c_{i});

and manipulating the domain:

(\prod_{R (j)} a_{j}) (\prod_{S (j)} a_{j}) = (\prod_{R (j) \lor S (j)} a_{j}) (\prod_{R (j) \land S (j)} a_{j}) .

23. [10] Explain why it is a good idea to deﬁne

\sum_{R (j)} a_{j}

and

\prod_{R (j)} a_{j}

as zero and one, respectively, when no integers satisify

R (j)

It is a good idea to deﬁne $\sum_{j \in \emptyset} a_{j} = 0$ and $\prod_{j \in \emptyset} a_{j} = 1$ as they are the identity elements for the operations of addition and multiplication, respectively. This way, $\sum_{j \in \emptyset} a_{j} + \sum_{R (j)} a_{j} = \sum_{R (j)} a_{j}$ and $(\prod_{j \in \emptyset} a_{j}) (\prod_{R (j)} a_{j}) = \prod_{R (j)} a_{j}$ .

24. [20] Suppose that

R (j)

is true for only ﬁnitely many

j

. By induction on the number of integers satisfying

R (j)

, prove that

\log_{b} \prod_{R (j)} a_{j} = \sum_{R (j)} (\log_{b} a_{j})

, assuming that all

a_{j} > 0

Proposition. $\log_{b} \prod_{R (j)} a_{j} = \sum_{R (j)} (\log_{b} a_{j})$ for all $a_{j} > 0$ .

Proof. Suppose $a_{j} > 0$ for $0 \leq j \leq n$ . We must show that $\log_{b} \prod_{0 \leq j \leq n} a_{j} = \sum_{0 \leq j \leq n} (\log_{b} a_{j})$ .

If $n = 0$ , clearly $\log_{b} \prod_{0 \leq j \leq 0} a_{j} = \log_{b} a_{0} = \sum_{0 \leq j \leq 0} (\log_{b} a_{j})$ . Then, assuming

\log_{b} \prod_{0 \leq j \leq k} a_{j} = \sum_{0 \leq j \leq k} (\log_{b} a_{j}),

we must show that

\log_{b} \prod_{0 \leq j \leq k + 1} a_{j} = \sum_{0 \leq j \leq k + 1} (\log_{b} a_{j}) .

But

\begin{array}{l} \log_{b} \prod_{0 \leq j \leq k + 1} a_{j} & = \log_{b} (a_{k + 1} \prod_{0 \leq j \leq k} a_{j}) \\ = \log_{b} \prod_{0 \leq j \leq k} a_{j} + \log_{b} a_{k + 1} \\ = \sum_{0 \leq j \leq k} (\log_{b} a_{j}) + \log_{b} a_{k + 1} \\ = \sum_{0 \leq j \leq k + 1} (\log_{b} a_{j}) \end{array}

as we needed to show. □

Yes. For one,

\sum_{1 \leq i \leq n} \sum_{1 \leq j \leq n} \frac{a_{i}}{a_{j}} \neq \sum_{1 \leq i \leq n} \sum_{1 \leq i \leq n} \frac{a_{i}}{a_{i}};

and for another,

\sum_{1 \leq i \leq n} \sum_{1 \leq i \leq n} \frac{a_{i}}{a_{i}} \neq \sum_{i = 1}^{n} 1

(in fact, $\sum_{1 \leq i \leq n} \sum_{1 \leq i \leq n} \frac{a_{i}}{a_{i}} = \sum_{i = 1}^{n} n = n^{2}$ ).

26. [25] Show that

\prod_{i = 0}^{n} \prod_{j = 0}^{i} a_{i} a_{j}

may be expressed in terms of

\prod_{i = 0}^{n} a_{i}

by manipulating the

\prod

-notation as stated in exercise 22.

Proposition. $\prod_{0 \leq i \leq n} \prod_{0 \leq j \leq i} a_{i} a_{j} = {(\prod_{0 \leq i \leq n} a_{i})}^{n + 2}$ .

Proof. We must show that $\prod_{0 \leq i \leq n} \prod_{0 \leq j \leq i} a_{i} a_{j} = {(\prod_{0 \leq i \leq n} a_{i})}^{n + 2}$ .

First note that

\prod_{0 \leq i \leq n} \prod_{0 \leq j \leq i} a_{i} a_{j} = \prod_{0 \leq i \leq n} \prod_{i \leq j \leq n} a_{i} a_{j};

and then that

\begin{array}{l} {(\prod_{0 \leq i \leq n} \prod_{0 \leq j \leq i} a_{i} a_{j})}^{2} & = (\prod_{0 \leq i \leq n} \prod_{0 \leq j \leq i} a_{i} a_{j}) (\prod_{0 \leq i \leq n} \prod_{0 \leq j \leq i} a_{i} a_{j}) \\ = \prod_{0 \leq i \leq n} ((\prod_{0 \leq j \leq i} a_{i} a_{j}) (\prod_{0 \leq j \leq i} a_{i} a_{j})) \\ = \prod_{0 \leq i \leq n} ((\prod_{0 \leq j \leq i} a_{i} a_{j}) (\prod_{i \leq j \leq n} a_{i} a_{j})) \\ = \prod_{0 \leq i \leq n} ((\prod_{0 \leq j \leq n} a_{i} a_{j}) (a_{i} a_{i})) \\ = (\prod_{0 \leq i \leq n} \prod_{0 \leq j \leq n} a_{i} a_{j}) (\prod_{0 \leq i \leq n} a_{i}^{2}) \\ = (\prod_{0 \leq i \leq n} (a_{i}^{n + 1} \prod_{0 \leq j \leq n} a_{j})) {(\prod_{0 \leq i \leq n} a_{i})}^{2} \\ = {(\prod_{0 \leq i \leq n} a_{i})}^{n + 1} (\prod_{0 \leq i \leq n} \prod_{0 \leq j \leq n} a_{j}) {(\prod_{0 \leq i \leq n} a_{i})}^{2} \\ = {(\prod_{0 \leq i \leq n} a_{i})}^{n + 1} {(\prod_{0 \leq j \leq n} a_{j})}^{n + 1} {(\prod_{0 \leq i \leq n} a_{i})}^{2} \\ = {(\prod_{0 \leq i \leq n} a_{i})}^{2 n + 4} . \end{array}

Therefore,

\prod_{0 \leq i \leq n} \prod_{0 \leq j \leq i} a_{i} a_{j} = {(\prod_{0 \leq i \leq n} a_{i})}^{n + 2}

as we needed to show. □

Proposition. $\prod_{1 \leq j \leq n} (1 - a_{j}) \geq 1 - \sum_{1 \leq j \leq n} a_{j}$ if $0 < a_{j} < 1$ .

Proof. Let $0 < a_{j} < 1$ for $1 \leq j \leq n$ , $n \geq 0$ . We must show that

\prod_{1 \leq j \leq n} (1 - a_{j}) \geq 1 - \sum_{1 \leq j \leq n} a_{j} .

If $n = 0$ , then clearly $\prod_{1 \leq j \leq n} (1 - a_{j}) = 1 \geq 1 = 1 - \sum_{1 \leq j \leq n} a_{j}$ . Then, assuming

\prod_{1 \leq j \leq k} (1 - a_{j}) \geq 1 - \sum_{1 \leq j \leq k} a_{j},

we must show that

\prod_{1 \leq j \leq k + 1} (1 - a_{j}) \geq 1 - \sum_{1 \leq j \leq k + 1} a_{j} .

But since $a_{k + 1} \sum_{0 \leq j \leq k} a_{k} \geq 1$ ,

\begin{array}{l} \prod_{1 \leq j \leq k + 1} (1 - a_{j}) & = (\prod_{1 \leq j \leq k} (1 - a_{j})) (1 - a_{k + 1}) \\ \geq (1 - \sum_{1 \leq j \leq k} a_{j}) (1 - a_{k + 1}) \\ = (1 - \sum_{1 \leq j \leq k} a_{j}) - (a_{k + 1} - a_{k + 1} \sum_{0 \leq j \leq k} a_{j}) \\ = 1 - \sum_{0 \leq j \leq k} a_{j} - a_{k + 1} + a_{k + 1} \sum_{0 \leq j \leq k} a_{k} \\ \geq 1 - (\sum_{0 \leq j \leq k} a_{j} + a_{k + 1}) \\ = 1 - \sum_{1 \leq j \leq k + 1} a_{j} \end{array}

as we needed to show. □

We ﬁnd that

\begin{array}{l} \prod_{2 \leq j \leq n} (1 - \frac{1}{j^{2}}) & = \prod_{2 \leq j \leq n} \frac{j^{2} - 1}{j^{2}} \\ = (\prod_{2 \leq j \leq n} \frac{1}{j^{2}}) (\prod_{2 \leq j \leq n} (j - 1) (j + 1)) \\ = {(\prod_{2 \leq j \leq n} \frac{1}{j})}^{2} (\prod_{1 \leq j \leq n - 1} j) (\prod_{3 \leq j \leq n + 1} j) \\ = {(\frac{1}{n!})}^{2} (n - 1)! \frac{(n + 1)!}{2} \\ = \frac{n + 1}{2 n} . \end{array}

▸

29. [M30] (a) Express

\sum_{i = 0}^{n} \sum_{j = 0}^{i} \sum_{k = 0}^{j} a_{i} a_{j} a_{k}

in terms of the multiple-sum notation explained at the end of the section. (b) Express the same sum in terms of

\sum_{i = 0}^{n} a_{i}

\sum_{i = 0}^{n} a_{i}^{2}

, and

\sum_{i = 0}^{n} a_{i}^{3}

[see Eq. (13)].

a.

We can express the sum in terms of the multiple-sum notation as

\sum_{0 \leq i \leq n} \sum_{0 \leq j \leq i} \sum_{0 \leq k \leq j} a_{i} a_{j} a_{k} = \sum_{0 \leq k \leq j \leq i \leq n} a_{i} a_{j} a_{k} .

b.

From Eq. (13) for arbitrary

i > 0

we have

\sum_{0 \leq j \leq i - 1} \sum_{0 \leq k \leq j} a_{j} a_{k} = \frac{1}{2} ({(\sum_{0 \leq j \leq i - 1} a_{j})}^{2} + \sum_{0 \leq j \leq i - 1} a_{j}^{2})

or equivalently

{(\sum_{0 \leq j \leq i - 1} a_{j})}^{2} = 2 \sum_{0 \leq j \leq i - 1} \sum_{0 \leq k \leq j} a_{j} a_{k} - \sum_{0 \leq j \leq i - 1} a_{j}^{2} .

Also for arbitrary $i > 0$ we have that

\begin{array}{l} {(\sum_{0 \leq j \leq i} a_{j})}^{3} \\ = {(\sum_{0 \leq j \leq i - 1} a_{j} + a_{i})}^{3} \\ = {(\sum_{0 \leq j \leq i - 1} a_{j})}^{3} + 3 a_{i} {(\sum_{0 \leq j \leq i - 1} a_{j})}^{2} + 3 a_{i}^{2} \sum_{0 \leq j \leq i - 1} a_{j} + a_{i}^{3} \\ = {(\sum_{0 \leq j \leq i - 1} a_{j})}^{3} + 3 a_{i} (2 \sum_{0 \leq j \leq i - 1} \sum_{0 \leq k \leq j} a_{j} a_{k} - \sum_{0 \leq j \leq i - 1} a_{j}^{2}) + 3 a_{i}^{2} \sum_{0 \leq j \leq i - 1} a_{j} + a_{i}^{3} \\ = {(\sum_{0 \leq j \leq i - 1} a_{j})}^{3} + 6 \sum_{0 \leq j \leq i - 1} \sum_{0 \leq k \leq j} a_{i} a_{j} a_{k} - 3 \sum_{0 \leq j \leq i - 1} a_{i} a_{j}^{2} + 3 \sum_{0 \leq j \leq i - 1} a_{i}^{2} a_{j} + a_{i}^{3} \\ = {(\sum_{0 \leq j \leq i - 1} a_{j})}^{3} + 6 \sum_{0 \leq j \leq i - 1} \sum_{0 \leq k \leq j} a_{i} a_{j} a_{k} - 3 \sum_{0 \leq j \leq i} a_{i} a_{j}^{2} + 3 \sum_{0 \leq j \leq i} a_{i}^{2} a_{j} + a_{i}^{3} \\ = {(\sum_{0 \leq j \leq i - 1} a_{j})}^{3} + 6 \sum_{0 \leq j \leq i} \sum_{0 \leq k \leq j} a_{i} a_{j} a_{k} - 6 \sum_{0 \leq j \leq i} a_{i}^{2} a_{j} - 3 \sum_{0 \leq j \leq i} a_{i} a_{j}^{2} + 3 \sum_{0 \leq j \leq i} a_{i}^{2} a_{j} + a_{i}^{3} \\ = {(\sum_{0 \leq j \leq i - 1} a_{j})}^{3} + 6 \sum_{0 \leq j \leq i} \sum_{0 \leq k \leq j} a_{i} a_{j} a_{k} - 3 \sum_{0 \leq j \leq i} a_{i} a_{j}^{2} - 3 \sum_{0 \leq j \leq i} a_{i}^{2} a_{j} + a_{i}^{3} \\ = {(\sum_{0 \leq j \leq i - 1} a_{j})}^{3} + 6 \sum_{0 \leq j \leq i} \sum_{0 \leq k \leq j} a_{i} a_{j} a_{k} - 3 \sum_{0 \leq j \leq i} a_{i} a_{j} (a_{i} + a_{j}) + a_{i}^{3} \end{array}

and in the trivial case for $i = 0$ that

{(\sum_{0 \leq j \leq i} a_{j})}^{3} = a_{0}^{3} = {(0)}^{3} + 6 a_{0}^{3} - 3 (2) a_{0}^{3} + a_{0}^{3}

so that

6 \sum_{0 \leq j \leq i} \sum_{0 \leq k \leq j} a_{i} a_{j} a_{k} = {(\sum_{0 \leq j \leq i} a_{j})}^{3} - {(\sum_{0 \leq j \leq i - 1} a_{j})}^{3} + 3 \sum_{0 \leq j \leq i} a_{i} a_{j} (a_{i} + a_{j}) - a_{i}^{3}

and so that for $0 \leq i \leq n$ we have $6 \sum_{0 \leq i \leq n} \sum_{0 \leq j \leq i} \sum_{0 \leq k \leq j} a_{i} a_{j} a_{k}$ equivalent to

\sum_{0 \leq i \leq n} ({(\sum_{0 \leq j \leq i} a_{j})}^{3} - {(\sum_{0 \leq j \leq i - 1} a_{j})}^{3}) + 3 \sum_{0 \leq i \leq n} \sum_{0 \leq j \leq i} a_{i} a_{j} (a_{i} + a_{j}) - \sum_{0 \leq i \leq n} a_{i}^{3} .

We may also prove by induction that

\sum_{0 \leq i \leq n} ({(\sum_{0 \leq j \leq i} a_{j})}^{3} - {(\sum_{0 \leq j \leq i - 1} a_{j})}^{3}) = {(\sum_{0 \leq i \leq n} a_{i})}^{3} .

If $n = 0$ , clearly $a_{0}^{3} - {(0)}^{3} = a_{0}^{3}$ . Then, assuming

\sum_{0 \leq i \leq k} ({(\sum_{0 \leq j \leq i} a_{j})}^{3} - {(\sum_{0 \leq j \leq i - 1} a_{j})}^{3}) = {(\sum_{0 \leq i \leq k} a_{i})}^{3}

we must show that

\sum_{0 \leq i \leq k + 1} ({(\sum_{0 \leq j \leq i} a_{j})}^{3} - {(\sum_{0 \leq j \leq i - 1} a_{j})}^{3}) = {(\sum_{0 \leq i \leq k + 1} a_{i})}^{3} .

But

\begin{array}{l} \sum_{0 \leq i \leq k + 1} ({(\sum_{0 \leq j \leq i} a_{j})}^{3} - {(\sum_{0 \leq j \leq i - 1} a_{j})}^{3}) \\ = \sum_{0 \leq i \leq k} ({(\sum_{0 \leq j \leq i} a_{j})}^{3} - {(\sum_{0 \leq j \leq i - 1} a_{j})}^{3}) + {(\sum_{0 \leq j \leq k + 1} a_{j})}^{3} - {(\sum_{0 \leq j \leq k} a_{j})}^{3} \\ = {(\sum_{0 \leq i \leq k} a_{i})}^{3} + {(\sum_{0 \leq j \leq k + 1} a_{j})}^{3} - {(\sum_{0 \leq j \leq k} a_{j})}^{3} \\ = {(\sum_{0 \leq j \leq k + 1} a_{j})}^{3} \end{array}

And so ﬁnally, we have that

6 \sum_{0 \leq i \leq n} \sum_{0 \leq j \leq i} \sum_{0 \leq k \leq j} a_{i} a_{j} a_{k} = {(\sum_{0 \leq i \leq n} a_{i})}^{3} + 3 \sum_{0 \leq i \leq n} \sum_{0 \leq j \leq i} a_{i} a_{j} (a_{i} + a_{j}) - \sum_{0 \leq i \leq n} a_{i}^{3}

and

\begin{array}{l} 6 \sum_{0 \leq i \leq n} \sum_{0 \leq j \leq i} \sum_{0 \leq k \leq j} a_{i} a_{j} a_{k} \\ = {(\sum_{0 \leq i \leq n} a_{i})}^{3} + 3 \sum_{0 \leq i \leq n} \sum_{0 \leq j \leq i} a_{i} a_{j} (a_{i} + a_{j}) - \sum_{0 \leq i \leq n} a_{i}^{3} \\ = {(\sum_{0 \leq i \leq n} a_{i})}^{3} + \sum_{0 \leq i \leq n} \sum_{0 \leq j \leq i} a_{i} a_{j} (a_{i} + a_{j}) - \sum_{0 \leq i \leq n} a_{i}^{3} + 2 \sum_{0 \leq i \leq n} \sum_{0 \leq j \leq i} a_{i} a_{j} (a_{i} + a_{j}) \\ \begin{aligned} = {(\sum_{0 \leq i \leq n} a_{i})}^{3} + \sum_{0 \leq i \leq n} (\frac{1}{2} \sum_{0 \leq j \leq i} a_{i} a_{j} (a_{i} + a_{j}) + \frac{1}{2} \sum_{i \leq j \leq n} a_{i} a_{j} (a_{i} + a_{j})) \\ - \sum_{0 \leq i \leq n} a_{i}^{3} + 2 \sum_{0 \leq i \leq n} \sum_{0 \leq j \leq i} a_{i} a_{j} (a_{i} + a_{j}) \end{aligned} \\ \begin{aligned} = {(\sum_{0 \leq i \leq n} a_{i})}^{3} + \sum_{0 \leq i \leq n} (\frac{1}{2} \sum_{0 \leq j \leq n} a_{i} a_{j}^{2} + \frac{1}{2} \sum_{0 \leq j \leq n} a_{i}^{2} a_{j} + a_{i}^{3}) \\ - \sum_{0 \leq i \leq n} a_{i}^{3} + 2 \sum_{0 \leq i \leq n} \sum_{0 \leq j \leq i} a_{i} a_{j} (a_{i} + a_{j}) \end{aligned} \\ = {(\sum_{0 \leq i \leq n} a_{i})}^{3} + (\sum_{0 \leq i \leq n} a_{i}) (\sum_{0 \leq i \leq n} a_{i}^{2}) + \sum_{0 \leq i \leq n} a_{i}^{3} - \sum_{0 \leq i \leq n} a_{i}^{3} + 2 \sum_{0 \leq i \leq n} \sum_{0 \leq j \leq i} a_{i} a_{j} (a_{i} + a_{j}) \\ = {(\sum_{0 \leq i \leq n} a_{i})}^{3} + (\sum_{0 \leq i \leq n} a_{i}) (\sum_{0 \leq i \leq n} a_{i}^{2}) + 2 \sum_{0 \leq i \leq n} \sum_{0 \leq j \leq i} a_{i} a_{j} (a_{i} + a_{j}) \\ = {(\sum_{0 \leq i \leq n} a_{i})}^{3} + (\sum_{0 \leq i \leq n} a_{i}) (\sum_{0 \leq i \leq n} a_{i}^{2}) + \sum_{0 \leq i \leq n} (\sum_{0 \leq j \leq i} a_{i} a_{j} (a_{i} + a_{j}) + \sum_{i \leq j \leq n} a_{i} a_{j} (a_{i} + a_{j})) \\ = {(\sum_{0 \leq i \leq n} a_{i})}^{3} + (\sum_{0 \leq i \leq n} a_{i}) (\sum_{0 \leq i \leq n} a_{i}^{2}) + \sum_{0 \leq i \leq n} (\sum_{0 \leq j \leq n} a_{i} a_{j} (a_{i} + a_{j}) + 2 a_{i}^{3}) \\ = {(\sum_{0 \leq i \leq n} a_{i})}^{3} + (\sum_{0 \leq i \leq n} a_{i}) (\sum_{0 \leq i \leq n} a_{i}^{2}) + \sum_{0 \leq i \leq n} \sum_{0 \leq j \leq n} a_{i} a_{j}^{2} + \sum_{0 \leq i \leq n} \sum_{0 \leq j \leq n} a_{i}^{2} a_{j} + 2 \sum_{0 \leq i \leq n} a_{i}^{3} \\ = {(\sum_{0 \leq i \leq n} a_{i})}^{3} + (\sum_{0 \leq i \leq n} a_{i}) (\sum_{0 \leq i \leq n} a_{i}^{2}) + 2 (\sum_{0 \leq i \leq n} a_{i}) (\sum_{0 \leq i \leq n} a_{i}^{2}) + 2 \sum_{0 \leq i \leq n} a_{i}^{3} \\ = {(\sum_{0 \leq i \leq n} a_{i})}^{3} + 3 (\sum_{0 \leq i \leq n} a_{i}) (\sum_{0 \leq i \leq n} a_{i}^{2}) + 2 \sum_{0 \leq i \leq n} a_{i}^{3} \end{array}

Therefore,

\sum_{0 \leq i \leq n} \sum_{0 \leq j \leq i} \sum_{0 \leq k \leq j} a_{i} a_{j} a_{k} = \frac{1}{6} {(\sum_{0 \leq i \leq n} a_{i})}^{3} + \frac{1}{2} (\sum_{0 \leq i \leq n} a_{i}) (\sum_{0 \leq i \leq n} a_{i}^{2}) + \frac{1}{3} \sum_{0 \leq i \leq n} a_{i}^{3} .

[An important special case arises when

w_{1}, \dots, w_{n}, z_{1}, \dots, z_{n}

are aribtrary complex numbers and we set

a_{j} = w_{j}

b_{j} = {\bar{z}}_{j}

x_{j} = {\bar{w}}_{j}

y_{j} = z_{j}

The terms

| w_{j} {\bar{z}}_{j} |^{2}

are nonnegative, so the famous Cauchy-Schwarz inequality

Proposition. $(\sum_{1 \leq j \leq n} a_{j} x_{j}) (\sum_{1 \leq j \leq n} b_{j} y_{j}) = (\sum_{1 \leq j \leq n} a_{j} y_{j}) (\sum_{1 \leq j \leq n} b_{j} x_{j}) + \sum_{1 \leq j \leq n} \sum_{j < k \leq n} (a_{j} b_{k} - a_{k} b_{j}) (x_{j} y_{k} - x_{k} y_{j})$ .

Proof. We need to show that

(\sum_{1 \leq j \leq n} a_{j} x_{j}) (\sum_{1 \leq j \leq n} b_{j} y_{j}) = (\sum_{1 \leq j \leq n} a_{j} y_{j}) (\sum_{1 \leq j \leq n} b_{j} x_{j}) + \sum_{1 \leq j \leq n} \sum_{j < k \leq n} (a_{j} b_{k} - a_{k} b_{j}) (x_{j} y_{k} - x_{k} y_{j}) .

But

\begin{array}{l} \sum_{1 \leq j \leq n} \sum_{j < k \leq n} (a_{j} b_{k} - a_{k} b_{j}) (x_{j} y_{k} - x_{k} y_{j}) \\ = \sum_{1 \leq j \leq n} \sum_{j < k \leq n} a_{j} b_{k} (x_{j} y_{k} - x_{k} y_{j}) - \sum_{1 \leq j \leq n} \sum_{j < k \leq n} a_{k} b_{j} (x_{j} y_{k} - x_{k} y_{j}) \\ = \sum_{1 \leq j \leq n} \sum_{j < k \leq n} a_{j} b_{k} (x_{j} y_{k} - x_{k} y_{j}) + \sum_{1 \leq j \leq n} \sum_{j < k \leq n} a_{k} b_{j} (x_{k} y_{j} - x_{j} y_{k}) \\ = \sum_{1 \leq j \leq n} \sum_{j < k \leq n} a_{j} b_{k} (x_{j} y_{k} - x_{k} y_{j}) + \sum_{1 \leq k \leq n} \sum_{k < j \leq n} a_{j} b_{k} (x_{j} y_{k} - x_{k} y_{j}) \\ = \sum_{1 \leq j \leq n} \sum_{j < k \leq n} a_{j} b_{k} (x_{j} y_{k} - x_{k} y_{j}) + \sum_{1 \leq j \leq n} \sum_{1 \leq k < j} a_{j} b_{k} (x_{j} y_{k} - x_{k} y_{j}) \\ = \sum_{1 \leq j \leq n} \sum_{1 \leq k < j} a_{j} b_{k} (x_{j} y_{k} - x_{k} y_{j}) + 0 + \sum_{1 \leq j \leq n} \sum_{j < k \leq n} a_{j} b_{k} (x_{j} y_{k} - x_{k} y_{j}) \\ = \sum_{1 \leq j \leq n} \sum_{1 \leq k < j} a_{j} b_{k} (x_{j} y_{k} - y_{j} x_{k}) + \sum_{1 \leq j \leq n} a_{j} b_{j} (x_{j} y_{j} - y_{j} x_{j}) + \sum_{1 \leq j \leq n} \sum_{j < k \leq n} a_{j} b_{k} (x_{j} y_{k} - y_{j} x_{k}) \\ = \sum_{1 \leq j \leq n} \sum_{1 \leq k \leq n} a_{j} b_{k} (x_{j} y_{k} - y_{j} x_{k}) \\ = \sum_{1 \leq j \leq n} \sum_{1 \leq k \leq n} a_{j} x_{j} b_{k} y_{k} - \sum_{1 \leq j \leq n} \sum_{1 \leq k \leq n} a_{j} y_{j} b_{k} x_{k} \\ = (\sum_{1 \leq j \leq n} a_{j} x_{j}) (\sum_{1 \leq j \leq n} b_{j} y_{j}) - (\sum_{1 \leq j \leq n} a_{j} y_{j}) (\sum_{1 \leq j \leq n} b_{j} x_{j}) \end{array}

as we needed to show. □

31. [M20] Use Binet’s formula to express the sum

\sum_{1 \leq j \leq k \leq n} (u_{j} - u_{k}) (v_{j} - v_{k})

in terms of

\sum_{j = 1}^{n} u_{j} v_{j}

\sum_{j = 1}^{n} u_{j}

, and

\sum_{j = 1}^{n} v_{j}

We want to ﬁnd an expression for

\sum_{1 \leq j n} \sum_{j < k \leq n} (u_{j} - u_{k}) (v_{j} - v_{k})

in terms of $\sum_{1 \leq j \leq n} u_{j} v_{j}$ , $\sum_{1 \leq j \leq n} u_{j}$ , and $\sum_{1 \leq j \leq n} v_{j}$ .

From Binet’s formula we have that

\sum_{1 \leq j \leq n} \sum_{j < k \leq n} (a_{j} b_{k} - a_{k} b_{j}) (x_{j} y_{k} - x_{k} y_{j}) = (\sum_{1 \leq j \leq n} a_{j} x_{j}) (\sum_{1 \leq j \leq n} b_{j} y_{j}) - (\sum_{1 \leq j \leq n} a_{j} y_{j}) (\sum_{1 \leq j \leq n} b_{j} x_{j}) .

If we let $a_{j} = u_{j}$ , $x_{j} = v_{j}$ , and $b_{j} = y_{j} = 1$ , we ﬁnd

\begin{array}{l} \sum_{1 \leq j \leq n} \sum_{j < k \leq n} (u_{j} - u_{k}) (v_{j} - v_{k}) \\ = (\sum_{1 \leq j \leq n} u_{j} v_{j}) (\sum_{1 \leq j \leq n} 1) - (\sum_{1 \leq j \leq n} u_{j}) (\sum_{1 \leq j \leq n} v_{j}) \\ = n \sum_{1 \leq j \leq n} u_{j} v_{j} - (\sum_{1 \leq j \leq n} u_{j}) (\sum_{1 \leq j \leq n} v_{j}) . \end{array}

______________________________________________________________________________________________________________________________

[See Soobschch. Mat. Obschch. Khar’kovskom Univ. 4, 2 (1882), 93–98.]

Proposition. $\prod_{1 \leq j \leq n} \sum_{1 \leq i_{j} \leq m} a_{i_{j} j} = \sum_{1 \leq i_{1}, \dots, i_{n} \leq m} a_{i_{1} 1} \dots a_{i_{n} n}$ .

Proof. We need to show that

\prod_{1 \leq j \leq n} \sum_{1 \leq i_{j} \leq m} a_{i_{j} j} = \sum_{1 \leq i_{1}, \dots, i_{n} \leq m} a_{i_{1} 1} \dots a_{i_{n} n} .

If $n = 1$ , clearly $\sum_{1 \leq i_{1} \leq m} a_{i_{1} 1} = \sum_{1 \leq i_{1} \leq m} a_{i_{1} 1}$ . Then, assuming that

\prod_{1 \leq j \leq k} \sum_{1 \leq i_{j} \leq m} a_{i_{j} j} = \sum_{1 \leq i_{1}, \dots, i_{k} \leq m} a_{i_{1} 1} \dots a_{i_{k} k}

we must show that

\prod_{1 \leq j \leq k + 1} \sum_{1 \leq i_{j} \leq m} a_{i_{j} j} = \sum_{1 \leq i_{1}, \dots, i_{k + 1} \leq m} a_{i_{1} 1} \dots a_{i_{k + 1} (k + 1)} .

But

\begin{array}{l} \prod_{1 \leq j \leq k + 1} \sum_{1 \leq i_{j} \leq m} a_{i_{j} j} & = (\prod_{1 \leq j \leq k} \sum_{1 \leq i_{j} \leq m} a_{i_{j} j}) \sum_{1 \leq i_{k + 1} \leq m} a_{i_{k + 1} (k + 1)} \\ = (\sum_{1 \leq i_{1}, \dots, i_{k} \leq m} a_{i_{1} 1} \dots a_{i_{k} k}) \sum_{1 \leq i_{k + 1} \leq m} a_{i_{k + 1} (k + 1)} \\ = \sum_{1 \leq i_{1}, \dots, i_{k + 1} \leq m} a_{i_{1} 1} \dots a_{i_{k + 1} (k + 1)} \end{array}

as we needed to show. □

▸

33. [M30] One evening Dr. Matrix discovered some formulas that might even be classed as more remarkable than those of exercise 20:

Prove that these formulas are a special case of a general law; let

x_{1}, x_{2}, \dots, x_{n}

be distinct numbers, and show that

Proposition. $\sum_{1 \leq i \leq n} (\frac{x_{i}^{r}}{\prod_{\begin{array}{c} 1 \leq j \leq n \\ j \neq i \end{array}} (x_{i} - x_{j})}) = \{\begin{matrix} 0 & if 0 \leq r < n - 1 \\ 1 & if r = n - 1 \\ \sum_{1 \leq i \leq n} x_{i} & if r = n \end{matrix}$ if $x_{1}, x_{2}, \dots, x_{n}$ distinct.

Proof. For an arbitrary series of distinct numbers $x_{i}$ , $1 \leq i \leq n$ , and for an arbitrary $ι$ , $1 \leq ι \leq n$ , let $P (x_{ι}) = x_{ι}^{r}$ for $0 \leq r \leq n$ , and $Q (x_{ι}) = \prod_{\begin{array}{c} 1 \leq i \leq n \\ i \neq ι \end{array}} (x_{ι} - x_{i})$ . By the fundamental theorem of algebra and the method of partial fractions, since $r = \deg P \leq \deg Q + 1 = n$ , we have that

\frac{P (x_{ι})}{Q (x_{ι})} = \frac{x_{ι}^{r}}{\prod_{\begin{array}{c} 1 \leq i \leq n \\ i \neq ι \end{array}} (x_{ι} - x_{i})} = D (x_{ι}) + \sum_{\begin{array}{c} 1 \leq i \leq n \\ i \neq ι \end{array}} \frac{c_{i}}{x_{ι} - x_{i}}

for constants $c_{i}$ , where $D (x_{ι})$ is the polynomial divisor with remainder $R (x_{ι})$ such that

\begin{matrix} P (x_{ι}) = D (x_{ι}) Q (x_{ι}) + R (x_{ι}) \deg R < \deg Q \end{matrix}

By polynomial division, we have

D (x_{ι}) = \{\begin{matrix} 0 & if 0 \leq r = \deg P < \deg Q = n - 1 \\ 1 & if r = \deg P = \deg Q = n - 1 \\ \sum_{1 \leq i \leq n} x_{i} & if r = \deg P = \deg Q + 1 = n \end{matrix}

Also, for an arbitrary $κ$ , $1 \leq κ \leq n$ , we have

\begin{array}{l} \frac{x_{ι}^{r}}{\prod_{\begin{array}{c} 1 \leq i \leq n \\ i \neq ι \end{array}} (x_{ι} - x_{i})} = D (x_{ι}) + \sum_{\begin{array}{c} 1 \leq i \leq n \\ i \neq ι \end{array}} \frac{c_{i}}{x_{ι} - x_{i}} \\ \Leftrightarrow \frac{x_{ι}^{r}}{(x_{ι} - x_{κ}) \prod_{\begin{array}{c} 1 \leq i \leq n \\ i \neq ι \\ i \neq κ \end{array}} (x_{ι} - x_{i})} = D (x_{ι}) + \sum_{\begin{array}{c} 1 \leq i \leq n \\ i \neq ι \\ i \neq κ \end{array}} \frac{c_{i}}{x_{ι} - x_{i}} + \frac{c_{κ}}{x_{ι} - x_{κ}} \\ \Leftrightarrow \frac{x_{ι}^{r} (x_{ι} - x_{κ})}{(x_{ι} - x_{κ}) \prod_{\begin{array}{c} 1 \leq i \leq n \\ i \neq ι \\ i \neq κ \end{array}} (x_{ι} - x_{i})} = (x_{ι} - x_{κ}) D (x_{ι}) + (x_{ι} - x_{κ}) \sum_{\begin{array}{c} 1 \leq i \leq n \\ i \neq ι \\ i \neq κ \end{array}} \frac{c_{i}}{x_{ι} - x_{i}} + \frac{c_{κ} (x_{ι} - x_{κ})}{x_{ι} - x_{κ}} \\ \Leftrightarrow \frac{x_{ι}^{r}}{\prod_{\begin{array}{c} 1 \leq i \leq n \\ i \neq ι \\ i \neq κ \end{array}} (x_{ι} - x_{i})} = (x_{ι} - x_{κ}) D (x_{ι}) + (x_{ι} - x_{κ}) \sum_{\begin{array}{c} 1 \leq i \leq n \\ i \neq ι \\ i \neq κ \end{array}} \frac{c_{i}}{x_{ι} - x_{i}} + c_{κ} \\ \Leftrightarrow c_{κ} = \frac{x_{ι}^{r}}{\prod_{\begin{array}{c} 1 \leq i \leq n \\ i \neq ι \\ i \neq κ \end{array}} (x_{ι} - x_{i})} + (x_{κ} - x_{ι}) D (x_{ι}) + (x_{κ} - x_{ι}) \sum_{\begin{array}{c} 1 \leq i \leq n \\ i \neq ι \\ i \neq κ \end{array}} \frac{c_{i}}{x_{ι} - x_{i}} \end{array}

Letting $ι = κ$ , we ﬁnd

\begin{array}{l} c_{κ} & = \frac{x_{κ}^{r}}{\prod_{\begin{array}{c} 1 \leq i \leq n \\ i \neq κ \end{array}} (x_{κ} - x_{i})} + (x_{κ} - x_{κ}) D (x_{κ}) + (x_{κ} - x_{κ}) \sum_{\begin{array}{c} 1 \leq i \leq n \\ i \neq κ \end{array}} \frac{c_{i}}{x_{κ} - x_{i}} \\ = \frac{x_{κ}^{r}}{\prod_{\begin{array}{c} 1 \leq i \leq n \\ i \neq κ \end{array}} (x_{κ} - x_{i})} \end{array}

And so

\begin{array}{l} \frac{x_{ι}^{r}}{\prod_{\begin{array}{c} 1 \leq i \leq n \\ i \neq ι \end{array}} (x_{ι} - x_{i})} & = D (x_{ι}) + \sum_{\begin{array}{c} 1 \leq i \leq n \\ i \neq ι \end{array}} \frac{c_{i}}{x_{ι} - x_{i}} \\ = D (x_{ι}) + \sum_{\begin{array}{c} 1 \leq i \leq n \\ i \neq ι \end{array}} \frac{x_{i}^{r}}{(x_{ι} - x_{i}) \prod_{\begin{array}{c} 1 \leq j \leq n \\ j \neq i \end{array}} (x_{i} - x_{j})} \\ = D (x_{ι}) - \sum_{\begin{array}{c} 1 \leq i \leq n \\ i \neq ι \end{array}} \frac{x_{i}^{r}}{(x_{i} - x_{ι}) \prod_{\begin{array}{c} 1 \leq j \leq n \\ j \neq i \end{array}} (x_{i} - x_{j})} \end{array}

or equivalently

D (x_{ι}) = \frac{x_{ι}^{r}}{\prod_{\begin{array}{c} 1 \leq i \leq n \\ i \neq ι \end{array}} (x_{ι} - x_{i})} + \sum_{\begin{array}{c} 1 \leq i \leq n \\ i \neq ι \end{array}} \frac{x_{i}^{r}}{(x_{i} - x_{ι}) \prod_{\begin{array}{c} 1 \leq j \leq n \\ j \neq i \end{array}} (x_{i} - x_{j})}

letting $ι = n$ yields

\begin{array}{l} D (x_{n}) \\ = \frac{x_{n}^{r}}{\prod_{\begin{array}{c} 1 \leq i \leq n \\ i \neq n \end{array}} (x_{n} - x_{i})} + \sum_{\begin{array}{c} 1 \leq i \leq n \\ i \neq n \end{array}} \frac{x_{i}^{r}}{(x_{i} - x_{n}) \prod_{\begin{array}{c} 1 \leq j \leq n \\ j \neq i \end{array}} (x_{i} - x_{j})} \\ = \sum_{1 \leq i \leq n - 1} \frac{x_{i}^{r}}{(x_{i} - x_{n}) \prod_{\begin{array}{c} 1 \leq j \leq n - 1 \\ j \neq i \end{array}} (x_{i} - x_{j})} + \frac{x_{n}^{r}}{\prod_{\begin{array}{c} 1 \leq i \leq n - 1 \end{array}} (x_{n} - x_{i})} \\ \begin{aligned} = \frac{\sum_{1 \leq i \leq n - 1} ((\prod_{\begin{array}{c} 1 \leq j \leq n - 1 \\ j \neq i \end{array}} \prod_{\begin{array}{c} 1 \leq k \leq n - 1 \\ k \neq j \end{array}} (x_{j} - x_{k})) \frac{x_{i}^{r}}{x_{i} - x_{n}})}{(\prod_{1 \leq i \leq n - 1} \prod_{\begin{array}{c} 1 \leq j \leq n - 1 \\ j \neq i \end{array}} (x_{i} - x_{j}))} \\ + \frac{x_{n}^{r}}{\prod_{\begin{array}{c} 1 \leq i \leq n - 1 \end{array}} (x_{n} - x_{i})} \end{aligned} \\ \begin{aligned} = \frac{\sum_{1 \leq i \leq n - 1} (\frac{1}{x_{i} - x_{n}} (\prod_{\begin{array}{c} 1 \leq j \leq n - 1 \\ j \neq i \end{array}} \prod_{\begin{array}{c} 1 \leq k \leq n - 1 \\ k \neq j \end{array}} (x_{j} - x_{k})) x_{i}^{r})}{(\prod_{1 \leq i \leq n - 1} \prod_{\begin{array}{c} 1 \leq j \leq n - 1 \\ j \neq i \end{array}} (x_{i} - x_{j}))} \\ + \frac{x_{n}^{r}}{\prod_{\begin{array}{c} 1 \leq i \leq n - 1 \end{array}} (x_{n} - x_{i})} \end{aligned} \\ \begin{aligned} = \frac{\sum_{1 \leq i \leq n - 1} ((\prod_{\begin{array}{c} 1 \leq j \leq n - 1 \\ j \neq i \end{array}} (x_{j} - x_{n})) (\prod_{\begin{array}{c} 1 \leq j \leq n - 1 \\ j \neq i \end{array}} \prod_{\begin{array}{c} 1 \leq k \leq n - 1 \\ k \neq j \end{array}} (x_{j} - x_{k})) x_{i}^{r})}{(\prod_{1 \leq i \leq n - 1} (x_{i} - x_{n})) (\prod_{1 \leq i \leq n - 1} \prod_{\begin{array}{c} 1 \leq j \leq n - 1 \\ j \neq i \end{array}} (x_{i} - x_{j}))} \\ + \frac{x_{n}^{r}}{\prod_{\begin{array}{c} 1 \leq i \leq n - 1 \end{array}} (x_{n} - x_{i})} \end{aligned} \\ \begin{aligned} = \frac{\sum_{1 \leq i \leq n - 1} ((\prod_{\begin{array}{c} 1 \leq j \leq n - 1 \end{array}} (x_{n} - x_{j})) (\prod_{\begin{array}{c} 1 \leq j \leq n - 1 \\ j \neq i \end{array}} (x_{j} - x_{n})) (\prod_{\begin{array}{c} 1 \leq j \leq n - 1 \\ j \neq i \end{array}} \prod_{\begin{array}{c} 1 \leq k \leq n - 1 \\ k \neq j \end{array}} (x_{j} - x_{k})) x_{i}^{r})}{(\prod_{\begin{array}{c} 1 \leq j \leq n - 1 \end{array}} (x_{n} - x_{j})) (\prod_{1 \leq i \leq n - 1} (x_{i} - x_{n})) (\prod_{1 \leq i \leq n - 1} \prod_{\begin{array}{c} 1 \leq j \leq n - 1 \\ j \neq i \end{array}} (x_{i} - x_{j}))} \\ + \frac{(\prod_{\begin{array}{c} 1 \leq i \leq n - 1 \end{array}} (x_{i} - x_{n})) (\prod_{\begin{array}{c} 1 \leq i \leq n - 1 \end{array}} \prod_{\begin{array}{c} 1 \leq j \leq n - 1 \\ j \neq i \end{array}} (x_{i} - x_{j})) x_{n}^{r}}{(\prod_{\begin{array}{c} 1 \leq j \leq n - 1 \end{array}} (x_{n} - x_{j})) (\prod_{1 \leq i \leq n - 1} (x_{i} - x_{n})) (\prod_{1 \leq i \leq n - 1} \prod_{\begin{array}{c} 1 \leq j \leq n - 1 \\ j \neq i \end{array}} (x_{i} - x_{j}))} \end{aligned} \\ = \frac{U}{V} \end{array}

where

\begin{array}{l} U \begin{aligned} = \sum_{1 \leq i \leq n - 1} ((\prod_{\begin{array}{c} 1 \leq j \leq n - 1 \end{array}} (x_{n} - x_{j})) (\prod_{\begin{array}{c} 1 \leq j \leq n - 1 \\ j \neq i \end{array}} (x_{j} - x_{n})) (\prod_{\begin{array}{c} 1 \leq j \leq n - 1 \\ j \neq i \end{array}} \prod_{\begin{array}{c} 1 \leq k \leq n - 1 \\ k \neq j \end{array}} (x_{j} - x_{k})) x_{i}^{r}) \\ + ((\prod_{\begin{array}{c} 1 \leq i \leq n - 1 \end{array}} (x_{i} - x_{n})) (\prod_{\begin{array}{c} 1 \leq i \leq n - 1 \end{array}} \prod_{\begin{array}{c} 1 \leq j \leq n - 1 \\ j \neq i \end{array}} (x_{i} - x_{j}))) x_{n}^{r} \end{aligned} \\ \begin{aligned} = \sum_{1 \leq i \leq n - 1} ((\prod_{\begin{array}{c} 1 \leq j \leq n - 1 \end{array}} (x_{n} - x_{j})) (\prod_{\begin{array}{c} 1 \leq j \leq n - 1 \\ j \neq i \end{array}} (x_{j} - x_{n})) (\prod_{\begin{array}{c} 1 \leq j \leq n - 1 \\ j \neq i \end{array}} \prod_{\begin{array}{c} 1 \leq k \leq n - 1 \\ k \neq j \end{array}} (x_{j} - x_{k})) x_{i}^{r}) \\ + (\prod_{\begin{array}{c} 1 \leq i \leq n - 1 \end{array}} ((\prod_{\begin{array}{c} 1 \leq j \leq n - 1 \\ j \neq i \end{array}} (x_{i} - x_{j})) (x_{i} - x_{n}))) x_{n}^{r} \end{aligned} \\ \begin{aligned} = \sum_{1 \leq i \leq n - 1} ((\prod_{\begin{array}{c} 1 \leq j \leq n - 1 \end{array}} (x_{n} - x_{j})) (\prod_{\begin{array}{c} 1 \leq j \leq n - 1 \\ j \neq i \end{array}} (x_{j} - x_{n})) (\prod_{\begin{array}{c} 1 \leq j \leq n - 1 \\ j \neq i \end{array}} \prod_{\begin{array}{c} 1 \leq k \leq n - 1 \\ k \neq j \end{array}} (x_{j} - x_{k})) x_{i}^{r}) \\ + (\prod_{\begin{array}{c} 1 \leq i \leq n - 1 \end{array}} \prod_{\begin{array}{c} 1 \leq j \leq n \\ j \neq i \end{array}} (x_{i} - x_{j})) x_{n}^{r} \end{aligned} \\ \begin{aligned} = \sum_{1 \leq i \leq n - 1} ((\prod_{\begin{array}{c} 1 \leq j \leq n - 1 \\ j \neq i \end{array}} ((\prod_{\begin{array}{c} 1 \leq k \leq n - 1 \\ k \neq j \end{array}} (x_{j} - x_{k})) (x_{j} - x_{n}))) (\prod_{\begin{array}{c} 1 \leq k \leq n \\ k \neq n \end{array}} (x_{n} - x_{k})) x_{i}^{r}) \\ + (\prod_{\begin{array}{c} 1 \leq j \leq n \\ j \neq n \end{array}} \prod_{\begin{array}{c} 1 \leq k \leq n \\ k \neq j \end{array}} (x_{j} - x_{k})) x_{n}^{r} \end{aligned} \\ \begin{aligned} = \sum_{1 \leq i \leq n - 1} ((\prod_{\begin{array}{c} 1 \leq j \leq n - 1 \\ j \neq i \end{array}} \prod_{\begin{array}{c} 1 \leq k \leq n \\ k \neq j \end{array}} (x_{j} - x_{k})) (\prod_{\begin{array}{c} 1 \leq k \leq n \\ k \neq n \end{array}} (x_{n} - x_{k})) x_{i}^{r}) \\ + (\prod_{\begin{array}{c} 1 \leq j \leq n \\ j \neq n \end{array}} \prod_{\begin{array}{c} 1 \leq k \leq n \\ k \neq j \end{array}} (x_{j} - x_{k})) x_{n}^{r} \end{aligned} \\ \begin{aligned} = \sum_{1 \leq i \leq n - 1} ((\prod_{\begin{array}{c} 1 \leq j \leq n \\ j \neq i \end{array}} \prod_{\begin{array}{c} 1 \leq k \leq n \\ k \neq j \end{array}} (x_{j} - x_{k})) x_{i}^{r}) \\ + (\prod_{\begin{array}{c} 1 \leq j \leq n \\ j \neq n \end{array}} \prod_{\begin{array}{c} 1 \leq k \leq n \\ k \neq j \end{array}} (x_{j} - x_{k})) x_{n}^{r} \end{aligned} \\ = \sum_{1 \leq i \leq n} ((\prod_{\begin{array}{c} 1 \leq j \leq n \\ j \neq i \end{array}} \prod_{\begin{array}{c} 1 \leq k \leq n \\ k \neq j \end{array}} (x_{j} - x_{k})) x_{i}^{r}) \end{array}

and where

\begin{array}{l} V & = (\prod_{\begin{array}{c} 1 \leq j \leq n - 1 \end{array}} (x_{n} - x_{j})) (\prod_{1 \leq i \leq n - 1} (x_{i} - x_{n})) (\prod_{1 \leq i \leq n - 1} \prod_{\begin{array}{c} 1 \leq j \leq n - 1 \\ j \neq i \end{array}} (x_{i} - x_{j})) \\ = (\prod_{1 \leq i \leq n - 1} ((\prod_{\begin{array}{c} 1 \leq j \leq n - 1 \\ j \neq i \end{array}} (x_{i} - x_{j})) (x_{i} - x_{n}))) (\prod_{\begin{array}{c} 1 \leq j \leq n - 1 \end{array}} (x_{n} - x_{j})) \\ = (\prod_{1 \leq i \leq n - 1} \prod_{\begin{array}{c} 1 \leq j \leq n \\ j \neq i \end{array}} (x_{i} - x_{j})) (\prod_{\begin{array}{c} 1 \leq j \leq n - 1 \end{array}} (x_{n} - x_{j})) \\ = \prod_{1 \leq i \leq n} \prod \begin{array}{c} 1 \leq j \leq n \\ j \neq i \end{array} (x_{i} - x_{j}) \end{array}

so that

D (x_{n}) = \frac{U}{V} = \frac{\sum_{1 \leq i \leq n} ((\prod_{\begin{array}{c} 1 \leq j \leq n \\ j \neq i \end{array}} \prod_{\begin{array}{c} 1 \leq k \leq n \\ k \neq j \end{array}} (x_{j} - x_{k})) x_{i}^{r})}{\prod_{1 \leq i \leq n} \prod_{\begin{array}{c} 1 \leq j \leq n \\ j \neq i \end{array}} (x_{i} - x_{j})} = \sum_{1 \leq i \leq n} \frac{x_{i}^{r}}{\prod_{\begin{array}{c} 1 \leq j \leq n \\ j \neq i \end{array}} (x_{i} - x_{j})} .

That is,

\sum_{1 \leq i \leq n} \frac{x_{i}^{r}}{\prod_{\begin{array}{c} 1 \leq j \leq n \\ j \neq i \end{array}} (x_{i} - x_{j})} = \{\begin{matrix} 0 & if 0 \leq r < n - 1 \\ 1 & if r = n - 1 \\ \sum_{1 \leq i \leq n} x_{i} & if r = n \end{matrix}

as we needed to show. □

______________________________________________________________________________________________________________________________

Notes: Dr. Matrix was anticipated in this discovery by L. Euler, who wrote to Christian Golbach about it on 9 November 1762. See Euler’s Institutionum Calculi Integralis 2 (1769), §1169; and E. Waring, Phil. Trans. 69 (1779), 64–67 $\dots$ [J. J. Sylvester, Quart. J. Math. 1 (1857), 141–152.]

provided that

1 \leq m \leq n

and

x

is arbitrary. For example, if

n = 4

and

m = 2

, then

Proposition. $\sum_{1 \leq i \leq n} \frac{\prod_{1 \leq j \leq n, j \neq k} (x + i - j)}{\prod_{1 \leq j \leq n, j \neq i} (i - j)} = 1$ provided that $1 \leq k \leq n$ and $x$ is arbitrary.

Proof. We may prove

\sum_{1 \leq i \leq n} \frac{\prod_{1 \leq j \leq n, j \neq k} (x + i - j)}{\prod_{1 \leq j \leq n, j \neq i} (i - j)} = 1

provided that $1 \leq k \leq n$ and $x$ is arbitrary, but ﬁrst we shall ﬁrst prove the more general result

\sum_{1 \leq i \leq n} \frac{\prod_{1 \leq j \leq n, j \neq k} (y_{i} - z_{j})}{\prod_{1 \leq j \leq n, j \neq i} (y_{i} - y_{j})} = 1 .

Let $P (y)$ be the polynomial representation of $\prod_{1 \leq j \leq n, j \neq k} (y - z_{j})$ where

P (y) = \prod_{\begin{array}{c} 1 \leq j \leq n \\ j \neq k \end{array}} (y - z_{j}) = \sum_{0 \leq j \leq n - 1} c_{j} y^{j}

for arbitrary coeﬃcients $c_{0}, c_{1}, \dots, c_{n - 1}$ . Note that since $P (y) = y^{n - 1} + \dots$ , $c_{n - 1} = 1$ . Then, from exercise 33, we ﬁnd that

\begin{array}{l} \sum_{1 \leq i \leq n} \frac{\prod_{1 \leq j \leq n, j \neq k} (y_{i} - z_{j})}{\prod_{1 \leq j \leq n, j \neq i} (y_{i} - y_{j})} & = \sum_{1 \leq i \leq n} \frac{P (y_{i})}{\prod_{1 \leq j \leq n, j \neq i} (y_{i} - y_{j})} \\ = \sum_{1 \leq i \leq n} \frac{\sum_{0 \leq j \leq n - 1} c_{j} y_{i}^{j}}{\prod_{1 \leq j \leq n, j \neq i} (y_{i} - y_{j})} \\ = \sum_{1 \leq j \leq n} \frac{\sum_{0 \leq i \leq n - 1} c_{i} y_{j}^{i}}{\prod_{1 \leq k \leq n, k \neq j} (y_{j} - y_{k})} \\ = \sum_{0 \leq i \leq n - 1} c_{i} \sum_{1 \leq j \leq n} \frac{y_{j}^{i}}{\prod_{1 \leq k \leq n, k \neq j} (y_{j} - y_{k})} \\ \begin{aligned} = (\sum_{0 \leq i < n - 1} c_{i} (\sum_{1 \leq j \leq n} \frac{y_{j}^{i}}{\prod_{1 \leq k \leq n, k \neq j} (y_{j} - y_{k})})) \\ + c_{n - 1} (\sum_{1 \leq j \leq n} \frac{y_{j}^{n - 1}}{\prod_{1 \leq k \leq n, k \neq j} (y_{j} - y_{k})}) \end{aligned} \\ = (\sum_{0 \leq i < n - 1} c_{i} (0)) + c_{n - 1} (1) \\ = c_{n - 1} \\ = 1 . \end{array}

Letting $y_{i} = i$ and $z_{i} = i + x$ for $1 \leq i \leq n$ , $1 \leq k \leq n$ , and $x$ arbitrary, we have that

\sum_{1 \leq i \leq n} \frac{\prod_{1 \leq j \leq n, j \neq k} (x + i - j)}{\prod_{1 \leq j \leq n, j \neq i} (i - j)} = 1

as we needed to show. □

35. [HM20] The notation

\sup_{R (j)} a_{j}

is used to denote the least upper bound of the elements

a_{j}

, in a manner analogous to the

\sum

- and

\prod

-notations. (When

R (j)

is satisﬁed for only ﬁnitely many

j

, the notation

\max_{R (j)} a_{j}

is often used to denote the same quantity.) Show how rules (a), (b), (c), and (d) can be adapted for manipulation of this notation. In particular discuss the following analog of rule (a):

and give a suitable deﬁnition for the notation when

R (j)

is satisﬁed for no

j

We have the following analogs for the least upper bound: an additive law:

(\sup_{R (i)} a_{i}) + (\sup_{S (j)} b_{j}) = \sup_{R (i)} (\sup_{S (j)} (a_{i} + b_{j}))

as well as a multiplicative law:

(\sup_{R (i)} a_{i}) (\sup_{S (j)} b_{j}) = \sup_{R (i)} (\sup_{S (j)} (a_{i} b_{j}))

provided $a_{i}$ and $a_{j}$ are nonnegative; change of variable:

\sup_{R (i)} a_{i} = \sup_{R (j)} = \sup_{R (p (j))} a_{p (j)};

interchanging order of bound:

\sup_{R (i)} \sup_{S (j)} a_{i j} = \sup_{S (j)} \sup_{R (i)} a_{i j};

and manipulating the domain:

\sup (\sup_{R (j)} a_{j}, \sup_{S (j)} a_{j}) = \sup_{R (j) \lor S (j)} a_{j} .

A suitable deﬁnition for the notation when $R (j)$ is satisﬁed for no $j$ would be

\sup_{j \in \emptyset} = - \infty

since $- \infty$ acts as the identity element for the least upper bound, in that $\sup (\sup_{j \in \emptyset} a_{j}, \sup_{R (j)} a_{j}) = \sup_{R (j)} a_{j}$ .

36. [M23] Show that the determinant of the combinatorial matrix is

x^{n - 1} (x + n y)

Proposition. $\det {[y + δ_{i j} x]}_{n} = x^{n - 1} (n y + x)$ .

Proof. For

A n = {[a_{i j}]}_{n} = {[y + δ_{i j} x]}_{n} = {[\begin{matrix} y + x & y & \dots & y \\ y & y + x & \dots & y \\ ⋮ & ⋮ & ⋱ & ⋮ \\ y & y & \dots & y + x \end{matrix}]}_{n},

we must show that

\det {[a_{i j}]}_{n} = x^{n - 1} (n y + x) .

Let

a_{i j}^{'} = \{\begin{matrix} a_{i 1} & if j = 1 \\ a_{i j} - a_{i 1} & if 2 \leq j \leq n \end{matrix}

and

a_{i j}^{″} = \{\begin{matrix} a_{1 j}^{'} + \sum_{2 \leq k \leq n} a_{k j}^{'} & if i = 1 \\ a_{i j}^{'} & if 2 \leq i \leq n \end{matrix}

so that $\det {[a_{i j}]}_{n} = \det {[a_{i j}^{″}]}_{n}$ where

a_{i j}^{″} = \{\begin{matrix} n y + x & if i = 1, j = 1 \\ 0 & if i = 1, 2 \leq j \leq n \\ y & if 2 \leq i \leq n, j = 1 \\ δ_{i j} x & if 2 \leq i \leq n, 2 \leq j \leq n \end{matrix}

since:

\begin{array}{l} a_{11}^{'} & = a_{11} = y + x & i = 1, j = 1 \\ a_{1 j}^{'} & = - x & i = 1, 2 \leq j \leq n \\ a_{i 1}^{'} & = a_{i 1} = y & 2 \leq i \leq n, j = 1 \\ a_{i j}^{'} & = δ_{i j} x & 2 \leq i \leq n, 2 \leq j \leq n \\ a_{11}^{″} & = a_{11}^{'} + \sum_{2 \leq k \leq n} a_{k 1}^{'} = y + x + \sum_{2 \leq k \leq n} y = n y + x & i = 1, j = 1 \\ a_{1 j}^{″} & = a_{1 j}^{'} + \sum_{2 \leq k \leq n} a_{k j}^{'} = - x + \sum_{2 \leq k \leq n} δ_{k j} x = 0 & i = 1, 2 \leq j \leq n \\ a_{i 1}^{″} & = a_{i 1}^{'} = y & 2 \leq i \leq n, j = 1 \\ a_{i j}^{″} & = a_{i j}^{'} = δ_{i j} x & 2 \leq i \leq n, 2 \leq j \leq n \end{array}

Then, since ${[a_{i j}^{″}]}_{n}$ is a triangular matrix ( $a_{i j}^{″} = 0$ whenever $i < j$ ), we have that

\begin{array}{l} \det {[a_{i j}]}_{n} & = \det {[a_{i j}^{″}]}_{n} \\ = \prod_{1 \leq k \leq n} a_{k k}^{″} \\ = a_{11}^{″} \prod_{2 \leq k \leq n} a_{k k}^{″} \\ = (n y + x) \prod_{2 \leq k \leq n} δ_{k k} x \\ = (n y + x) \prod_{2 \leq k \leq n} x \\ = (n y + x) x^{n - 1} \\ = x^{n - 1} (n y + x) \end{array}

as we needed to show. □

Proposition. $\det {[x_{j}^{i}]}_{n} = \prod_{1 \leq i \leq n} x_{i} \prod_{1 \leq j < i \leq n} (x_{i} - x_{j})$ .

Proof. For

A n = {[a_{i j}]}_{n} = {[x_{j}^{i}]}_{n} = {[\begin{matrix} x_{1} & x_{2} & \dots & x_{n} \\ x_{1}^{2} & x_{2}^{2} & \dots & x_{n}^{2} \\ ⋮ & ⋮ & ⋱ & ⋮ \\ x_{1}^{n} & x_{2}^{n} & \dots & x_{n}^{n} \end{matrix}]}_{n},

we must show that

\det {[a_{i j}]}_{n} = \prod_{1 \leq i \leq n} x_{i} \prod_{1 \leq j < i \leq n} (x_{i} - x_{j}) .

Let

a_{i j}^{'} = \{\begin{matrix} a_{i 1} & if j = 1 \\ a_{i j} - a_{i 1} & if 2 \leq j \leq n \end{matrix}

and

a_{i j}^{″} = \{\begin{matrix} a_{11}^{'} & if i = 1, j = 1 \\ a_{1 j}^{'} & if i = 1, 2 \leq j \leq n \\ a_{i 1}^{'} - x_{1} a_{(i - 1) 1}^{'} & if 2 \leq i \leq n, j = 1, \\ a_{i j}^{'} - x_{1} a_{(i - 1) j}^{'} & if 2 \leq i \leq n, 2 \leq j \leq n, \end{matrix}

so that $\det [a_{i j}] = \det [a_{i j}^{″}]$ where

a_{i j}^{″} = \{\begin{matrix} x_{1} & if i = 1, j = 1 \\ x_{j} - x_{1} & if i = 1, 2 \leq j \leq n \\ 0 & if 2 \leq i \leq n, j = 1 \\ x_{j}^{i - 1} (x_{j} - x_{1}) & if 2 \leq i \leq n, 2 \leq j \leq n \end{matrix}

since:

\begin{array}{l} a_{11}^{'} & = a_{11} = x_{1} & i = 1, j = 1 \\ a_{1 j}^{'} & = a_{1 j} - a_{11} = x_{j} - x_{1} & i = 1, 2 \leq j \leq n \\ a_{i 1}^{'} & = a_{i 1} = x_{1}^{i} & 2 \leq i \leq n, j = 1 \\ a_{i j}^{'} & = a_{i j} - a_{i 1} = x_{j}^{i} - x_{1}^{i} & 2 \leq i \leq n, 2 \leq j \leq n \\ a_{11}^{″} & = a_{11}^{'} = a_{11} = x_{1} & i = 1, j = 1 \\ a_{1 j}^{″} & = a_{1 j}^{'} = a_{1 j} - a_{11} = x_{j} - x_{1} & i = 1, 2 \leq j \leq n \\ a_{i 1}^{″} & = a_{i 1}^{'} - x_{1} a_{(i - 1) 1}^{'} = a_{i 1} - x_{1} a_{(i - 1) 1}) = 0 & 2 \leq i \leq n, j = 1 \\ a_{i j}^{″} & = a_{i j}^{'} - x_{1} a_{(i - 1) j}^{'} = a_{i j} - a_{i 1} - x_{1} (a_{(i - 1) j} - a_{(i - 1) 1}) = x_{j}^{i - 1} (x_{j} - x_{1}) & 2 \leq i \leq n, 2 \leq j \leq n \end{array}

Let

\begin{array}{l} q_{i j} & = \{\begin{matrix} x_{j + 1} - x_{1} & if i = j, 1 \leq i, j \leq n - 1 \\ 0 & otherwise \end{matrix} \end{array}

so that $minor ({[a^{″}]}_{n}, 1, 1) = {({[q_{i j}]}_{n - 1} minor {({[a]}_{n}, 1, 1)}^{T})}^{T}$ and $\det {[q_{i j}]}_{n - 1} = \prod_{1 \leq k \leq n - 1} (x_{k + 1} - x_{1})$ . Then

\begin{array}{l} \det {[a_{i j}]}_{n} & = \det {[a_{i j}^{″}]}_{n} \\ = \sum_{1 \leq i \leq n} a_{i 1}^{″} cofactor (a_{i 1}^{″}) \\ = a_{11}^{″} cofactor (a_{11}^{″}) + \sum_{2 \leq i \leq n} a_{i 1}^{″} cofactor (a_{i 1}^{″}) \\ = x_{1} {(- 1)}^{1 + 1} \det minor ({[a^{″}]}_{n}, 1, 1) + 0 \\ = x_{1} \det minor ({[a^{″}]}_{n}, 1, 1) \\ = x_{1} \det ({({[q_{i j}]}_{n - 1} minor {({[a]}_{n}, 1, 1)}^{T})}^{T}) \\ = x_{1} \det ({[q_{i j}]}_{n - 1} minor {({[a]}_{n}, 1, 1)}^{T}) \\ = x_{1} \det {[q_{i j}]}_{n - 1} \det (minor {({[a]}_{n}, 1, 1)}^{T}) \\ = x_{1} \det {[q_{i j}]}_{n - 1} \det minor ({[a]}_{n}, 1, 1) \\ = x_{1} (\prod_{1 \leq k \leq n - 1} (x_{k + 1} - x_{1})) \det minor ({[a]}_{n}, 1, 1) . \end{array}

We shall ﬁnally use this recursive identity to give a proof by mathematical induction on $n$ .

If $n = 1$ , then clearly

\det {[a_{i j}]}_{1} = \det {[a_{11}]}_{1} = x_{1} = \prod_{1 \leq i \leq n} x_{i} \prod_{1 \leq j < i \leq 1} (x_{i} - x_{j}) .

Then, assuming that

\det {[a_{i j}]}_{k} = \prod_{1 \leq i \leq k} x_{i} \prod_{1 \leq j < i \leq k} (x_{i} - x_{j})

or equivalently that

\det minor ({[a]}_{k + 1}, 1, 1) = \prod_{2 \leq i \leq k + 1} x_{i} \prod_{2 \leq j < i \leq k + 1} (x_{i} - x_{j})

we must show that

\det {[a_{i j}]}_{k + 1} = \prod_{1 \leq i \leq k + 1} x_{i} \prod_{1 \leq j < i \leq k + 1} (x_{i} - x_{j}) .

But

\begin{array}{l} \det {[a_{i j}]}_{k + 1} & = x_{1} (\prod_{1 \leq i \leq k} (x_{i + 1} - x_{1})) \det {[a_{(i + 1) (j + 1)}]}_{k} \\ = x_{1} (\prod_{1 \leq i \leq k} (x_{i + 1} - x_{1})) (\prod_{2 \leq i \leq k + 1} x_{i} \prod_{2 \leq j < i \leq k + 1} (x_{i} - x_{j})) \\ = (x_{1} \prod_{2 \leq i \leq k + 1} (x_{i} - x_{1})) (\prod_{2 \leq i \leq k + 1} x_{i} \prod_{2 \leq j < i \leq k + 1} (x_{i} - x_{j})) \\ = (\prod_{1 \leq i \leq 1} x_{i} \prod_{1 \leq j < i \leq k + 1} (x_{i} - x_{j})) (\prod_{2 \leq i \leq k + 1} x_{i} \prod_{2 \leq j < i \leq k + 1} (x_{i} - x_{j})) \\ = \prod_{1 \leq i \leq k + 1} x_{i} \prod_{1 \leq j < i \leq k + 1} (x_{i} - x_{j}) \end{array}

as we needed to show. □

Proposition. $\det {[1 ∕ (x_{i} + y_{j})]}_{n} = \prod_{1 \leq i < j \leq n} (x_{j} - x_{i}) (y_{j} - y_{i}) / \prod_{1 \leq i, j \leq n} (x_{i} + y_{j})$ .

Proof. For

A n = {[a_{i j}]}_{n} = {[1 ∕ (x_{i} + y_{i})]}_{n} = {[\begin{matrix} 1 ∕ (x_{1} + y_{1}) & 1 ∕ (x_{1} + y_{2}) & \dots & 1 ∕ (x_{1} + y_{n}) \\ 1 ∕ (x_{2} + y_{1}) & 1 ∕ (x_{2} + y_{2}) & \dots & 1 ∕ (x_{2} + y_{n}) \\ ⋮ & ⋮ & ⋱ & ⋮ \\ 1 ∕ (x_{n} + y_{1}) & 1 ∕ (x_{n} + y_{2}) & \dots & 1 ∕ (x_{n} + y_{n}) \end{matrix}]}_{n},

we must show that

\det {[a_{i j}]}_{n} = \prod_{1 \leq i < j \leq n} (x_{j} - x_{i}) (y_{j} - y_{i}) / \prod_{1 \leq i, j \leq n} (x_{i} + y_{j}) .

Let

a_{i j}^{'} = \{\begin{matrix} a_{i 1} & if j = 1 \\ a_{i j} - a_{i 1} & if 2 \leq j \leq n \end{matrix}

so that $\det [a_{i j}] = \det [a_{i j}^{'}]$ where

a_{i j}^{'} = \{\begin{matrix} 1 ∕ (x_{1} + y_{1}) & if i = 1, j = 1 \\ ((y_{1} - y_{j}) ∕ (x_{1} + y_{1})) (1 ∕ (x_{1} + y_{j})) & if i = 1, 2 \leq j \leq n \\ 1 ∕ (x_{1} + y_{1}) & if 2 \leq i \leq n, j = 1 \\ ((y_{1} - y_{j}) ∕ (x_{i} + y_{1})) (1 ∕ (x_{i} + y_{j})) & if 2 \leq i \leq n, 2 \leq j \leq n \end{matrix}

since:

\begin{array}{l} a_{11}^{'} & = a_{11} = 1 ∕ (x_{1} + y_{1}) & i = 1, j = 1 \\ a_{1 j}^{'} & = a_{1 j} - a_{11} = ((y_{1} - y_{j}) ∕ (x_{1} + y_{1})) (1 ∕ (x_{1} + y_{j})) & i = 1, 2 \leq j \leq n \\ a_{i 1}^{'} & = a_{i 1} = 1 ∕ (x_{i} + y_{1}) & 2 \leq i \leq n, j = 1 \\ a_{i j}^{'} & = a_{i j} - a_{i 1} = ((y_{1} - y_{j}) ∕ (x_{i} + y_{1})) (1 ∕ (x_{i} + y_{j})) & 2 \leq i \leq n, 2 \leq j \leq n \end{array}

Let

\begin{array}{l} b_{i j} & = \{\begin{matrix} 1 & if j = 1 \\ 1 ∕ (x_{i} + y_{j}) & otherwise, \end{matrix} \end{array}

\begin{array}{l} p_{i j} & = \{\begin{matrix} 1 ∕ (x_{i} + y_{1}) & if i = j, 1 \leq i, j \leq n \\ 0 & otherwise, \end{matrix} \end{array}

and

\begin{array}{l} q_{i j} & = \{\begin{matrix} 1 & if i = j = 1 \\ y_{1} - y_{j} & if i = j, 2 \leq i, j \leq n \\ 0 & otherwise \end{matrix} \end{array}

so that

{[a_{i j}^{'}]}_{n} = {({[q_{i j}]}_{n} {({[p_{i j}]}_{n} {[b_{i j}]}_{n})}^{T})}^{T}

and:

\begin{matrix} \det {[p_{i j}]}_{n} = \prod_{1 \leq k \leq n} \frac{1}{x_{k} + y_{1}} \\ \det {[q_{i j}]}_{n} = \prod_{2 \leq k \leq n} y_{1} - y_{k} \end{matrix}

Also let

b_{i j}^{'} = \{\begin{matrix} b_{1 j} & if i = 1 \\ b_{i j} - b_{1 j} & if 2 \leq i \leq n \end{matrix}

so that $\det [b_{i j}] = \det [b_{i j}^{'}]$ where

b_{i j}^{'} = \{\begin{matrix} 1 & if i = 1, j = 1 \\ 1 ∕ (x_{i} + y_{j}) & if i = 1, 2 \leq j \leq n \\ 0 & if 2 \leq i \leq n, j = 1 \\ ((x_{1} - x_{i}) ∕ (x_{1} + y_{j})) (1 ∕ (x_{i} + y_{j})) & if 2 \leq i \leq n, 2 \leq j \leq n \end{matrix}

since:

\begin{array}{l} b_{11}^{'} & = b_{11} = 1 & i = 1, j = 1 \\ b_{1 j}^{'} & = b_{1 j} = 1 ∕ (x_{i} + y_{j}) & i = 1, 2 \leq j \leq n \\ b_{i 1}^{'} & = b_{i 1} - b_{11} = 0 & 2 \leq i \leq n, j = 1 \\ b_{i j}^{'} & = b_{i j} - b_{1 j} = ((x_{1} - x_{i}) ∕ (x_{1} + y_{j})) (1 ∕ (x_{i} + y_{j})) & 2 \leq i \leq n, 2 \leq j \leq n \end{array}

Also let

\begin{array}{l} r_{i j} & = \{\begin{matrix} 1 & if i = j = 1 \\ x_{1} - x_{i} & if i = j, 2 \leq i, j \leq n \\ 0 & otherwise \end{matrix} \end{array}

and

\begin{array}{l} s_{i j} & = \{\begin{matrix} 1 & if i = j = 1 \\ 1 ∕ (x_{1} + y_{j}) & if i = j, 2 \leq i, j \leq n \\ 0 & otherwise \end{matrix} \end{array}

so that

minor ({[b^{'}]}_{n}, 1, 1) = {({[s_{i j}]}_{n - 1} {({[r_{i j}]}_{n - 1} minor ({[a]}_{n}, 1, 1))}^{T})}^{T}

and:

\begin{matrix} \det {[r_{i j}]}_{n - 1} = \prod_{2 \leq k \leq n} x_{1} - x_{k} \\ \det {[s_{i j}]}_{n - 1} = \prod_{2 \leq k \leq n} \frac{1}{x_{1} + y_{j}} \end{matrix}

Then

\begin{array}{l} \det [a_{i j}] & = \det {[a_{i j}^{″}]}_{n} \\ = \det ({({[q_{i j}]}_{n} {({[p_{i j}]}_{n} {[b_{i j}]}_{n})}^{T})}^{T}) \\ = \det ({[q_{i j}]}_{n}) \det ({[p_{i j}]}_{n} {[b_{i j}]}_{n}) \\ = \det ({[q_{i j}]}_{n}) \det ({[p_{i j}]}_{n}) \det ({[b_{i j}]}_{n}) \\ = (\prod_{2 \leq k \leq n} y_{1} - y_{k}) \det ({[p_{i j}]}_{n}) \det ({[b_{i j}]}_{n}) \\ = (\prod_{2 \leq k \leq n} y_{1} - y_{k}) (\prod_{1 \leq k \leq n} \frac{1}{x_{k} + y_{1}}) \det ({[b_{i j}]}_{n}) \\ = (\prod_{2 \leq k \leq n} y_{1} - y_{k}) (\prod_{1 \leq k \leq n} \frac{1}{x_{k} + y_{1}}) \det ({[b_{i j}^{'}]}_{n}) \\ = (\prod_{2 \leq k \leq n} y_{1} - y_{k}) (\prod_{1 \leq k \leq n} \frac{1}{x_{k} + y_{1}}) (b_{11}^{'} cofactor (b_{11}^{'}) + \sum_{2 \leq i \leq n} b_{i 1}^{'} cofactor (b_{i 1}^{'})) \\ = (\prod_{2 \leq k \leq n} y_{1} - y_{k}) (\prod_{1 \leq k \leq n} \frac{1}{x_{k} + y_{1}}) (b_{11}^{'} cofactor (b_{11}^{'}) + 0) \\ = (\prod_{2 \leq k \leq n} y_{1} - y_{k}) (\prod_{1 \leq k \leq n} \frac{1}{x_{k} + y_{1}}) (\det (minor ({[b^{'}]}_{n}, 1, 1)) + 0) \\ = (\prod_{2 \leq k \leq n} y_{1} - y_{k}) (\prod_{1 \leq k \leq n} \frac{1}{x_{k} + y_{1}}) \det ({({[s_{i j}]}_{n - 1} {({[r_{i j}]}_{n - 1} minor ({[a]}_{n}, 1, 1))}^{T})}^{T}) \\ = (\prod_{2 \leq k \leq n} y_{1} - y_{k}) (\prod_{1 \leq k \leq n} \frac{1}{x_{k} + y_{1}}) \det ({[s_{i j}]}_{n - 1}) \det ({[r_{i j}]}_{n - 1} minor ({[a]}_{n}, 1, 1)) \\ = (\prod_{2 \leq k \leq n} y_{1} - y_{k}) (\prod_{1 \leq k \leq n} \frac{1}{x_{k} + y_{1}}) \det ({[s_{i j}]}_{n - 1}) \det ({[r_{i j}]}_{n - 1}) \det (minor ({[a]}_{n}, 1, 1)) \\ = (\prod_{2 \leq k \leq n} y_{1} - y_{k}) (\prod_{1 \leq k \leq n} \frac{1}{x_{k} + y_{1}}) (\prod_{2 \leq k \leq n} \frac{1}{x_{1} + y_{j}}) \det ({[r_{i j}]}_{n - 1}) \det (minor ({[a]}_{n}, 1, 1)) \\ = (\prod_{2 \leq k \leq n} y_{1} - y_{k}) (\prod_{1 \leq k \leq n} \frac{1}{x_{k} + y_{1}}) (\prod_{2 \leq k \leq n} \frac{1}{x_{1} + y_{j}}) (\prod_{2 \leq k \leq n} x_{1} - x_{k}) \det (minor ({[a]}_{n}, 1, 1)) \\ = \frac{\prod_{2 \leq i \leq n} (x_{i} - x_{1}) (y_{i} - y_{1})}{\prod_{1 \leq i, j \leq n} (x_{i} + y_{1}) (x_{1} + y_{j})} \det (minor ({[a]}_{n}, 1, 1)) . \end{array}

We shall ﬁnally use this recursive identity to give a proof by mathematical induction on $n$ .

If $n = 1$ , then clearly

\det {[a_{i j}]}_{1} = \det {[a_{11}]}_{1} = 1 ∕ (x_{1} + y_{1}) = \prod_{1 \leq i < j \leq 1} (x_{j} - x_{i}) (y_{j} - y_{i}) / \prod_{1 \leq i, j \leq 1} (x_{i} + y_{j}) .

Then, assuming that

\det {[a_{i j}]}_{k} = \prod_{1 \leq i < j \leq k} (x_{j} - x_{i}) (y_{j} - y_{i}) / \prod_{1 \leq i, j \leq k} (x_{i} + y_{j})

or equivalently that

\det minor ({[a]}_{k + 1}, 1, 1) = \prod_{2 \leq i < j \leq k + 1} (x_{j} - x_{i}) (y_{j} - y_{i}) / \prod_{2 \leq i, j \leq k + 1} (x_{i} + y_{j})

we must show that

\det {[a_{i j}]}_{k + 1} = \prod_{1 \leq i < j \leq k + 1} (x_{j} - x_{i}) (y_{j} - y_{i}) / \prod_{1 \leq i, j \leq k + 1} (x_{i} + y_{j}) .

But

\begin{array}{l} \det {[a_{i j}]}_{k + 1} & = \frac{\prod_{2 \leq i \leq k + 1} (x_{i} - x_{1}) (y_{i} - y_{1})}{\prod_{1 \leq i, j \leq k + 1} (x_{i} + y_{1}) (x_{1} + y_{j})} \det minor ({[a]}_{k + 1}, 1, 1) \\ = \frac{\prod_{2 \leq i \leq k + 1} (x_{i} - x_{1}) (y_{i} - y_{1})}{\prod_{1 \leq i, j \leq k + 1} (x_{i} + y_{1}) (x_{1} + y_{j})} \frac{\prod_{2 \leq i < j \leq k + 1} (x_{j} - x_{i}) (y_{j} - y_{i})}{\prod_{2 \leq i, j \leq k + 1} (x_{i} + y_{j})} \\ = \frac{(\prod_{2 \leq j \leq k + 1} (x_{j} - x_{1}) (y_{j} - y_{1})) (\prod_{2 \leq i < j \leq k + 1} (x_{j} - x_{i}) (y_{j} - y_{i}))}{(\prod_{1 \leq i, j \leq k + 1} (x_{i} + y_{1}) (x_{1} + y_{j})) (\prod_{2 \leq i, j \leq k + 1} (x_{i} + y_{j}))} \\ = \frac{(\prod_{1 \leq i < j \leq k + 1} (x_{j} - x_{i}) (y_{j} - y_{i})) (\prod_{2 \leq i < j \leq k + 1} (x_{j} - x_{i}) (y_{j} - y_{i}))}{(\prod_{1 \leq i, j \leq k + 1} (x_{i} + y_{1}) (x_{1} + y_{j})) (\prod_{2 \leq i, j \leq k + 1} (x_{i} + y_{j}))} \\ = \prod_{1 \leq i < j \leq k + 1} (x_{j} - x_{i}) (y_{j} - y_{i}) / \prod_{1 \leq i, j \leq k + 1} (x_{i} + y_{j}) \end{array}

as we needed to show. □

39. [M23] Show that the inverse of a combinatorial matrix is a combinatorial matrix with the entries

b_{i j} = (- y + δ_{i j} (x + n y)) ∕ x (x + n y)

Proposition. ${[y + δ_{i j} x]}_{n}^{- 1} = {[\frac{- y + δ_{i j} (x + n y)}{x (x + n y)}]}_{n}$ .

Proof. For

A n = {[a_{i j}]}_{n} = {[y + δ_{i j} x]}_{n} = {[\begin{matrix} y + x & y & \dots & y \\ y & y + x & \dots & y \\ ⋮ & ⋮ & ⋱ & ⋮ \\ y & y & \dots & y + x \end{matrix}]}_{n},

we must show that

{[a_{i j}]}_{n}^{- 1} = {[\frac{- y + δ_{i j} (x + n y)}{x (x + n y)}]}_{n} .

Let $I n = {[δ_{i j}]}_{n}$ and $J n = {[1]}_{n}$ so that $A n = y J n + x I n$ , and note that $J n 2 = n J n$ . Then

\begin{array}{l} A n (- y J n + x I n) & = x^{2} I n - n y^{2} J n & \Leftrightarrow \\ A n (- y J n + x I n) + n y^{2} J n & = x^{2} I n & \Leftrightarrow \\ A n (- y J n + x I n) + n y I n y J n & = x^{2} I n & \Leftrightarrow \\ A n (- y J n + x I n) + n y I n y J n + x n y I n & = x^{2} I n + x n y I n & \Leftrightarrow \\ A n (- y J n + x I n) + n y I n (y J n + x I n) & = x^{2} I n + x n y I n & \Leftrightarrow \\ A n (- y J n + x I n) + n y I n A n & = x (x + n y) I n & \Leftrightarrow \\ A n (- y J n + x I n + n y I n) & = x (x + n y) I n & \Leftrightarrow \\ A n ((x + n y) I n - y J n) & = x (x + n y) I n & \Leftrightarrow \\ A n (\frac{(x + n y) I}{n} n x (x + n y)) & = I n . \end{array}

That is, for

\begin{array}{l} B n & = \frac{(x + n y) I}{n} \\ = \frac{(x + n y) {[δ_{i j}]}_{n} - y {[1]}_{n}}{x (x + n y)} \\ = {[\frac{(x + n y) δ_{i j} - y}{x (x + n y)}]}_{n} \\ = {[\frac{- y + δ_{i j} (x + n y)}{x (x + n y)}]}_{n}, \end{array}

$A n B n = I n$ , or equivalently, that

A n - 1 = {[\frac{- y + δ_{i j} (x + n y)}{x (x + n y)}]}_{n}

as we needed to show. □

Don’t be dismayed by the complicated sum in the numerator—it is just the coeﬃcient of

x^{j - 1}

in the polynomial

(x_{1} - x) \dots (x_{n} - x) ∕ (x_{i} - x)

Proposition. ${[x_{j}^{i}]}_{n}^{- 1} = [(\sum_{\begin{array}{c} 1 \leq k_{1} < \dots < k_{n - j} \leq n \\ k_{1}, \dots, k_{n - j} \neq i \end{array}} {(- 1)}^{j - 1} x_{k_{1}} \dots x_{k_{n - j}}) / x_{i} \prod_{\begin{array}{c} 1 \leq k \leq n \\ k \neq i \end{array}} (x_{k} - x_{i})]$ .

Proof. Let

A n = {[a_{i j}]}_{n} = {[x_{j}^{i}]}_{n} = {[\begin{matrix} x_{1} & x_{2} & \dots & x_{n} \\ x_{1}^{2} & x_{2}^{2} & \dots & x_{n}^{2} \\ ⋮ & ⋮ & ⋱ & ⋮ \\ x_{1}^{n} & x_{2}^{n} & \dots & x_{n}^{n} \end{matrix}]}_{n} .

We must show that

{[a_{i j}]}_{n}^{- 1} = {[\sum_{\begin{array}{c} 1 \leq k_{1} < \dots < k_{n - j} \leq n \\ k_{1}, \dots, k_{n - j} \neq i \end{array}} {(- 1)}^{j - 1} x_{k_{1}} \dots x_{k_{n - j}} / x_{i} \prod_{\begin{array}{c} 1 \leq k \leq n \\ k \neq i \end{array}} (x_{k} - x_{i})]}_{n} .

Let ${[b_{i j}]}_{n} = {[a_{i j}]}_{n}^{- 1}$ , so that by the deﬁnition of inverse and matrix multiplication, we have

{[b_{i j}]}_{n} {[a_{i j}]}_{n} = {[\sum_{1 \leq k \leq n} b_{i k} a_{k j}]}_{n} = {[\sum_{1 \leq k \leq n} b_{i k} x_{j}^{k}]}_{n} = {[δ_{i j}]}_{n} .

We require

\sum_{1 \leq k \leq n} b_{i k} x_{j}^{k} = δ_{i j},

or equivalently, given a polynomial $P_{i} (x) = \sum_{1 \leq k \leq n} b_{i k} x^{k}$ for arbitrary $x$ , we require

P_{i} (x) = δ_{i j}

with given data points $(δ_{i 1}, x_{1}), (δ_{i 2}, x_{2}), \dots, (δ_{i n}, x_{n})$ . By polynomial interpolation, expanding the polynomial to an initial but trivial $(n + 1)$ th variable $x_{0} = 0$ , with $b_{i 0} = b_{0 j} = 0$ , in order to obtain a complete set of diﬀerences, we have

\begin{array}{l} P_{i} (x) & = \sum_{0 \leq k \leq n} (δ_{i k} \prod_{\begin{array}{c} 0 \leq m \leq n \\ m \neq k \end{array}} \frac{x - x_{m}}{x_{k} - x_{m}}) \\ = \sum_{\begin{array}{c} 0 \leq k \leq n \\ k = i \end{array}} (δ_{i k} \prod_{\begin{array}{c} 0 \leq m \leq n \\ m \neq k \end{array}} \frac{x - x_{m}}{x_{k} - x_{m}}) + \sum_{\begin{array}{c} 0 \leq k \leq n \\ k \neq i \end{array}} (δ_{i k} \prod_{\begin{array}{c} 0 \leq m \leq n \\ m \neq k \end{array}} \frac{x - x_{m}}{x_{k} - x_{m}}) \\ = δ_{i i} \prod_{\begin{array}{c} 0 \leq m \leq n \\ m \neq i \end{array}} \frac{x - x_{m}}{x_{i} - x_{m}} + 0 \\ = \prod_{\begin{array}{c} 0 \leq k \leq n \\ k \neq i \end{array}} \frac{x - x_{k}}{x_{i} - x_{k}} \\ = \frac{x - x_{0}}{x_{i} - x_{0}} \prod_{\begin{array}{c} 1 \leq k \leq n \\ k \neq i \end{array}} \frac{x - x_{k}}{x_{i} - x_{k}} \\ = \frac{x}{x_{i}} \prod_{\begin{array}{c} 1 \leq k \leq n \\ k \neq i \end{array}} \frac{x_{k} - x}{x_{k} - x_{i}} . \end{array}

For $x = x_{j}$ , we have

\sum_{1 \leq k \leq n} b_{i k} x_{j}^{k} = P_{i} (x_{j}) = \frac{x_{j}}{x_{i}} \prod_{\begin{array}{c} 1 \leq k \leq n \\ k \neq i \end{array}} \frac{x_{k} - x_{j}}{x_{k} - x_{i}} = δ_{i j} .

What is left is to ﬁnd the coeﬃcients $b_{i j}$ . By de Moivre’s work¹ , we may do so.

The real and diﬀerent roots of $P_{i} (x)$ are exactly those $x_{r}$ where $r \neq i$ , since in such a case, we have

P_{i} (x_{r}) = \frac{x_{r}}{x_{i}} \prod_{\begin{array}{c} 1 \leq k \leq n \\ k \neq i \end{array}} \frac{x_{k} - x_{r}}{x_{k} - x_{i}} = (x_{r} - x_{r}) \frac{x_{r}}{x_{i}} \prod_{\begin{array}{c} 1 \leq k \leq n \\ k \neq i \\ k \neq r \end{array}} \frac{x_{k} - x_{r}}{x_{k} - x_{i}} = 0 .

Let these roots be denoted by $x_{r_{1}}, x_{r_{2}}, \dots, x_{r_{n}}$ .

Since matrix multiplication with inverse is commutative, We also have

\sum_{1 \leq k \leq n} b_{i k} x_{j}^{k} = \sum_{1 \leq k \leq n} x_{k}^{i} b_{k j} = δ_{i j} .

By de Moivre’s identities, with our trivially expanded polynomial,

\begin{matrix} δ_{i j} = \sum_{0 \leq k \leq n} x_{k}^{i} b_{k j} \\ \Leftrightarrow \\ b_{k j} = \sum_{1 \leq m \leq n} {(- 1)}^{m} \sum_{\begin{array}{c} 1 \leq r_{1} < \dots < r_{m} \leq n \\ r_{1}, \dots, r_{m} \neq i \end{array}} x_{r_{1}} \dots x_{r_{m}} δ_{(n - m) j} / x_{k} \prod_{\begin{array}{c} 1 \leq m \leq n \\ m \neq k \end{array}} (x_{k} - x_{m}) \end{matrix}

we then have, since $δ_{(n - k) j}$ requires $j = n - k$ and since $n - j$ and $j - 1$ have opposite parity, that

\begin{array}{l} b_{i j} & = \sum_{1 \leq k \leq n} {(- 1)}^{k} \sum_{\begin{array}{c} 1 \leq r_{1} < \dots < r_{k} \leq n \\ r_{1}, \dots, r_{k} \neq i \end{array}} x_{r_{1}} \dots x_{r_{k}} δ_{(n - k) j} / x_{i} \prod_{\begin{array}{c} 1 \leq k \leq n \\ k \neq i \end{array}} (x_{i} - x_{k}) \\ = {(- 1)}^{n - j} \sum_{\begin{array}{c} 1 \leq r_{1} < \dots < r_{n - j} \leq n \\ r_{1}, \dots, r_{n - j} \neq i \end{array}} x_{r_{1}} \dots x_{r_{n - j}} / x_{i} \prod_{\begin{array}{c} 1 \leq k \leq n \\ k \neq i \end{array}} (x_{i} - x_{k}) \\ = (- 1) {(- 1)}^{j - 1} \sum_{\begin{array}{c} 1 \leq r_{1} < \dots < r_{n - j} \leq n \\ r_{1}, \dots, r_{n - j} \neq i \end{array}} x_{r_{1}} \dots x_{r_{n - j}} / (- 1) x_{i} \prod_{\begin{array}{c} 1 \leq k \leq n \\ k \neq i \end{array}} (x_{k} - x_{i}) \\ = \sum_{\begin{array}{c} 1 \leq r_{1} < \dots < r_{n - j} \leq n \\ r_{1}, \dots, r_{n - j} \neq i \end{array}} {(- 1)}^{j - 1} x_{r_{1}} \dots x_{r_{n - j}} / x_{i} \prod_{\begin{array}{c} 1 \leq k \leq n \\ k \neq i \end{array}} (x_{k} - x_{i}) . \end{array}

Therefore

{[a_{i j}]}_{n}^{- 1} = {[\sum_{\begin{array}{c} 1 \leq k_{1} < \dots < k_{n - j} \leq n \\ k_{1}, \dots, k_{n - j} \neq i \end{array}} {(- 1)}^{j - 1} x_{k_{1}} \dots x_{k_{n - j}} / x_{i} \prod_{\begin{array}{c} 1 \leq k \leq n \\ k \neq i \end{array}} (x_{k} - x_{i})]}_{n}

as we needed to show. □

______________________________________________________________________________________________________________________________

[A. de Moivre, The Doctrine of Chances, 2nd edition (London: 1738), 197–199.]

Let

A n = {[a_{i j}]}_{n} = {[1 ∕ (x_{i} + y_{i})]}_{n} = {[\begin{matrix} 1 ∕ (x_{1} + y_{1}) & 1 ∕ (x_{1} + y_{2}) & \dots & 1 ∕ (x_{1} + y_{n}) \\ 1 ∕ (x_{2} + y_{1}) & 1 ∕ (x_{2} + y_{2}) & \dots & 1 ∕ (x_{2} + y_{n}) \\ ⋮ & ⋮ & ⋱ & ⋮ \\ 1 ∕ (x_{n} + y_{1}) & 1 ∕ (x_{n} + y_{2}) & \dots & 1 ∕ (x_{n} + y_{n}) \end{matrix}]}_{n},

We must show that

{[a_{i j}]}_{n}^{- 1} = {[(\prod_{1 \leq k \leq n} (x_{j} + y_{k}) (x_{k} + y_{i})) / (x_{j} + y_{i}) (\prod_{\begin{array}{c} 1 \leq k \leq n \\ k \neq j \end{array}} (x_{j} - x_{k})) (\prod_{\begin{array}{c} 1 \leq k \leq n \\ k \neq i \end{array}} (y_{i} - y_{k}))]}_{n} .

But, by the deﬁnition of inverse,

\begin{array}{l} {[a_{i j}]}_{n}^{- 1} & = \frac{{[cofactor (a_{i j})]}_{n}^{T}}{\det {[a_{i j}]}_{n}} \\ = \frac{{[cofactor (a_{j i})]}_{n}}{\prod_{1 \leq u < v \leq n} (x_{v} - x_{u}) (y_{v} - y_{u}) / \prod_{1 \leq u, v \leq n} (x_{u} + y_{v})} \\ = \frac{{(- 1)}^{j + i} \det minor ({[a]}_{n}, j, i)}{\prod_{1 \leq u < v \leq n} (x_{v} - x_{u}) (y_{v} - y_{u}) / \prod_{1 \leq u, v \leq n} (x_{u} + y_{v})} \\ = \frac{{(- 1)}^{j + i} \prod_{\begin{array}{c} 1 \leq u < v \leq n \\ u \neq j, u \neq i \\ v \neq j, v \neq i \end{array}} (x_{v} - x_{u}) (y_{v} - y_{u}) / \prod_{\begin{array}{c} 1 \leq u, v \leq n \\ u \neq j \\ v \neq i \end{array}} (x_{u} + y_{v})}{\prod_{1 \leq u < v \leq n} (x_{v} - x_{u}) (y_{v} - y_{u}) / \prod_{1 \leq u, v \leq n} (x_{u} + y_{v})} \\ = \frac{{(- 1)}^{j + i} (\prod_{\begin{array}{c} 1 \leq u < v \leq n \\ u \neq j \\ v \neq j \end{array}} (x_{u} - x_{v})) (\prod_{\begin{array}{c} 1 \leq u < v \leq n \\ u \neq i \\ v \neq i \end{array}} (y_{u} - y_{v})) / \prod_{\begin{array}{c} 1 \leq u, v \leq n \\ u \neq j \\ v \neq i \end{array}} (x_{u} + y_{v})}{(\prod_{1 \leq u < v \leq n} (x_{u} - x_{v})) (\prod_{1 \leq u < v \leq n} (y_{u} - y_{v})) / \prod_{1 \leq u, v \leq n} (x_{u} + y_{v})} \\ = {(- 1)}^{j + i} \frac{\prod_{1 \leq u, v \leq n} (x_{u} + y_{v})}{\prod_{\begin{array}{c} 1 \leq u, v \leq n \\ u \neq j \\ v \neq i \end{array}} (x_{u} + y_{v})} \frac{\prod_{\begin{array}{c} 1 \leq u < v \leq n \\ u \neq j \\ v \neq j \end{array}} (x_{u} - x_{v})}{\prod_{1 \leq u < v \leq n} (x_{u} - x_{v})} \frac{\prod_{\begin{array}{c} 1 \leq u < v \leq n \\ u \neq i \\ v \neq i \end{array}} (y_{u} - y_{v})}{\prod_{1 \leq u < v \leq n} (y_{u} - y_{v})} \\ = {(- 1)}^{j + i} \prod_{\begin{array}{c} 1 \leq u, v \leq n \\ u = j \lor v = i \end{array}} (x_{u} + y_{v}) \frac{1}{\prod_{\begin{array}{c} 1 \leq u < v \leq n \\ u = j \lor v = j \end{array}} (x_{u} - x_{v})} \frac{1}{\prod_{\begin{array}{c} 1 \leq u < v \leq n \\ u = i \lor v = i \end{array}} (y_{u} - y_{v})} \\ \begin{aligned} = {(- 1)}^{j + i} (x_{j} + y_{i}) \prod_{\begin{array}{c} 1 \leq u \leq n \\ u \neq j \end{array}} (x_{u} + y_{i}) \prod_{\begin{array}{c} 1 \leq v \leq n \\ v \neq i \end{array}} (x_{j} + y_{v}) \\ \frac{1}{(\prod_{1 \leq u \leq j - 1} (x_{u} - x_{j})) (\prod_{j + 1 \leq v \leq n} (x_{j} - x_{v}))} \frac{1}{(\prod_{1 \leq u \leq i - 1} (y_{u} - y_{i})) (\prod_{i + 1 \leq v \leq n} (y_{i} - y_{v}))} \end{aligned} \\ = {(- 1)}^{j + i} (x_{j} + y_{i}) \prod_{\begin{array}{c} 1 \leq u \leq n \\ u \neq j \end{array}} (x_{u} + y_{i}) \prod_{\begin{array}{c} 1 \leq v \leq n \\ v \neq i \end{array}} (x_{j} + y_{v}) \frac{{(- 1)}^{j - 1}}{\prod_{\begin{array}{c} 1 \leq u \leq n \\ u \neq j \end{array}} (x_{j} - x_{u})} \frac{{(- 1)}^{i - 1}}{\prod_{\begin{array}{c} 1 \leq v \leq n \\ v \neq i \end{array}} (y_{i} - y_{v})} \\ = {(- 1)}^{2 (j + i - 1)} (x_{j} + y_{i}) \frac{\prod_{\begin{array}{c} 1 \leq u \leq n \\ u \neq j \end{array}} (x_{u} + y_{i})}{\prod_{\begin{array}{c} 1 \leq u \leq n \\ u \neq j \end{array}} (x_{j} - x_{u})} \frac{\prod_{\begin{array}{c} 1 \leq v \leq n \\ v \neq i \end{array}} (x_{j} + y_{v})}{\prod_{\begin{array}{c} 1 \leq v \leq n \\ v \neq i \end{array}} (y_{i} - y_{v})} \\ = \frac{{(x_{j} + y_{i})}^{2} (\prod_{\begin{array}{c} 1 \leq u \leq n \\ u \neq j \end{array}} (x_{u} + y_{i})) (\prod_{\begin{array}{c} 1 \leq v \leq n \\ v \neq i \end{array}} (x_{j} + y_{v}))}{(x_{j} + y_{i}) (\prod_{\begin{array}{c} 1 \leq u \leq n \\ u \neq j \end{array}} (x_{j} - x_{u})) (\prod_{\begin{array}{c} 1 \leq v \leq n \\ v \neq i \end{array}} (y_{i} - y_{v}))} \\ = \frac{(\prod_{1 \leq u \leq n} (x_{u} + y_{i})) (\prod_{1 \leq v \leq n} (x_{j} + y_{v}))}{(x_{j} + y_{i}) (\prod_{\begin{array}{c} 1 \leq u \leq n \\ u \neq j \end{array}} (x_{j} - x_{u})) (\prod_{\begin{array}{c} 1 \leq v \leq n \\ v \neq i \end{array}} (y_{i} - y_{v}))} \\ = \frac{\prod_{1 \leq k \leq n} (x_{j} + y_{k}) (x_{k} + y_{i})}{(x_{j} + y_{i}) (\prod_{\begin{array}{c} 1 \leq k \leq n \\ k \neq j \end{array}} (x_{j} - x_{k})) (\prod_{\begin{array}{c} 1 \leq k \leq n \\ k \neq i \end{array}} (y_{i} - y_{k}))} \end{array}

as we needed to show.

42. [M18] What is the sum of all

n^{2}

elements in the inverse of the combinatorial matrix?

For the inverse of the combinatorial matrix

{[\frac{1}{y + δ_{i j} x}]}_{n}^{- 1} = {[\frac{- y + δ_{i j} (x + n y)}{x (x + n y)}]}_{n}

the sum of all $n^{2}$ elements is simply

\begin{array}{l} \sum_{1 \leq i \leq n} \sum_{1 \leq j \leq n} \frac{- y + δ_{i j} (x + n y)}{x (x + n y)} & = \sum_{1 \leq i \leq n} \frac{(\sum_{\begin{array}{c} 1 \leq j \leq n \\ j \neq i \end{array}} - y) - y + x + n y}{x (x + n y)} \\ = \sum_{1 \leq i \leq n} \frac{- y (n - 1) - y + x + n y}{x (x + n y)} \\ = \sum_{1 \leq i \leq n} \frac{- n y + y - y + x + n y}{x (x + n y)} \\ = \sum_{1 \leq i \leq n} \frac{x}{x (x + n y)} \\ = \sum_{1 \leq i \leq n} \frac{1}{x + n y} \\ = \frac{n}{x + n y} . \end{array}

43. [M24] What is the sum of all

n^{2}

elements in the inverse of Vandermonde’s matrix? [Hint: Use exercise 33.]

For the inverse of the Vandermonde matrix

{[x_{j}^{i}]}_{n}^{- 1} = {[(\sum_{\begin{array}{c} 1 \leq k_{1} < \dots < k_{n - j} \leq n \\ k_{1}, \dots, k_{n - j} \neq i \end{array}} x_{k_{1}} \dots x_{k_{n - j}}) / x_{i} \prod_{\begin{array}{c} 1 \leq k \leq n \\ k \neq i \end{array}} (x_{k} - x_{i})]}_{n} = {[b_{i j}]}_{n},

we want to ﬁnd the sum of all $n^{2}$ elements $\sum_{1 \leq i, j \leq n} b_{i j}$ .

In the case that any $x_{κ} = 1$ , $1 \leq κ \leq n$ , from exercise 40, we have that

{[b_{i j}]}_{n} {[x_{j}^{i}]}_{n} = {[\sum_{1 \leq k \leq n} b_{i k} x_{j}^{k}]}_{n} = {[δ_{i j}]}_{n}

or equivalently that

\begin{array}{l} \sum_{1 \leq j \leq n} b_{i j} = δ_{i κ} \\ \Rightarrow \sum_{1 \leq i \leq n} \sum_{1 \leq j \leq n} b_{i j} = 1 \\ \Rightarrow \sum_{1 \leq i, j \leq n} b_{i j} = 1 - (1 - 1 ∕ x_{κ}) \\ \Rightarrow \sum_{1 \leq i, j \leq n} b_{i j} = 1 - \prod_{1 \leq k \leq n} (1 - 1 ∕ x_{k}) . \end{array}

Otherwise, in the case that $x_{κ} \neq 1$ , $1 \leq κ \leq n$ , again from exercise 40, given $P_{i} (x) = \sum_{1 \leq k \leq n} b_{i k} x^{k}$ for $x = 1$ we have that

\sum_{1 \leq i, j \leq n} b_{i j} = \sum_{1 \leq i \leq n} P_{i} (x) = \sum_{1 \leq i \leq n} \frac{x}{x_{i}} \prod_{\begin{array}{c} 1 \leq k \leq n \\ k \neq i \end{array}} \frac{x_{k} - x}{x_{k} - x_{i}}

or equivalently, for $x = 1$ , that

\begin{array}{l} \sum_{1 \leq i \leq n} P_{i} (1) & = \sum_{1 \leq i \leq n} (\frac{1}{x_{i}} \prod_{\begin{array}{c} 1 \leq k \leq n \\ k \neq i \end{array}} \frac{x_{k} - 1}{x_{k} - x_{i}}) \\ = \sum_{1 \leq i \leq n} (\frac{x_{i} - 1}{x_{i} - 1} \frac{1}{x_{i}} \prod_{\begin{array}{c} 1 \leq k \leq n \\ k \neq i \end{array}} \frac{x_{k} - 1}{x_{k} - x_{i}}) \\ = \sum_{1 \leq i \leq n} \frac{(x_{i} - 1) \prod_{\begin{array}{c} 1 \leq k \leq n \\ k \neq i \end{array}} (x_{k} - 1)}{x_{i} (x_{i} - 1) \prod_{\begin{array}{c} 1 \leq k \leq n \\ k \neq i \end{array}} (x_{k} - x_{i})} \\ = \sum_{1 \leq i \leq n} \frac{\prod_{1 \leq k \leq n} (x_{k} - 1)}{x_{i} (x_{i} - 1) \prod_{\begin{array}{c} 1 \leq k \leq n \\ k \neq i \end{array}} (x_{k} - x_{i})} \\ = \prod_{1 \leq k \leq n} (x_{k} - 1) \sum_{1 \leq i \leq n} \frac{1}{x_{i} (x_{i} - 1) \prod_{\begin{array}{c} 1 \leq k \leq n \\ k \neq i \end{array}} (x_{k} - x_{i})} \\ = \prod_{1 \leq k \leq n} (1 - x_{k}) \sum_{1 \leq i \leq n} \frac{1}{x_{i} (x_{i} - 1) \prod_{\begin{array}{c} 1 \leq k \leq n \\ k \neq i \end{array}} (x_{i} - x_{k})} \\ = \prod_{1 \leq k \leq n} (x_{k} - 1) (\sum_{1 \leq i \leq n} \frac{1}{x_{i} \prod_{\begin{array}{c} 1 \leq k \leq n \\ k \neq i \end{array}} (x_{i} - x_{k})} - \sum_{1 \leq i \leq n} \frac{1}{(x_{i} - 1) \prod_{\begin{array}{c} 1 \leq k \leq n \\ k \neq i \end{array}} (x_{i} - x_{k})}) . \end{array}

Also, from exercise 33, we have for an extrapolated and distinct $x_{0} = 1$ and for $r = 0$ that

\sum_{0 \leq i \leq n} (\frac{1}{\prod_{\begin{array}{c} 0 \leq j \leq n \\ j \neq i \end{array}} (x_{i} - x_{j})}) = \frac{1}{\prod_{1 \leq j \leq n} (1 - x_{j})} + \sum_{1 \leq i \leq n} (\frac{1}{(x_{i} - 1) \prod_{\begin{array}{c} 1 \leq j \leq n \\ j \neq i \end{array}} (x_{i} - x_{j})}) = 1

or equivalently that

\sum_{1 \leq i \leq n} (\frac{1}{(x_{i} - 1) \prod_{\begin{array}{c} 1 \leq j \leq n \\ j \neq i \end{array}} (x_{i} - x_{j})}) = 1 - \frac{1}{\prod_{1 \leq j \leq n} (1 - x_{j})} .

Similarly, if $x_{0} = 0$

\sum_{1 \leq i \leq n} (\frac{1}{x_{i} \prod_{\begin{array}{c} 1 \leq j \leq n \\ j \neq i \end{array}} (x_{i} - x_{j})}) = 1 - \frac{1}{\prod_{1 \leq j \leq n} (- x_{j})} .

This yields

\begin{array}{l} \sum_{1 \leq i, j \leq n} b_{i j} & = \sum_{1 \leq i \leq n} P_{i} (1) \\ = \prod_{1 \leq k \leq n} (x_{k} - 1) (\sum_{1 \leq i \leq n} \frac{1}{x_{i} \prod_{\begin{array}{c} 1 \leq k \leq n \\ k \neq i \end{array}} (x_{i} - x_{k})} - \sum_{1 \leq i \leq n} \frac{1}{(x_{i} - 1) \prod_{\begin{array}{c} 1 \leq k \leq n \\ k \neq i \end{array}} (x_{i} - x_{k})}) \\ = \prod_{1 \leq k \leq n} (x_{k} - 1) ((1 - \frac{1}{\prod_{1 \leq j \leq n} (- x_{j})}) - (1 - \frac{1}{\prod_{1 \leq j \leq n} (1 - x_{j})})) \\ = \prod_{1 \leq k \leq n} (x_{k} - 1) (\frac{1}{\prod_{1 \leq j \leq n} (- x_{j})} - \frac{1}{\prod_{1 \leq j \leq n} (1 - x_{j})}) \\ = \frac{\prod_{1 \leq k \leq n} (x_{k} - 1)}{\prod_{1 \leq j \leq n} (- x_{j})} - \frac{\prod_{1 \leq k \leq n} (x_{k} - 1)}{\prod_{1 \leq j \leq n} (1 - x_{j})} \\ = \frac{\prod_{1 \leq k \leq n} (1 - x_{k})}{\prod_{1 \leq j \leq n} (1 - x_{j})} - \frac{\prod_{1 \leq k \leq n} (x_{k} - 1)}{\prod_{1 \leq j \leq n} (x_{j})} \\ = 1 - \frac{\prod_{1 \leq k \leq n} (x_{k} - 1)}{\prod_{1 \leq j \leq n} (x_{j})} \\ = 1 - \prod_{1 \leq k \leq n} \frac{x_{k} - 1}{x_{k}} \\ = 1 - \prod_{1 \leq k \leq n} (1 - 1 ∕ x_{k}) . \end{array}

Therefore, in all cases,

\sum_{1 \leq i, j \leq n} b_{i j} = 1 - \prod_{1 \leq k \leq n} (1 - 1 ∕ x_{k}) .

▸

44. [M26] What is the sum of all

n^{2}

elements in the inverse of Cauchy’s matrix?

For the inverse of the Cauchy matrix

{[a_{i j}]}_{n}^{- 1} = {[b_{i j}]}_{n} = {[\frac{\prod_{1 \leq k \leq n} (x_{j} + y_{k}) (x_{k} + y_{i})}{(x_{j} + y_{i}) (\prod_{\begin{array}{c} 1 \leq k \leq n \\ k \neq j \end{array}} (x_{j} - x_{k})) (\prod_{\begin{array}{c} 1 \leq k \leq n \\ k \neq i \end{array}} (y_{i} - y_{k}))}]}_{n}

we want to ﬁnd the sum of all $n^{2}$ elements $\sum_{1 \leq i, j \leq n} b_{i j}$ .

But

\begin{array}{l} \sum_{1 \leq i \leq n} b_{i j} & = \sum_{1 \leq i \leq n} \frac{(\prod_{1 \leq k \leq n} (x_{j} + y_{k}) (x_{k} + y_{i}))}{(x_{j} + y_{i}) (\prod_{\begin{array}{c} 1 \leq k \leq n \\ k \neq j \end{array}} (x_{j} - x_{k})) (\prod_{\begin{array}{c} 1 \leq k \leq n \\ k \neq i \end{array}} (y_{i} - y_{k}))} \\ = \sum_{1 \leq i \leq n} \frac{(\prod_{1 \leq k \leq n} (x_{j} + y_{k})) (\prod_{1 \leq k \leq n} (x_{k} + y_{i}))}{(x_{j} + y_{i}) (\prod_{\begin{array}{c} 1 \leq k \leq n \\ k \neq j \end{array}} (x_{j} - x_{k})) (\prod_{\begin{array}{c} 1 \leq k \leq n \\ k \neq i \end{array}} (y_{i} - y_{k}))} \\ = \frac{\prod_{1 \leq k \leq n} (x_{j} + y_{k})}{\prod_{\begin{array}{c} 1 \leq k \leq n \\ k \neq j \end{array}} (x_{j} - x_{k})} \sum_{1 \leq i \leq n} \frac{\prod_{1 \leq k \leq n} (x_{k} + y_{i})}{(x_{j} + y_{i}) \prod_{\begin{array}{c} 1 \leq k \leq n \\ k \neq i \end{array}} (y_{i} - y_{k})} \\ = \frac{\prod_{1 \leq k \leq n} (x_{j} + y_{k})}{\prod_{\begin{array}{c} 1 \leq k \leq n \\ k \neq j \end{array}} (x_{j} - x_{k})} \sum_{1 \leq i \leq n} \frac{\prod_{\begin{array}{c} 1 \leq k \leq n \\ k \neq i \end{array}} (x_{k} + y_{i})}{\prod_{\begin{array}{c} 1 \leq k \leq n \\ k \neq i \end{array}} (y_{i} - y_{k})} \\ = \frac{\prod_{1 \leq k \leq n} (x_{j} + y_{k})}{\prod_{\begin{array}{c} 1 \leq k \leq n \\ k \neq j \end{array}} (x_{j} - x_{k})} \end{array}

since in general

\sum_{1 \leq i \leq n} \frac{\prod_{1 \leq k \leq n - 1} (y_{i} - z_{k})}{\prod_{\begin{array}{c} 1 \leq k \leq n \\ k \neq i \end{array}} (y_{i} - y_{k})} = 1

from exercise 34.

Then, for some polynomial $P (x)$ of order $n - 2$ and by exercise 33

\begin{array}{l} \sum_{1 \leq i, j \leq n} b_{i j} & = \sum_{1 \leq i \leq n} \frac{\prod_{1 \leq k \leq n} (x_{j} + y_{k})}{\prod_{\begin{array}{c} 1 \leq k \leq n \\ k \neq j \end{array}} (x_{j} - x_{k})} \\ = \sum_{1 \leq i \leq n} \frac{x_{j}^{n} + (\sum_{1 \leq k \leq n} y_{k}) x_{j}^{n - 1} + P (x_{j})}{\prod_{\begin{array}{c} 1 \leq k \leq n \\ k \neq j \end{array}} (x_{j} - x_{k})} \\ = \sum_{1 \leq i \leq n} \frac{x_{j}^{n}}{\prod_{\begin{array}{c} 1 \leq k \leq n \\ k \neq j \end{array}} (x_{j} - x_{k})} + (\sum_{1 \leq k \leq n} y_{k}) \sum_{1 \leq i \leq n} \frac{x_{j}^{n - 1}}{\prod_{\begin{array}{c} 1 \leq k \leq n \\ k \neq j \end{array}} (x_{j} - x_{k})} + \sum_{1 \leq i \leq n} \frac{P (x_{j})}{\prod_{\begin{array}{c} 1 \leq k \leq n \\ k \neq j \end{array}} (x_{j} - x_{k})} \\ = \sum_{1 \leq k \leq n} x_{k} + \sum_{1 \leq k \leq n} y_{k} + 0 \\ = \sum_{1 \leq k \leq n} (x_{k} + y_{k}) . \end{array}

▸

45. [M25] A Hilbert matrix, sometimes called an

n \times n

segment of the (inﬁnite) Hilbert matrix, is a matrix for which

a_{i j} = 1 ∕ (i + j - 1)

. Show that this is a special case of Cauchy’s matrix, ﬁnd its inverse, show that each element of the inverse is an integer, and show that the sum of all elements of the inverse is

n^{2}

. [Note: Hilbert matrices have often been used to test various matrix manipulation algorithms, because they are numerically unstable, and they have known inverses. However, it is a mistake to compare the known inverse, given in this exercise, to the computed inverse of a Hilbert matrix, since the matrix to be inverted must be expressed in rounded numbers beforehand; the inverse of an approximate Hilbert matrix will be somewhat diﬀerent from the inverse of an exact one, due to the instability present. Since the elements of the inverse are integers, and since the inverse matrix is just as unstable as the original, the inverse can be speciﬁed exactly, and one should try to invert the inverse. The integers that appear in the inverse are, however, quite large.] The solution to this problem requires an elementary knowledge of factorials and binomial coeﬃcients, which are discussed in Sections 1.2.5 and 1.2.6.

The Hilbert matrix, deﬁned as

A n = {[a_{i j}]}_{n} = {[\frac{1}{i + j - 1}]}_{n} = {[\begin{matrix} 1 & \frac{1}{2} & \dots & \frac{1}{n} \\ \frac{1}{2} & \frac{1}{3} & \dots & \frac{1}{n + 1} \\ ⋮ & ⋮ & ⋱ & ⋮ \\ \frac{1}{n} & \frac{1}{n + 1} & \dots & \frac{1}{2 n - 1} \end{matrix}]}_{n}

is a special case of a Cauchy matrix $C n = {[c_{i j}]}_{n} = {[\frac{1}{x_{i} + y_{j}}]}_{n}$ with $x_{i} = i$ and $y_{j} = j - 1$ .

As such, its inverse ${[b_{i j}]}_{n} = {[\frac{1}{i + j - 1}]}_{n}^{- 1}$ has elements given by

\begin{array}{l} b_{i j} & = \frac{\prod_{1 \leq k \leq n} (j + k - 1) (k + i - 1)}{(j + i - 1) (\prod_{\begin{array}{c} 1 \leq k \leq n \\ k \neq j \end{array}} (j - k)) (\prod_{\begin{array}{c} 1 \leq k \leq n \\ k \neq i \end{array}} (i - k))} \\ = \frac{\prod_{1 \leq k \leq n} (k + i - 1) \prod_{1 \leq k \leq n} (k + i - 1)}{(j + i - 1) (\prod_{\begin{array}{c} 1 \leq k \leq j \\ k \neq j \end{array}} (j - k)) (\prod_{\begin{array}{c} j \leq k \leq n \\ k \neq j \end{array}} (- 1) (k - j)) (\prod_{\begin{array}{c} 1 \leq k \leq i \\ k \neq i \end{array}} (i - k)) (\prod_{\begin{array}{c} i \leq k \leq n \\ k \neq i \end{array}} (- 1) (k - i))} \\ = (\frac{(j + n - 1)!}{(j - 1)!} \frac{(i + n - 1)!}{(i - 1)!}) / ((j + i - 1) \frac{(j - 1)!}{1!} {(- 1)}^{n - j + 1} \frac{(n - j)!}{1!} \frac{(i - 1)!}{1!} {(- 1)}^{n - i + 1} \frac{(n - i)!}{1!}) \\ = \frac{(j + n - 1)! (i + n - 1)!}{{(- 1)}^{2 n - i - j + 2} (j + i - 1) (j - 1)! (i - 1)! (j - 1)! (n - j)! (i - 1)! (n - i)!} \\ = \frac{(j + n - 1)! (i + n - 1)!}{{(- 1)}^{- (i + j)} (j + i - 1) {((j - 1)! (i - 1)!)}^{2} (n - j)! (n - i)!} \\ = \frac{{(- 1)}^{i + j} (i + n - 1)! (j + n - 1)!}{(i + j - 1) (i - 1)!^{2} (j - 1)!^{2} (n - i)! (n - j)!} . \end{array}

It is clear that $b_{i j}$ is an integer, as it may be cast into binomial coeﬃcients as

\begin{array}{l} b_{i j} & = \frac{{(- 1)}^{i + j} (i + n - 1)! (j + n - 1)!}{(i + j - 1) (i - 1)!^{2} (j - 1)!^{2} (n - i)! (n - j)!} \\ = {(- 1)}^{i + j} \frac{1}{(j - 1)! (i - 1)!} \frac{(i + n - 1)!}{(i - 1)!} \frac{(j + n - 1)!}{(j + i - 1) (n - i)!} \frac{1}{(n - j)! (j - 1)!} \\ = {(- 1)}^{i + j} j \frac{(i + j - 2)!}{(j - 1)! (i - 1)!} \frac{(i + n - 1)!}{n! (i - 1)!} \frac{(j + n - 1)!}{(j + i - 1)! (n - i)!} \frac{n!}{(n - j)! j!} \\ \begin{aligned} = {(- 1)}^{i + j} j \frac{(i + j - 2)!}{((i + j - 2) - (i - 1))! (i - 1)!} \frac{(i + n - 1)!}{((i + n - 1) - (i - 1))! (i - 1)!} \\ \frac{(j + n - 1)!}{((j + n - 1) - (n - i))! (n - i)!} \frac{n!}{(n - j)! j!} \end{aligned} \\ = {(- 1)}^{i + j} j (\binom{i + j - 2}{i - 1}) (\binom{i + n - 1}{i - 1}) (\binom{j + n - 1}{n - i}) (\binom{n}{j}) . \end{array}

From exercise 44, the sum of the elements of the inverse is simply

\begin{array}{l} \sum_{1 \leq i, j \leq n} b_{i j} & = \sum_{1 \leq k \leq n} (k + k - 1) \\ = 2 (\sum_{1 \leq k \leq n} k) - \sum_{1 \leq k \leq n} 1 \\ = 2 \frac{n (n + 1)}{2} - n \\ = n^{2} + n - n \\ = n^{2} . \end{array}

______________________________________________________________________________________________________________________________

[For further information, see J. Todd, J. Research Nat. Bur. Stand. 65 (1961), 19–22; A. Cauchy, Exercices d’analyse et de physique mathématique 2 (1841), 151–159.]

▸

46. [M30] Let

A

be an

m \times n

matrix, and let

B

be an

n \times m

matrix. Given that

1 \leq j_{1}, j_{2}, \dots, j_{m} \leq n

, let

A_{j_{1} j_{2} \dots j_{m}}

denote the

m \times m

matrix consisting of columns

j_{1}, \dots, j_{m}

A

, and let

B_{j_{1} j_{2} \dots j_{m}}

denote the

m \times m

matrix consisting of rows

j_{1}, \dots, j_{m}

B

. Prove the Binet-Cauchy identity

(Note the special cases: (i)

m = n

, (ii)

m = 1

, (iii)

B = A^{T}

, (iv)

m > n

, (v)

m = 2

Proposition. $\det (A B) = \sum_{1 \leq j_{1} < j_{2} < \dots < j_{m} \leq n} \det (A_{j_{1} j_{2} \dots j_{m}}) \det (B_{j_{1} j_{2} \dots j_{m}})$ .

Proof. Let $A$ be an $m \times n$ matrix, and let $B$ be an $n \times m$ matrix. Given that $1 \leq j_{1}, j_{2}, \dots, j_{m} \leq n$ , let $A_{j_{1} j_{2} \dots j_{m}}$ denote the $m \times m$ matrix consisting of columns $j_{1}, \dots, j_{m}$ of $A$ , and let $B_{j_{1} j_{2} \dots j_{m}}$ denote the $m \times m$ matrix consisting of rows $j_{1}, \dots, j_{m}$ of $B$ . We must show that

\det (A B) = \sum_{1 \leq j_{1} < j_{2} < \dots < j_{m} \leq n} \det (A_{j_{1} j_{2} \dots j_{m}}) \det (B_{j_{1} j_{2} \dots j_{m}}) .

Let

𝜖 (k_{1}, \dots, k_{m}) = sign (\prod_{1 \leq i < j \leq m} (k_{j} - k_{i}))

for

sign (x) = [x > 0] - [x < 0]

be the Levi-Civita function so that in general

\det ({[c_{i} j]}_{n}) = \sum_{1 \leq i_{1}, \dots, i_{n} \leq n} 𝜖 (i_{1}, \dots, i_{n}) \prod_{1 \leq i \leq n} a_{i, i_{i}};

and so that if $(k_{1}, \dots, k_{m})$ and $(l_{1}, \dots, l_{m})$ are identical except that $k_{i} = l_{j}$ and $k_{j} = l_{i}$ , so that $𝜖 (k_{1}, \dots, k_{m})$ and $- 𝜖 (l_{1}, \dots, l_{m})$ , then in general

\det (B_{k_{1} \dots k_{m}}) = 𝜖 (k_{1}, \dots, k_{m}) \det (B_{j_{1} \dots j_{m}})

if $j_{1} \leq \dots \leq j_{m}$ are the numbers $k_{1}, \dots, k_{m}$ rearranged into nondecreasing order.

Then

\begin{array}{l} \det (A B) & = \sum_{1 \leq l_{1}, \dots, l_{m} \leq m} 𝜖 (l_{1}, \dots, l_{m}) (\sum_{1 \leq k \leq n} a_{1 k} b_{k l_{1}}) \dots (\sum_{1 \leq k \leq n} a_{m k} b_{k l_{m}}) \\ = \sum_{1 \leq k_{1}, \dots, k_{m} \leq n} a_{1 k_{1}} \dots a_{m k_{m}} \sum_{1 \leq l_{1}, \dots, l_{m} \leq m} 𝜖 (l_{1}, \dots, l_{m}) b_{k_{1} l_{1}} \dots b_{k_{m} l_{m}} \\ = \sum_{1 \leq k_{1}, \dots, k_{m} \leq n} a_{1 k_{1}} \dots a_{m k_{m}} \det (B_{k_{1} \dots k_{m}}) \\ = \sum_{1 \leq k_{1}, \dots, k_{m} \leq n} 𝜖 (k_{1}, \dots, k_{m}) a_{1 k_{1}} \dots a_{m k_{m}} \det (B_{j_{1} \dots j_{m}}) \\ = \sum_{1 \leq j_{1} \leq \dots \leq j_{m} \leq n} \det (A_{j_{1} \dots j_{m}}) \det (B_{j_{1} \dots j_{m}}) \end{array}

as we needed to show.

Note that if $m = n$ , we have the usual identity for square matrices

\det (A B) = \det (A) \det (B);

if $m = 1$ , we have the dot product

\det (A B) = \sum_{1 \leq k \leq n} a_{1 k} b_{k 1} = A \cdot B;

if $B = A^{T}$ , we have the square

\det (A B) = \det (A A^{T}) = \sum_{1 \leq j_{1} \leq \dots \leq j_{m} \leq n} \det {(A_{j_{1} \dots j_{m}})}^{2};

and if $m = 2$ , we have the ﬁrst nontrivial case of the identity

\det (A B) = \sum_{1 \leq j_{1} \leq j_{2} \leq n} \det (A_{j_{1} j_{2}}) \det (B_{j_{1} j_{2}}) .

□

______________________________________________________________________________________________________________________________

[J. de l’École Polytechnique 9 (1813), 280–354; 10 (1815), 29–112. Binet and Cauchy presented their papers on the same day in 1812.]

and generalize this equation to an identity for an

n \times n

determinant in

3 n - 2

variables

x_{1}, \dots, x_{n}, p_{1}, \dots, p_{n - 1}, q_{2}, \dots, q_{n}

. Compare your formula to the result of exercise 38.

We may prove the more general equation.

Proposition. $\det {[(\prod_{1 \leq k \leq j - 1} (x_{i} + p_{k})) (\prod_{j + 1 \leq k \leq n} (x_{i} + q_{k}))]}_{n} = \prod_{1 \leq i < j \leq n} (x_{i} - x_{j}) (p_{i} - q_{j})$ .

Proof. Let

\begin{array}{l} A n & = {[a_{i j}]}_{n} \\ = {[(\prod_{1 \leq k \leq j - 1} (x_{i} + p_{k})) (\prod_{j + 1 \leq k \leq n} (x_{i} + q_{k}))]}_{n} \\ = {[\begin{matrix} \prod_{2 \leq k \leq n} (x_{1} + q_{k}) & (x_{1} + p_{1}) \prod_{3 \leq k \leq n} (x_{1} + q_{k}) & \dots & \prod_{1 \leq k \leq n - 1} (x_{1} + p_{k}) \\ \prod_{2 \leq k \leq n} (x_{2} + q_{k}) & (x_{2} + p_{1}) \prod_{3 \leq k \leq n} (x_{2} + q_{k}) & \dots & \prod_{1 \leq k \leq n - 1} (x_{2} + p_{k}) \\ ⋮ & ⋮ & ⋱ & ⋮ \\ \prod_{2 \leq k \leq n} (x_{n} + q_{k}) & (x_{n} + p_{1}) \prod_{3 \leq k \leq n} (x_{n} + q_{k}) & \dots & \prod_{1 \leq k \leq n - 1} (x_{n} + p_{k}) \end{matrix}]}_{n} . \end{array}

We must show that

\det {[a_{i j}]}_{n} = \prod_{1 \leq i < j \leq n} (x_{i} - x_{j}) (p_{i} - q_{j}) .

Let

a_{i j}^{'} = \{\begin{matrix} a_{i 1} & if j = 1 \\ a_{i j} - a_{i, j - 1} & if 2 \leq j \leq n \end{matrix}

so that $\det {[a_{i j}]}_{n} = \det {[a_{i j}^{'}]}_{n}$ where

a_{i j}^{'} = \{\begin{matrix} (\prod_{1 \leq k \leq j - 1} (x_{i} + p_{k})) (\prod_{j + 1 \leq k \leq n} (x_{i} + q_{k})) & if j = 1 \\ (p_{j - 1} - q_{j}) (\prod_{1 \leq k \leq j - 2} (x_{i} + p_{k})) (\prod_{j + 1 \leq k \leq n} (x_{i} + q_{k})) & if 2 \leq j \leq n \end{matrix}

since for $2 \leq j \leq n$

\begin{array}{l} a_{i j}^{'} & = (\prod_{1 \leq k \leq j - 1} (x_{i} + p_{k})) (\prod_{j + 1 \leq k \leq n} (x_{i} + q_{k})) - (\prod_{1 \leq k \leq j - 2} (x_{i} + p_{k})) (\prod_{j \leq k \leq n} (x_{i} + q_{k})) \\ \begin{aligned} = ((x_{i} + p_{j - 1}) \prod_{1 \leq k \leq j - 2} (x_{i} + p_{k})) (\prod_{j + 1 \leq k \leq n} (x_{i} + q_{k})) \\ - (\prod_{1 \leq k \leq j - 2} (x_{i} + p_{k})) ((x_{i} + q_{j}) \prod_{j + 1 \leq k \leq n} (x_{i} + q_{k})) \end{aligned} \\ = ((x_{i} + p_{j - 1}) - (x_{i} + q_{j})) (\prod_{1 \leq k \leq j - 2} (x_{i} + p_{k})) (\prod_{j + 1 \leq k \leq n} (x_{i} + q_{k})) \\ = (p_{j - 1} - q_{j}) (\prod_{1 \leq k \leq j - 2} (x_{i} + p_{k})) (\prod_{j + 1 \leq k \leq n} (x_{i} + q_{k})) . \end{array}

Let

q_{i j} = \{\begin{matrix} 1 & if j = 1 \\ p_{j - 1} - q_{j} & if 2 \leq j \leq n \end{matrix}

so that

{[a_{i j}^{'}]}_{n} = {({[q_{i j}]}_{n} {[b_{i j}]}_{n}^{T})}^{T}

and that

\begin{array}{l} \det {[a_{i j}^{'}]}_{n} & = \det ({({[q_{i j}]}_{n} {[b_{i j}]}_{n}^{T})}^{T}) \\ = \det ({[q_{i j}]}_{n} {[b_{i j}]}_{n}^{T}) \\ = \det {[q_{i j}]}_{n} \det ({[b_{i j}]}_{n}^{T}) \\ = \prod_{2 \leq k \leq n} (p_{k - 1} - q_{k}) \det ({[b_{i j}]}_{n}^{T}) \\ = \prod_{2 \leq k \leq n} (p_{k - 1} - q_{k}) \det {[b_{i j}]}_{n} \end{array}

where

[b_{i j}] = {[(\prod_{1 \leq k \leq j - 2} (x_{i} + p_{k})) (\prod_{j + 1 \leq k \leq n} (x_{i} + q_{k}))]}_{n} .

Repeating this transformation, each time over fewer columns to factor out $(p_{j - 2} - q_{j - 1})$ , $(p_{j - 3} - q_{j - 2})$ , etc., we eventually have

\det {[a_{i j}]}_{n} = \prod_{1 \leq i < j \leq n} (p_{i} - q_{j}) \det {[b_{i j}]}_{n}

for

{[b_{i j}]}_{n} = {[\begin{matrix} \prod_{j + 1 \leq k \leq n} (x_{i} + q_{k}) \end{matrix}]}_{n} .

Then let

b_{i j}^{'} = \{\begin{matrix} b_{i j} - (q_{j + 1}) b_{i, j + 1} & if 1 \leq j \leq n - 1 \\ b_{i n} & if j = n \end{matrix}

so that $\det {[b_{i j}]}_{n} = \det {[b_{i j}^{'}]}_{n}$ where

b_{i j}^{'} = \{\begin{matrix} x_{i} \prod_{j + 2 \leq k \leq n} (x_{i} + q_{k}) & if 1 \leq j \leq n - 1 \\ x_{i} & if j = n \end{matrix}

since for $1 \leq j \leq n - 1$

\begin{array}{l} b_{i j}^{'} & = \prod_{j + 1 \leq k \leq n} (x_{i} + q_{k}) - (q_{j + 1}) \prod_{j + 2 \leq k \leq n} (x_{i} + q_{k}) \\ = (x_{i} + q_{j + 1}) \prod_{j + 2 \leq k \leq n} (x_{i} + q_{k}) - (q_{j + 1}) \prod_{j + 2 \leq k \leq n} (x_{i} + q_{k}) \\ = ((x_{i} + q_{j + 1}) - (q_{j + 1})) \prod_{j + 2 \leq k \leq n} (x_{i} + q_{k}) \\ = x_{i} \prod_{j + 2 \leq k \leq n} (x_{i} + q_{k}) . \end{array}

Repeating this transformation also, each time over fewer columns to factor out $q_{j + 2}$ , $q_{j + 3}$ , etc., we eventually have

\det {[a_{i j}]}_{n} = \prod_{1 \leq i < j \leq n} (p_{i} - q_{j}) \det {[b_{i j}]}_{n} = \prod_{1 \leq i < j \leq n} (p_{i} - q_{j}) \det {[b_{i j}^{'}]}_{n}

for

{[b_{i j}^{'}]}_{n} = {[x_{i}^{n - j}]}_{n} .

Let

c_{i j}^{'} = \{\begin{matrix} b_{1 j}^{'} & if i = 1 \\ b_{i j}^{'} - b_{1 j}^{'} & if 2 \leq i \leq n \end{matrix}

and

c_{i j}^{″} = \{\begin{matrix} c_{1 j}^{'} - x_{1} c_{1 (j + 1)}^{'} & if i = 1, 1 \leq j \leq n - 1 \\ c_{1 n}^{'} & if i = 1, j = n \\ c_{i j}^{'} - x_{1} c_{i (j + 1)}^{'} & if 2 \leq i \leq n, 1 \leq j \leq n - 1 \\ c_{i n}^{'} & if 2 \leq i \leq n, j = n \leq n, \end{matrix}

so that $\det [b_{i j}^{'}] = \det [c_{i j}^{″}]$ where

c_{i j}^{″} = \{\begin{matrix} 0 & if i = 1, 1 \leq j \leq n - 1 \\ 1 & if i = 1, j = n \\ x_{i}^{n - j - 1} (x_{i} - x_{1}) & if 2 \leq i \leq n, 1 \leq j \leq n - 1 \\ 0 & if 2 \leq i \leq n, j = n \leq n, \end{matrix}

since:

\begin{array}{l} c_{1 j}^{'} & = b_{1 j}^{'} = x_{1}^{n - j} & i = 1, 1 \leq j \leq n - 1 \\ c_{1 n}^{'} & = b_{1 n}^{'} = x_{1}^{0} = 1 & i = 1, j = n \\ c_{i j}^{'} & = b_{i j}^{'} - b_{1 j}^{'} = x_{i}^{n - j} - x_{1}^{n - j} & 2 \leq i \leq n, 1 \leq j \leq n - 1 \\ c_{i n}^{'} & = b_{i j}^{'} - b_{1 j}^{'} = x_{i}^{0} - x_{1}^{0} = 0 & 2 \leq i \leq n, j = n \leq n \\ c_{1 j}^{″} & = x_{1}^{n - j} - x_{1} x_{1}^{n - j - 1} = 0 & i = 1, 1 \leq j \leq n - 1 \\ c_{1 n}^{″} & = x_{1}^{0} = 1 & i = 1, j = n \\ c_{i j}^{″} & = x_{i}^{n - j} - x_{1}^{n - j} - x_{1} (x_{i}^{n - j - 1} - x_{1}^{n - j - 1}) = x_{i}^{n - j - 1} (x_{i} - x_{1}) & 2 \leq i \leq n, 1 \leq j \leq n - 1 \\ c_{i n}^{″} & = x_{i}^{0} - x_{1}^{0} = 0 & 2 \leq i \leq n, j = n \leq n \end{array}

Let

\begin{array}{l} r_{i j} & = \{\begin{matrix} x_{i + 1} - x_{1} & if i = j, 1 \leq i, j \leq n - 1 \\ 0 & otherwise \end{matrix} \end{array}

so that $minor ({[b^{'}]}_{n}, 1, n) = {[r_{i j}]}_{n - 1} minor ({[c^{″}]}_{n}, 1, n)$ and $\det {[r_{i j}]}_{n - 1} = \prod_{1 \leq k \leq n - 1} (x_{k + 1} - x_{1})$ . Then

\begin{array}{l} \det {[c_{i j}^{″}]}_{n} & = \sum_{1 \leq i \leq n} c_{i n}^{″} cofactor (c_{i n}^{″}) \\ = c_{1 n}^{″} cofactor (c_{1 n}^{″}) + \sum_{2 \leq i \leq n} c_{i n}^{″} cofactor (c_{i n}^{″}) \\ = (1) {(- 1)}^{1 + n} \det minor ({[c^{″}]}_{n}, 1, n) + 0 \\ = {(- 1)}^{n + 1} \det minor ({[c^{″}]}_{n}, 1, n) \\ = {(- 1)}^{n + 1} \det {[r_{i j}]}_{n - 1} \det (minor ({[b^{'}]}_{n}, 1, n)) \\ = {(- 1)}^{n + 1} \det {[r_{i j}]}_{n - 1} \det minor ({[b^{'}]}_{n}, 1, n) \\ = {(- 1)}^{n + 1} (\prod_{1 \leq k \leq n - 1} (x_{k + 1} - x_{1})) \det minor ({[b^{'}]}_{n}, 1, n) \\ = (\prod_{1 \leq k \leq n - 1} (x_{k + 1} - x_{1})) \det minor ({[b^{'}]}_{n}, 1, n) \end{array}

since a product of $n + 1$ signs will cancel with $n - 1$ (i.e., ${(- 1)}^{n + 1} {(- 1)}^{n - 1} = {(- 1)}^{2 n} = 1$ ). This recursive identity allows us to prove by mathematical induction on $n$ that

\det {[b_{i j}^{'}]}_{k} = \prod_{1 \leq i < j \leq k} (x_{i} - x_{j}) .

Therefore

\begin{array}{l} \det A n & = \det {[a_{i j}]}_{n} \\ = \det {[(\prod_{1 \leq k \leq j - 1} (x_{i} + p_{k})) (\prod_{j + 1 \leq k \leq n} (x_{i} + q_{k}))]}_{n} \\ = \prod_{1 \leq i < j \leq n} (p_{i} - q_{j}) \det {[b_{i j}]}_{n} \\ = \prod_{1 \leq i < j \leq n} (p_{i} - q_{j}) \det {[b_{i j}^{'}]}_{n} \\ = \prod_{1 \leq i < j \leq n} (p_{i} - q_{j}) {[x_{i}^{n - j}]}_{n} \\ = \prod_{1 \leq i < j \leq n} (p_{i} - q_{j}) \prod_{1 \leq i < j \leq k} (x_{i} - x_{j}) \\ = \prod_{1 \leq i < j \leq n} (x_{i} - x_{j}) (p_{i} - q_{j}) \end{array}

as we needed to show. □

______________________________________________________________________________________________________________________________

[Manuscripta Math. 69 (1990), 177–178.]