Find f i ( x ) n − 1 {\displaystyle f_{i}(x)n-1} degree polynomial where: f i ( x i ) = 1 {\displaystyle f_{i}(x_{i})=1} and f i ( x j ) = 0 {\displaystyle f_{i}(x_{j})=0}
Noting that: f i ( x ) = x n − 1 + . . . {\displaystyle f_{i}(x)=x^{n-1}+...}
is the same as f i ( x ) = ∏ j = 1 n x j + . . . {\displaystyle f_{i}(x)=\prod _{j=1}^{n}x_{j}+...}
Then:
f i ( x ) = ∏ j = 1 n ( x − x j ) ( x i − x j ) {\displaystyle f_{i}(x)=\prod _{j=1}^{n}{\frac {(x-x_{j})}{(x_{i}-x_{j})}}} where j ! = i {\displaystyle j!=i}
Now find a polynomial function f {\displaystyle f} of degree n − 1 {\displaystyle n-1} such that f ( x i ) = a i {\displaystyle f(x_{i})=a_{i}}
f ( x ) = ∑ i = 1 n a i f i ( x ) {\displaystyle f(x)=\sum _{i=1}^{n}a_{i}f_{i}(x)} where j ! = i {\displaystyle j!=i}
so: f ( x ) = ∑ i = 1 n a i ∏ j = 1 n ( x − x j ) ( x i − x j ) {\displaystyle f(x)=\sum _{i=1}^{n}a_{i}\prod _{j=1}^{n}{\frac {(x-x_{j})}{(x_{i}-x_{j})}}} where j ! = i {\displaystyle j!=i}
(Note that in this equation will always resulting in 0 unless x = x_i)
