Using Lagrange’s interpolation formula to prove complicated sum/product identities

A paper by Sen and Balakrishnan pointed out that Lagrange’s polynomial interpolation formula can be used to construct relatively simple proofs of some complicated-looking sum/product identities. (Sen, A., Balakrishnan, N., 1999, Convolution of geometrics and a reliability problem, Statistics and Probability Letters, 43, pp. 421-426). In this note I want to make a quick record of how this works.

Let $(R_1, f(R_1)), (R_2, f(R_2)), \ldots , (R_{\mathcal{N}}, f(R_{\mathcal{N}}))$ be a set of $\mathcal{N}$ distinct points in $[0, \infty)$ and let $f$ be a continuous function defined on $[0, \infty)$ . Then there is a unique polynomial $p$ of degree $\mathcal{N}-1$ or less which satisfies the interpolation conditions

$p(R_i) = f(R_i) \qquad \qquad \qquad (1)$

for $i = 1, \ldots, \mathcal{N}$ . This unique polynomial can be constructed by defining for $n = 1, \ldots, \mathcal{N}$ the functions

$\mathcal{P}_n(R) = \prod_{\substack{j=1 \\ j \neq n}}^{\mathcal{N}} \frac{(R_j-R)}{(R_j-R_n)} \qquad \qquad \qquad (2)$

These are polynomials of degree less than $\mathcal{N}$ , and since the product on the right-hand side of (2) contains all the $R_j$ except $R_n$ , the functions $\mathcal{P}_n(R)$ satisfy

$\mathcal{P}_n(R_i) = \delta_{ni} \qquad \qquad \qquad (3)$

for $i = 1, \ldots, \mathcal{N}$ , where $\delta_{ni}$ is Kronecker’s delta. In other words, for each $n$ we have $\mathcal{P}_n(R_n) = 1$ , and $\mathcal{P}_n(R_i) = 0$ for $i \neq n$ . Lagrange’s polynomial interpolation formula is then written as

$p(R) = \sum_{n=1}^{\mathcal{N}} \mathcal{P}_n(R) \cdot f(R_n) \qquad \qquad \qquad (4)$

This satisfies the interpolation conditions in (1) above because setting $R = R_i$ in (4) causes all the terms to vanish except $\mathcal{P}_i(R_i)f(R_i) = f(R_i)$ , so (1) is obtained. Crucially for the proofs below, the formula (4) represents a unique polynomial of degree $\mathcal{N}-1$ or less whose values are $f(R_1), f(R_2), \dots, f(R_{\mathcal{N}})$ at the interpolation points $R_1, R_2, \ldots , R_{\mathcal{N}}$ respectively.

Now, a brief indication of how to prove

$\sum_{n=1}^{\mathcal{N}} \bigg(\prod_{\substack{j=1 \\ j\neq n}}^{\mathcal{N}} \bigg(\frac{R_j}{R_j - R_n}\bigg) \bigg) \equiv 1 \qquad \qquad \qquad (5)$

using Lagrange’s polynomial interpolation formula was provided in Sen and Balakrishnan’s paper (cited above), and we elaborate on this idea here to enable similar approaches for other formulas. The sum/product on the left-hand side of (5) looks like Lagrange’s formula for interpolating the points $(R_1, 1), (R_2, 1), \dots, (R_{\mathcal{N}}, 1)$ . In the style of (4), this formula would be

$p(R) = \sum_{n=1}^{\mathcal{N}} \bigg(\prod_{\substack{j=1 \\ j\neq n}}^{\mathcal{N}} \bigg(\frac{R_j - R}{R_j - R_n}\bigg) \bigg) \cdot 1 \qquad \qquad \qquad (6)$

But the constant function that takes the value 1 for all its arguments is a polynomial of degree 0, and the interpolating polynomial $p(R)$ in (6) is unique. Therefore we can immediately conclude that $p(R) = 1$ . But (5) is simply $p(0) = 1$ , so it is immediately proved.

We now see how to adapt this procedure to prove another sum/product formula. Consider the formula

$\sum_{n=1}^{\mathcal{N}} \bigg(\prod_{\substack{j=1 \\ j\neq n}}^{\mathcal{N}} \bigg(\frac{R_j}{R_j - R_n}\bigg)R_n^m \bigg) \equiv 0 \qquad \qquad \qquad (7)$

for $m = 1, \ldots, \mathcal{N}-1$ . The left-hand side of (7) looks like Lagrange’s formula for interpolating the points $(R_1, R_1^m), (R_2, R_2^m), \dots, (R_{\mathcal{N}}, R_{\mathcal{N}}^m)$ . In the style of (4), this formula would be

$p(R) = \sum_{n=1}^{\mathcal{N}} \bigg(\prod_{\substack{j=1 \\ j\neq n}}^{\mathcal{N}} \bigg(\frac{R_j - R}{R_j - R_n}\bigg) \bigg) \cdot R_n^m \qquad \qquad \qquad (8)$

But the function $f(R_n) = R_n^m$ in (8) is a polynomial of degree $m$ , and the interpolating polynomial $p(R)$ in (8) is unique. Therefore we can immediately conclude that $p(R) = R^m$ . But (7) is then simply $p(0) = 0$ , so it is immediately proved.