\documentclass {article}
\usepackage [dutch]{babel}
\usepackage {palatino}
\usepackage {amsmath,amssymb}
\title {Divided differences as set function}
\author {Jos van Kan}
\newtheorem {theorem} {Theorem}
\newcommand \qed {\hfill $\Box$}
\begin {document}
\maketitle
\section {Introduction}
The usual way to define divided differences is by recursion. Given pairs $(f_0,
x_0)$, $(f_1, x_1)$,\dots, $(f_n, x_n)$, such that $x_k \neq x_l$ if $k \neq l$
one constructs
\begin {align} 
D(x_0, x_1) &= \frac {f_1 - f_0}{x_1 - x_0}\\
D(x_0, x_1, x_2) &= \frac {D(x_0, x_1) - D(x_1, x_2)}{x_0 - x_2}\\
D(x_0, x_1, \dots, x_n) &= \frac {D(x_0, x_1,\dots,x_{n-1}) - D(x_1, x_2, \dots,
x_n)}{x_0 - x_n}
\end {align}
If you do it this way, it is not so clear, that divided differences are really
{\em 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 {\em define} the divided differences as set functions.

\section {Definition}

We define the divided differences on an arbitrary subset $\Sigma \subseteq \Omega
= \{x_0, x_1, \dots, x_n\}$ recursively:
\begin {align} \label {def:divdifone}
D(\{x_q\}) &= f_q \quad \forall x_q \in \Omega\\\label {def:divdifgen}
D(\Sigma) &= \frac {D(\Sigma \setminus x_p) - D(\Sigma \setminus x_q)}{x_q - x_p}
\end {align}
with $|\Sigma| > 1$, $x_p, x_q \in \Sigma$ and $x_p \neq 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 $|\Sigma|=2$. We
proceed with induction on the cardinality of $\Sigma$.

\begin {theorem} \label {thm:fund} Let $D (\Sigma)$ be a set function for all sets $\Sigma
\subseteq \Omega$ with
$|\Sigma|< k$. Let $3 \leq |\Sigma| \leq k $. Let $x_p$, $x_q$
and $x_r$ be three different elements belonging to $\Sigma$. Then
\begin {equation} \label {eq:fund}
(x_p - x_q) D(\Sigma \setminus x_r) + (x_q - x_r) D(\Sigma \setminus x_p) + 
(x_r - x_p) D(\Sigma \setminus x_q)   = 0
\end {equation}
\end {theorem} 
{\bf Proof.} Since $|\Sigma| \leq k$ it follows that $|\Sigma \setminus x|\leq
k-1, \forall x \in \Sigma$ hence $D
(\Sigma \setminus x)$ is a properly defined set function
by~\ref{def:divdifgen}. 
Hence the following equalities hold:
\begin {align}
D(\Sigma \setminus x_r) &= \frac {D(\Sigma \setminus x_r \setminus x_q) -
        D(\Sigma \setminus x_r \setminus x_p)} {x_p - x_q}\\
D(\Sigma \setminus x_p) &= \frac {D(\Sigma \setminus x_p \setminus x_r) -
        D(\Sigma \setminus x_p \setminus x_q)} {x_q - x_r}\\
D(\Sigma \setminus x_q) &= \frac {D(\Sigma \setminus x_q \setminus x_p) -
        D(\Sigma \setminus x_q \setminus x_r)} {x_r - x_p}
\end {align}
Substitution of these relations into the left hand side of
relation~\ref{eq:fund} shows that this relation in fact is an identity. \qed

\begin {theorem} Let $D (\Sigma)$ be a set function for all sets $\Sigma
\subseteq \Omega$ with $|\Sigma| < k$.  Let $|\Sigma| = k \geq 3$. Then definition~\ref
{def:divdifgen} does not depend on the particular choice of $x_p$ and $x_q$. 
\end {theorem}
{\bf Proof.} By theorem~\ref{thm:fund} we have
\begin {equation}
\frac {D(\Sigma \setminus x_p) - D(\Sigma \setminus x_q)}{x_q - x_p}=
\frac {D(\Sigma \setminus x_p) - D(\Sigma \setminus x_r)}{x_r - x_p}
\end {equation}
and also
\begin {equation}
\frac {D(\Sigma \setminus x_s) - D(\Sigma \setminus x_r)}{x_r - x_s}=
\frac {D(\Sigma \setminus x_p) - D(\Sigma \setminus x_r)}{x_r - x_p}
\end {equation}
as one may verify by multiplying out. Hence
\begin {equation}
\frac {D(\Sigma \setminus x_p) - D(\Sigma \setminus x_q)}{x_q - x_p}=
\frac {D(\Sigma \setminus x_r) - D(\Sigma \setminus x_s)}{x_s - x_r}
\end {equation}
and the theorem is established.\qed
\par\medskip\noindent{\bf Corollary} Definitions~\ref{def:divdifone} and \ref{def:divdifgen} define a
proper set function. Because if definition~\ref{def:divdifgen} properly defines
a set function on sets with cardinality at most $k-1$ it also does so for sets
of cardinality $k$.

\end {document}


 


   
 
