April Bush

Answered

2022-06-25

Properties of Finite Differences

I have seen this statement in different variants, but could not find a proof:

If the n-th order differences of equally spaced data are non-zero and constant then the data can be represented by a polynomial.

I interpret this statement more formally as follows:

Let $f:\mathbb{Z}\to \mathbb{Z}$be any function such that the finite differences ${D}_{r}$, defined by

${D}_{r+1}(x)={D}_{r}(x+1)-{D}_{r}(x)$ for $r\ge 0$ (where ${D}_{0}:=f$ by convention)

are such that ${D}_{r}$ is constant and non-zero for any $r\ge {r}_{0}$. Then f is a polynomial in x (with Q coefficients) and degree ${r}_{0}$.

Question: Is this correct as I stated it? How does one prove that such f must be a polynomial?

I have seen this statement in different variants, but could not find a proof:

If the n-th order differences of equally spaced data are non-zero and constant then the data can be represented by a polynomial.

I interpret this statement more formally as follows:

Let $f:\mathbb{Z}\to \mathbb{Z}$be any function such that the finite differences ${D}_{r}$, defined by

${D}_{r+1}(x)={D}_{r}(x+1)-{D}_{r}(x)$ for $r\ge 0$ (where ${D}_{0}:=f$ by convention)

are such that ${D}_{r}$ is constant and non-zero for any $r\ge {r}_{0}$. Then f is a polynomial in x (with Q coefficients) and degree ${r}_{0}$.

Question: Is this correct as I stated it? How does one prove that such f must be a polynomial?

Answer & Explanation

trajeronls

Expert

2022-06-26Added 21 answers

Every polynomial of degree d can be expressed in the basis given by the Falling Factorials up to falling index d.

That is

$\begin{array}{rl}& p(x)={a}_{\phantom{\rule{thinmathspace}{0ex}}d}\phantom{\rule{thinmathspace}{0ex}}{x}^{\phantom{\rule{thinmathspace}{0ex}}d}+{a}_{\phantom{\rule{thinmathspace}{0ex}}d-1}\phantom{\rule{thinmathspace}{0ex}}{x}^{\phantom{\rule{thinmathspace}{0ex}}d-1}+\phantom{\rule{thickmathspace}{0ex}}\cdots \phantom{\rule{thickmathspace}{0ex}}+{a}_{\phantom{\rule{thinmathspace}{0ex}}0}\phantom{\rule{thinmathspace}{0ex}}{x}^{\phantom{\rule{thinmathspace}{0ex}}0}=\\ & ={b}_{\phantom{\rule{thinmathspace}{0ex}}d}\phantom{\rule{thinmathspace}{0ex}}{x}^{\phantom{\rule{thinmathspace}{0ex}}\underset{\_}{d}}+{b}_{\phantom{\rule{thinmathspace}{0ex}}d-1}\phantom{\rule{thinmathspace}{0ex}}{x}^{\phantom{\rule{thinmathspace}{0ex}}\underset{\_}{d-1}}+\phantom{\rule{thickmathspace}{0ex}}\cdots \phantom{\rule{thickmathspace}{0ex}}+{b}_{\phantom{\rule{thinmathspace}{0ex}}0}\phantom{\rule{thinmathspace}{0ex}}{x}^{\phantom{\rule{thinmathspace}{0ex}}\underset{\_}{0}}\end{array}$

Then, from the properties of the falling factorial, it is easy to demonstrate that

${\mathrm{\Delta}}^{n}p(0)=\sum _{k}{\left(-1\right)}^{n-k}\left(\begin{array}{c}n\\ k\end{array}\right)\phantom{\rule{thickmathspace}{0ex}}p(k)=\{\begin{array}{cc}0& d<n\\ d!{b}_{\phantom{\rule{thinmathspace}{0ex}}d}=d!{a}_{\phantom{\rule{thinmathspace}{0ex}}d}& n=d\\ n!{b}_{\phantom{\rule{thinmathspace}{0ex}}n}& n\le d\end{array}$

And viceversa, given

${\mathrm{\Delta}}^{d}p(x)=d!{b}_{\phantom{\rule{thinmathspace}{0ex}}d}\phantom{\rule{1em}{0ex}}\Rightarrow \phantom{\rule{1em}{0ex}}{\mathrm{\Delta}}^{d+1}p(x)=0$

the Newton series assures us that

$p(a+x)=p(a)+x\phantom{\rule{thinmathspace}{0ex}}\mathrm{\Delta}p(a)+\cdots +\frac{{x}^{\phantom{\rule{thinmathspace}{0ex}}\underset{\_}{\phantom{\rule{thinmathspace}{0ex}}d}}}{d!}\phantom{\rule{thickmathspace}{0ex}}{\mathrm{\Delta}}^{\phantom{\rule{thinmathspace}{0ex}}d}p(a)$

So we can conclude that

if we are given a sequence of m+1 points equally spaced by h

$\left\{{x}_{0},{x}_{0}+h,{x}_{0}+2h,\dots ,{x}_{0}+mh\right\}$

and the corresponding sequence of values taken by a function f(x)

${\left\{f({x}_{0}+kh)\right\}}_{k=0}^{h}$

we can put

$f\left({x}_{0}+kh\right)=f\left(h\left(\frac{{x}_{0}}{h}+k\right)\right)=g\left(k\right)$

denoting the differences as

$\{\begin{array}{c}\mathrm{\Delta}g\left(k\right)=g\left(k+1\right)-g\left(k\right)\hfill \\ {\mathrm{\Delta}}^{n}g\left(k\right)=\mathrm{\Delta}\left({\mathrm{\Delta}}^{n-1}g\left(k\right)\right)=\hfill \\ =\sum _{\left(0\le \right)j\left(\le n\right)}{\left(-1\right)}^{n-j}\left(\begin{array}{c}n\\ j\end{array}\right)g\left(k+j\right)\phantom{\rule{1em}{0ex}}|\phantom{\rule{thickmathspace}{0ex}}0\le n+k\le m\hfill \end{array}$

we have that the sequence in n of $(-1{)}^{n}{\mathrm{\Delta}}^{n}g\left(k\right)$ is the Binomial Transform of the sequence of the values g(k+n)

${\left\{{\left(-1\right)}^{n}{\mathrm{\Delta}}^{n}g\left(k\right)\right\}}_{n=0}^{m-k}\underset{Binomial\phantom{\rule{thickmathspace}{0ex}}Transform}{\phantom{\rule{0pt}{0ex}}\u27f7}{\left\{g\left(k+n\right)\right\}}_{n=0}^{m-k}$

and since the Binomial Transform is self-inverse, we get

$g\left(k+n\right)=\sum _{\left(0\le \right)j\left(\le n\right)}\left(\begin{array}{c}n\\ j\end{array}\right){\mathrm{\Delta}}^{j}g\left(k\right)=\sum _{\left(0\le \right)j\left(\le n\right)}\frac{{\mathrm{\Delta}}^{j}g\left(k\right)}{j!}{\left(\left(n+k\right)-k\right)}^{\underset{\_}{\phantom{\rule{thinmathspace}{0ex}}j\phantom{\rule{thinmathspace}{0ex}}}}$

which is precisely the Newton series.

given n+1 points $\{k,k+1,\dots ,k+n\}$ and the respective g(k+j)the Newton series is the unique polynomial of max degree n which interpolates them.

if the differences of order n<m are all equal to each other (at changing k)

${\mathrm{\Delta}}^{n}g\left(k\right)=c\ne 0\phantom{\rule{1em}{0ex}}|\phantom{\rule{thickmathspace}{0ex}}0\le \mathrm{\forall}k\le m-n$

then all the differences of order higher than n will be null

${\mathrm{\Delta}}^{n+q}g\left(k\right)={\mathrm{\Delta}}^{q}\left({\mathrm{\Delta}}^{n}g\left(k\right)\right)={\mathrm{\Delta}}^{q}c=0\phantom{\rule{1em}{0ex}}|\phantom{\rule{thickmathspace}{0ex}}\mathrm{\forall}k$

and the relevant Newton series will be the unique polynomial of degree n which interpolates all the m+1 points

That is

$\begin{array}{rl}& p(x)={a}_{\phantom{\rule{thinmathspace}{0ex}}d}\phantom{\rule{thinmathspace}{0ex}}{x}^{\phantom{\rule{thinmathspace}{0ex}}d}+{a}_{\phantom{\rule{thinmathspace}{0ex}}d-1}\phantom{\rule{thinmathspace}{0ex}}{x}^{\phantom{\rule{thinmathspace}{0ex}}d-1}+\phantom{\rule{thickmathspace}{0ex}}\cdots \phantom{\rule{thickmathspace}{0ex}}+{a}_{\phantom{\rule{thinmathspace}{0ex}}0}\phantom{\rule{thinmathspace}{0ex}}{x}^{\phantom{\rule{thinmathspace}{0ex}}0}=\\ & ={b}_{\phantom{\rule{thinmathspace}{0ex}}d}\phantom{\rule{thinmathspace}{0ex}}{x}^{\phantom{\rule{thinmathspace}{0ex}}\underset{\_}{d}}+{b}_{\phantom{\rule{thinmathspace}{0ex}}d-1}\phantom{\rule{thinmathspace}{0ex}}{x}^{\phantom{\rule{thinmathspace}{0ex}}\underset{\_}{d-1}}+\phantom{\rule{thickmathspace}{0ex}}\cdots \phantom{\rule{thickmathspace}{0ex}}+{b}_{\phantom{\rule{thinmathspace}{0ex}}0}\phantom{\rule{thinmathspace}{0ex}}{x}^{\phantom{\rule{thinmathspace}{0ex}}\underset{\_}{0}}\end{array}$

Then, from the properties of the falling factorial, it is easy to demonstrate that

${\mathrm{\Delta}}^{n}p(0)=\sum _{k}{\left(-1\right)}^{n-k}\left(\begin{array}{c}n\\ k\end{array}\right)\phantom{\rule{thickmathspace}{0ex}}p(k)=\{\begin{array}{cc}0& d<n\\ d!{b}_{\phantom{\rule{thinmathspace}{0ex}}d}=d!{a}_{\phantom{\rule{thinmathspace}{0ex}}d}& n=d\\ n!{b}_{\phantom{\rule{thinmathspace}{0ex}}n}& n\le d\end{array}$

And viceversa, given

${\mathrm{\Delta}}^{d}p(x)=d!{b}_{\phantom{\rule{thinmathspace}{0ex}}d}\phantom{\rule{1em}{0ex}}\Rightarrow \phantom{\rule{1em}{0ex}}{\mathrm{\Delta}}^{d+1}p(x)=0$

the Newton series assures us that

$p(a+x)=p(a)+x\phantom{\rule{thinmathspace}{0ex}}\mathrm{\Delta}p(a)+\cdots +\frac{{x}^{\phantom{\rule{thinmathspace}{0ex}}\underset{\_}{\phantom{\rule{thinmathspace}{0ex}}d}}}{d!}\phantom{\rule{thickmathspace}{0ex}}{\mathrm{\Delta}}^{\phantom{\rule{thinmathspace}{0ex}}d}p(a)$

So we can conclude that

if we are given a sequence of m+1 points equally spaced by h

$\left\{{x}_{0},{x}_{0}+h,{x}_{0}+2h,\dots ,{x}_{0}+mh\right\}$

and the corresponding sequence of values taken by a function f(x)

${\left\{f({x}_{0}+kh)\right\}}_{k=0}^{h}$

we can put

$f\left({x}_{0}+kh\right)=f\left(h\left(\frac{{x}_{0}}{h}+k\right)\right)=g\left(k\right)$

denoting the differences as

$\{\begin{array}{c}\mathrm{\Delta}g\left(k\right)=g\left(k+1\right)-g\left(k\right)\hfill \\ {\mathrm{\Delta}}^{n}g\left(k\right)=\mathrm{\Delta}\left({\mathrm{\Delta}}^{n-1}g\left(k\right)\right)=\hfill \\ =\sum _{\left(0\le \right)j\left(\le n\right)}{\left(-1\right)}^{n-j}\left(\begin{array}{c}n\\ j\end{array}\right)g\left(k+j\right)\phantom{\rule{1em}{0ex}}|\phantom{\rule{thickmathspace}{0ex}}0\le n+k\le m\hfill \end{array}$

we have that the sequence in n of $(-1{)}^{n}{\mathrm{\Delta}}^{n}g\left(k\right)$ is the Binomial Transform of the sequence of the values g(k+n)

${\left\{{\left(-1\right)}^{n}{\mathrm{\Delta}}^{n}g\left(k\right)\right\}}_{n=0}^{m-k}\underset{Binomial\phantom{\rule{thickmathspace}{0ex}}Transform}{\phantom{\rule{0pt}{0ex}}\u27f7}{\left\{g\left(k+n\right)\right\}}_{n=0}^{m-k}$

and since the Binomial Transform is self-inverse, we get

$g\left(k+n\right)=\sum _{\left(0\le \right)j\left(\le n\right)}\left(\begin{array}{c}n\\ j\end{array}\right){\mathrm{\Delta}}^{j}g\left(k\right)=\sum _{\left(0\le \right)j\left(\le n\right)}\frac{{\mathrm{\Delta}}^{j}g\left(k\right)}{j!}{\left(\left(n+k\right)-k\right)}^{\underset{\_}{\phantom{\rule{thinmathspace}{0ex}}j\phantom{\rule{thinmathspace}{0ex}}}}$

which is precisely the Newton series.

given n+1 points $\{k,k+1,\dots ,k+n\}$ and the respective g(k+j)the Newton series is the unique polynomial of max degree n which interpolates them.

if the differences of order n<m are all equal to each other (at changing k)

${\mathrm{\Delta}}^{n}g\left(k\right)=c\ne 0\phantom{\rule{1em}{0ex}}|\phantom{\rule{thickmathspace}{0ex}}0\le \mathrm{\forall}k\le m-n$

then all the differences of order higher than n will be null

${\mathrm{\Delta}}^{n+q}g\left(k\right)={\mathrm{\Delta}}^{q}\left({\mathrm{\Delta}}^{n}g\left(k\right)\right)={\mathrm{\Delta}}^{q}c=0\phantom{\rule{1em}{0ex}}|\phantom{\rule{thickmathspace}{0ex}}\mathrm{\forall}k$

and the relevant Newton series will be the unique polynomial of degree n which interpolates all the m+1 points

Most Popular Questions