I am new to Math Overflow, so I am not really sure whether this question fits the community standards. But, I posted this question in Stack Exchange and recieved no answers. Moreover, nothing even close to an answer to my question can be (easily) found online. So, I decided to post it among researchers to see whether I can get any significant explations.


I was studying Newton's Forward Interpolation and backward interpolation in a computer science course and the form that I got them in, is as follows-


**Forward Interpolation**



> 
> $$f(x)=y=y\_0+\binom u1 \Delta y\_0+\binom u2 \Delta^2y\_0+\dots +\binom
>  un \Delta^ny\_0$$ where \begin{align\*} x\_i&=x\_0+ih \;\text{ (equispaced
>  points)}\\ u&=\frac{x-x\_0}{h}\\ \Delta y\_i &= y\_{i+1}-y\_i,
>  \;i=0,1,\dots\\ \Delta^k y\_i &= \Delta^{k-1}y\_{i+1}-\Delta^{k-1}y\_{i}
>  \end{align\*}
> 
> 
> 


**Backward Interpolation**



> 
> $$f(x)=y=y\_n+\binom u1 \Delta y\_{n-1} + \binom u2
>  \Delta^2y\_{n-2}+\dots +\binom{u+n-1}n \Delta^n y\_0$$ where
> \begin{align\*} x\_i&=x\_0+ih \;\text{ (equispaced points)}\\
>  u&=\frac{x-x\_n}{h}\\ \Delta y\_i &= y\_{n-1}-y\_{n-i-1}, \;i=0,1,\dots\\
>  \Delta^k y\_i &= \Delta^{k-1}y\_{n-1}-\Delta^{k-1}y\_{n-i-1} \end{align\*}
> 
> 
> 


Now, I understood polynomial approximation (that was taught just before these interpolations). But, I don't understand why and how these interpolations work.


I can guess that we have taken equispaced points, found the values of $f$ at those points, and tried to find a *better behaved* approximation that satisfies those values of $f(x)$. But, I don't have any intuition regarding how this approximation function behaves. I don't understand what role the binomials (that too with non integer values) play or what extra advantage the equispaced points give, and I have no idea of how the complex definitions of $\Delta^k$ help us to get this approximation. I tried to look into some of the expressions of $\Delta^k$ and these are what I calculated (about the forward part)-
\begin{align\*}
\Delta y\_0 &= y\_1-y\_0\\
\Delta^2y\_0 &= \Delta y\_1- \Delta y\_0\\
&=y\_2-2y\_1+y\_0
\end{align\*}
So, it's clear that these expressions wont simplify. They will just go on getting uglier.


As of now, I am completely confused about how this thing works. Also, what is the difference between Forward and Backward interpolation, and when to use which one? At this level of confusion, I don't think, rigorous proofs will be of much use. So, I would like to have a geometric interpretation, or simply a concrete intuition to arrive at such an expression.


Can somebody please help me with this? Thanks in advance.



About Newton's forward and backward interpolation
*The forward and backward finite differences and the derivative lower the degree of a polynomial by one.*


This property underlies the construction of series expansions of polynomials and, therefore, analytic functions with appropriate convergence properties in terms of diverse polynomial sequences, in particular, Sheffer sequences. In the terminology of the Sheffer operator calculus, these three operators are delta ops, or lowering ops.


The derivative acting on the power $x^n$ lowers the degree by one. In other words, the derivative is the lowering operator for the fundamental Sheffer sequence of polynomials $S\_n(x) = x^n$, the simplest such sequence. Specifically,


$$D \; x^n = n \; x^{n-1}.$$


Consequently,


$$\frac{D^k}{k!} \; x^n \; |\_{x=0} = \binom{n}{k} \; x^{n-k} \; |\_{x=0} = \delta\_{n-k}.$$


A polynomial of degree $n$ can be expanded as


$$p\_n(x) = \sum\_{k=0}^n \; c\_k \; x^k,$$


and the coefficients determined as


$$c\_k = \frac{D\_{x=0}^k}{k!} \; p\_n(x) ,$$


giving the Taylor series expansion


$$p\_n(x) = \sum\_{k \geq 0} [\; D\_{x=0}^k \; p\_n(x) \;] \; \frac{x^k}{k!}.$$


Now instead of the sequence of power monomials $x^n$, consider the polynomial falling factorials


$$(x)\_n = \frac{x!}{(x-n)!} = (x)(x-1) \cdots (x-n+1) = n! \; \binom{x}{n}.$$


The e.g.f. of a binomial Sheffer polynomial sequence $B\_n(x) = (B.(x))^n$ is


$$ e^{B.(x)t} = e^{xB(t)},$$


and the lowering operator defined by


$$L \; B\_n(x) = n \; B\_{n-1}(x)$$


is


$$L = B^{(-1)}(D),$$


where $B^{(-1)}(t)$ is the compositional inverse about the origin of $B(t)$. This is verified by


$$ B^{(-1)}(D) \; e^{B.(x) t} = B^{(-1)}(D) \; e^{x B(t)} = B^{(-1)}(B(t)) \; e^{x B(t)} = t \; e^{B.(x)t}.$$


The falling factorials have the e.g.f


$$e^{(x).t} = (1+t)^x = e^{x \ln(1+t)},$$


so their lowering op is


$$L = e^{D}-1 .$$


Check:


$$L \; (x)\_n = (e^{D}-1) \; (x)\_n = \frac{(x+1)!}{(x+1-n)} - \frac{x!}{(x-n)!}$$


$$= (x+1 -(x-n+1)) \; \frac{x!}{(x-n+1)!} = n \; (x)\_{n-1} . $$


Consequently,


$$\frac{(e^D-1)^k}{k!} \; (x)\_n \; |\_{x=0}= \binom{n}{k} \; (0)\_{n-k} = \delta\_{n-k}.$$


A polynomial of degree $n$ can be expanded as


$$p\_n(x) = \sum\_{k=0}^n \; c\_k \; (x)\_k$$


and the coefficients determined as


$$c\_k = \frac{(e^{D\_{x=0}}-1)^k }{k!} \; p\_n(x) ,$$


giving the series expansion


$$p\_n(x) = \sum\_{k \geq 0} [\; (e^D-1)^k \; p\_n(x) \; |\_{x=0} \;] \; \frac{(x)\_k}{k!}.$$


The lowering op is the forward difference op


$$(e^D -1) \; f(x) = f(x+1) - f(x), $$


and the $n$-th finite forward difference is


$$(e^D -1)^n \; f(x) = (-1)^n \; \sum\_{k=0}^n (-1)^k \; \binom{n}{k} \; e^{kD} \; f(x)$$


$$ = (-1)^n \; \sum\_{k=0}^\infty \; (-1)^k \; \binom{n}{k} \; f(x+k) := (-1)^n \; \nabla\_{k=0}^n \; f(x+k).$$


(For the purists: I use the convenient convention consistent with limits of the entire reciprocal of Euler's gamma function that $\binom{n}{m}$ vanishes for $m > n$. This allows invariance of the notation when $n$ is generalized to real or complex numbers.)


Then


$$p\_n(x) = \sum\_{k \geq 0} [\;(e^D-1)^k \; p\_n(x) \; |\_{x=0} \;] \; \frac{(x)\_k}{k!}$$


$$ = \sum\_{k \geq 0} \binom{x}{k} \; (-1)^k \; \nabla\_{m=0}^k \; p\_n(m)$$


$$ = \nabla\_{k=0}^{x} \; \nabla\_{m=0}^k \; p\_n(m),$$


the Newton series for the polynomial $p\_n(x)$.


The backward difference operator is


$$(1- e^{-D}) \; f(x) = f(x) - f(x-1).$$


The compositional inverse of $1-e^{-t}$ is $-\ln(1-t)$, so the backward difference operator is the lowering op of the binomial Sheffer sequence with the e.g.f


$$ e^{B.(x)t} = e^{-x \ln(1-t)} = (1-t)^{-x},$$


which is the e.g.f. for the rising factorials, a.k.a. the Pochhammer symbol,


$$(x)\_\bar{n} = (x+n-1)(x+n) \cdots (x) = n! \; \binom{x-1+n}{n} = (-1)^n\; n! \; \binom{-x}{n}.$$


The $n$-th order backward difference is


$$(1-e^{-D})^n \; f(x) = \sum\_{k=0}^n (-1)^k \; \binom{n}{k} \; e^{-kD} \; f(x)$$


$$ = \; \sum\_{k=0}^\infty \; (-1)^k \; \binom{n}{k} \; f(x-k) := \nabla\_{k=0}^n \; f(x-k),$$


and


$$p\_n(x) = \sum\_{k \geq 0} [\;(1-e^{-D})^k \; p\_n(x) \; |\_{x=0} \;] \; (-1)^k \; \frac{(-x)\_k}{k!}$$


$$ = \sum\_{k \geq 0} (-1)^k \; \binom{-x}{k} \; \nabla\_{m=0}^k \; p\_n(-m)$$


$$ = \nabla\_{k=0}^{-x} \; \nabla\_{m=0}^k \; p\_n(-m).$$


Check: $p\_n(-n) = \nabla\_{k=0}^{n} \; \nabla\_{m=0}^k \; p\_n(-m).$


These are the umbral relations cast by


$$y^x= (1-(1-y))^x = \nabla\_{k=0}^{x} \; \nabla\_{m=0}^k \; y^m$$


$$ = (1-(1-\frac{1}{y})^{-x} = \nabla\_{k=0}^{-x} \; \nabla\_{m=0}^k \; y^{-m}$$


where $=$ is understood to mean equivalence under analytic continuation, and in umbral notation, these Newton series may be expressed succinctly as


$$p\_n(x) = (p\_n(.))^x = (1-(1-p\_n(.)))^x =\nabla\_{k=0}^{x} \; (1-p\_n(.))^k $$


$$= \nabla\_{k=0}^{x} \; \nabla\_{m=0}^k \; p\_n(.)^m = \nabla\_{k=0}^{x} \; \nabla\_{m=0}^k \; p\_n(m)$$


$$ = (1-(1-\frac{1}{p\_n(.)}))^{-x} =\nabla\_{k=0}^{-x} \; (1-\frac{1}{p\_n(.)})^k $$


$$= \nabla\_{k=0}^{-x} \; \nabla\_{m=0}^k \; p\_n(.)^{-m} = \nabla\_{k=0}^{-x} \; \nabla\_{m=0}^k \; p\_n(-m).$$


(Info on connections between Mellin transform and Newton series interpolation and on the relations of the forward, backward, and central finite differences to the derivative and, therefore, to the slope of the tangent line to a point on a curve (and curvature, etc.) will appear in a couple of days on my blog.)


