In the follwoing problem, why does the solution with lagrange interpolation work only when i take number of given dataset ( x, f(x) pairs ) >= k+2

problem link

solution 1 - with k+2 points, [0 , k+1]

solution 2 - with k+1 points, [0,k]

@aryanc403 @l_returns @vijju123

2 Likes

Because

sigma n = n*(n+1)/2 is degree 2 polynomial

sigma n^2 = n*(n+1)*(2n+1)/6 is degree 3 polynomial

…

sigma n^k is degree k+1 polynomial.

And in lagrange we need k+1 data points for a degree k polynomial for getting correct result.

Hence we need k+2 data points because it will be a k+1 degree polynomial

4 Likes