Divided differences as set function

Jos van Kan

13 september 2001

1 Introduction

The usual way to define divided differences is by recursion. Given pairs (f_{0}, x_{0}), (f_{1}, x_{1}),…, (f_{n}, x_{n}), such that x_{k} ≠ x_{l} if k ≠ l one constructs

D(x_{0}, x_{1}) = \frac{f_{1} − f_{0}}{x_{1} − x_{0}}  (1)
D(x_{0}, x_{1}, x_{2}) = \frac{D(x_{0}, x_{1}) − D(x_{1}, x_{2})}{x_{0} − x_{2}}  (2)
D(x_{0}, x_{1}, …, x_{n}) = \frac{D(x_{0}, x_{1}, …, x_{n−1}) − D(x_{1}, x_{2}, …, x_{n})}{x_{0} − x_{n}}  (3)

If you do it this way, it is not so clear, that divided differences are really set functions, that is, the order in which the x_{k} appear is immaterial. Of course this is a theorem, and it can be (and has been) proved, but a more satisfactory way is to define the divided differences as set functions.

2 Definition

We define the divided differences on an arbitrary subset Σ ⊆ Ω = {x_{0}, x_{1}, …, x_{n}} recursively:

D({x_{q}}) = f_{q} ∀x_{q} ∈ Ω  (4)
D(Σ) = \frac{D(Σ \ x_{p}) − D(Σ \ x_{q})}{x_{q} − x_{p}}  (5)

with |Σ| > 1, x_{p}, x_{q} ∈ Σ and x_{p} ≠ x_{q}. What remains to be shown is, that this definition does not depend on the particular choice of x_{p} and x_{q}. Clearly this is true if |Σ| = 2. We proceed with induction on the cardinality of Σ.

Theorem 1 Let D(Σ) be a set function for all sets Σ ⊆ Ω with |Σ| < k. Let 3 ≤ |Σ| ≤ k. Let x_{p}, x_{q} and x_{r} be three different elements belonging to Σ. Then

(x_{p} − x_{q})D(Σ \ x_{r}) + (x_{q} − x_{r})D(Σ \ x_{p}) + (x_{r} − x_{p})D(Σ \ x_{q}) = 0 (6)

Proof. Since |Σ| ≤ k it follows that |Σ \ x| ≤ k − 1, ∀x ∈ Σ hence D(Σ \ x) is a properly defined set function by 5. Hence the following equalities hold:

D(Σ \ x_{r}) = \frac{D(Σ \ x_{r} \ x_{q}) − D(Σ \ x_{r} \ x_{p})}{x_{p} − x_{q}}  (7)
D(Σ \ x_{p}) = \frac{D(Σ \ x_{p} \ x_{r}) − D(Σ \ x_{p} \ x_{q})}{x_{q} − x_{r}}  (8)
D(Σ \ x_{q}) = \frac{D(Σ \ x_{q} \ x_{p}) − D(Σ \ x_{q} \ x_{r})}{x_{r} − x_{p}}  (9)

Substitution of these relations into the left hand side of relation 6 shows that this relation in fact is an identity. □

Theorem 2 Let D(Σ) be a set function for all sets Σ ⊆ Ω with |Σ| < k. Let |Σ| = k ≥ 3. Then definition 5 does not depend on the particular choice of x_{p} and x_{q}.

Proof. By theorem 1 we have

\frac{D(Σ \ x_{p}) − D(Σ \ x_{q})}{x_{q} − x_{p}} = \frac{D(Σ \ x_{p}) − D(Σ \ x_{r})}{x_{r} − x_{p}}  (10)

and also

\frac{D(Σ \ x_{s}) − D(Σ \ x_{r})}{x_{r} − x_{s}} = \frac{D(Σ \ x_{p}) − D(Σ \ x_{r})}{x_{r} − x_{p}}  (11)

as one may verify by multiplying out. Hence

\frac{D(Σ \ x_{p}) − D(Σ \ x_{q})}{x_{q} − x_{p}} = \frac{D(Σ \ x_{r}) − D(Σ \ x_{s})}{x_{s} − x_{r}}  (12)

and the theorem is established. □

Corollary Definitions 4 and 5 define a proper set function. Because if definition 5 properly defines a set function on sets with cardinality at most k − 1 it also does so for sets of cardinality k.