Editing Polynomial interpolation (section)

==== Proof of equivalence ====
If a path goes from <math>\Delta^{n-1}y_s    </math> to <math>\Delta^{n+1}y_{s-1}    </math>, it can connect through three intermediate steps, (a) through <math>\Delta^{n}y_{s-1}    </math>, (b) through <math display="inline">C(u-s ,n) </math> or (c) through <math>\Delta^{n}y_s </math>. Proving the equivalence of these three two-step paths should prove that all (n-step) paths can be morphed with the same starting and ending, all of which represents the same formula.

Path (a):

<math>C(u-s, n) \Delta^n y_{s-1}+C(u-s+1, n+1) \Delta^{n+1} y_{s-1}    </math>

Path (b):

<math>C(u-s, n) \Delta^n y_s + C(u-s, n+1) \Delta^{n+1} y_{s-1}            </math>

Path (c):

<math>C(u-s, n) \frac{\Delta^n y_{s-1}+\Delta^n y_{s}}{2} \quad+\frac{C(u-s+1, n+1)+C(u-s, n+1)}{2} \Delta^{n+1} y_{s-1}    </math>

Subtracting contributions from path a and b:

<math>\begin{aligned}
\text{Path a - Path b}= & C(u-s, n)(\Delta^n y_{s-1}-\Delta^n y_s) +(C(u-s+1, n+1)-C(u-s, n-1)) \Delta^{n+1} y_{s-1} \\
= & - C(u-s, n)\Delta^{n+1} y_{s-1} + C(u-s, n) \frac{(u-s+1)-(u-s-n)}{n+1} \Delta^{n+1} y_{s-1}  \\
= & C(u-s, n)(-\Delta^{n+1} y_{s-1}+\Delta^{n+1} y_{s-1} )=0 \\ 
\end{aligned}    </math>

Thus, the contribution of either path (a) or path (b) is the same. Since path (c) is the average of path (a) and (b), it also contributes identical function to the polynomial. Hence the equivalence of paths with same starting and ending points is shown. To check if the paths can be shifted to different values in the leftmost corner, taking only two step paths is sufficient: (a) <math>y_{s+1}          </math> to <math>y_{s}          </math> through <math>\Delta y_{s}          </math> or (b) factor between <math>y_{s+1}          </math> and <math>y_{s}          </math>, to <math>y_{s}          </math> through <math>\Delta y_{s}          </math> or (c) starting from <math>y_{s}          </math>.

Path (a)

<math>y_{s+1}+C(u-s-1,1) \Delta y_s - C(u-s, 1) \Delta y_s         </math>

Path (b)

<math>\frac{y_{s+1}+y_s}{2}+\frac{C(u-s-1,1)+C(u-s, 1)}{2} \Delta y_s - C(u-s, 1) \Delta y_s         </math>

Path (c)

<math>y_{s}          </math>

Since <math>\Delta y_{s} = y_{s+1}-y_s    </math>, substituting in the above equations shows that all the above terms reduce to <math>y_{s}          </math> and are hence equivalent. Hence these paths can be morphed to start from the leftmost corner and end in a common point.<ref name=":0" />