For calculating divided (fraction) difference table for interpolating the points $(x_i, f_i)$, $i=1,2,...,n$; by using a polynomial with degree lower or equal to $n$, $n(n-1)/2$ fraction was used.
I think this sentence is false and $n(n+1)/2$ is needed. Am I right? any hint or idea would highly appreciated. My instructor use following example to prove it:
The number of forward difference operators in a divided difference table forms an arithmetic series (the sum of the members of a finite arithmetic progression). For $n$ points, the number of forward difference operators, i.e. the number of $\Delta_i^j$ 's; as seen in the divided difference table is $$ 1+2+3+\cdots+(n-1)=\sum_{k=1}^{n-1}{k} $$ For an arithmetic series $a_1+a_2+\cdots +a_m$ with $m$ terms we have $$ a_1+a_2+\cdots +a_m=\sum_{k=a_1}^{a_m}{k}=\frac{m(a_1+a_m)}{2} $$ where $a_1$ is the initial term of an arithmetic progression and $a_m$ is the $m$th term of the sequence. Here we have $m=n-1$ terms, $a_1=1$ and $a_m=n-1$. Now mix all the ingredients $$ \sum_{k=1}^{n-1}{k}=\frac{(n-1)\left(1+(n-1)\right)}{2}=\frac{n(n-1)}{2} $$
In reply to the comment:
If we start from zero then you have $n+1$ points $x_0,x_1,x_2,\ldots,x_n$, not $n$ points that implies $a_1=1$, $m=n$ and $a_m=n$. Thus $$ \sum_{k=1}^{n}{k}=1+2+\cdots+n=\frac{n(n+1)}{2} $$ But be careful. In the above statement $n$ is not the number of points. It is the index of $x_n$. The number of points is $n+1$. As @Jean-ClaudeArbaut said, there are still $n(n−1)/2$ forward difference operators (be careful not to confuse this $n$ with the index of $x_n$. For this, it is good to write $N(N-1)/2$ where $N$ is the number of points) if we don't pay attention to the index of $x_n$ and just count the points.
For example for the following table $$ \begin{array}{c|lcr} i & x_i & f_i & \Delta f_i & \Delta^2f_i & \Delta^3f_i & \Delta^4f_i\\ \hline 0 & x_0 & f_0 & \Delta f_0 & \Delta^2f_0 & \Delta^3f_0 & \Delta^4f_0\\ 1 & x_1 & f_1 & \Delta f_1 & \Delta^2f_1 & \Delta^3f_1 & \\ 2 & x_2 & f_2 & \Delta f_2 & \Delta^2f_2 & \\ 3 & x_3 & f_3 & \Delta f_3 & \\ 4 & x_4 & f_4 & \\ \end{array} $$ we have five points. Thus $$ \text{Number of } \Delta_i^j \text{'s} = \frac{N(N-1)}{2}=\frac{5(5-1)}{2}=10 $$ If you like to use the index of the last point $x_4$, you can use $$ \text{Number of } \Delta_i^j \text{'s} = \frac{n(n+1)}{2}=\frac{4(4+1)}{2}=10 $$ Note you cannot use $n(n+1)/2$ if we start from one $$ \begin{array}{c|lcr} i & x_i & f_i & \Delta f_i & \Delta^2f_i & \Delta^3f_i & \Delta^4f_i\\ \hline 1 & x_1 & f_1 & \Delta f_1 & \Delta^2f_1 & \Delta^3f_1 & \Delta^4f_1\\ 2 & x_2 & f_2 & \Delta f_2 & \Delta^2f_2 & \Delta^3f_2 & \\ 3 & x_3 & f_3 & \Delta f_3 & \Delta^2f_3 & \\ 4 & x_4 & f_4 & \Delta f_4 & \\ 5 & x_5 & f_5 & \\ \end{array} $$ Since $$ \text{Number of } \Delta_i^j \text{'s} = \frac{N(N-1)}{2}=\frac{5(5-1)}{2}=10 $$ but $$ \text{Number of } \Delta_i^j \text{'s} = \frac{n(n+1)}{2}=\frac{5(5+1)}{2}=15 $$ It is just playing with indices.