8
$\begingroup$

A polynomial $ p(x)$ is such that $p(0) =5, p(1) = 4, p(2) = 9 $ and $p(3) = 20 $.

What is the minimum degree it can have?

The problem can easily be solved by hit and trial method. First assuming that the degree is 1, then 2 and so on until the initial conditions are satisfied. This method gives the answer as 2, for the above problem.

But in spite of checking each and every value, starting from 1; is there any better approach to solve such problems ?

Many thanks !!

$\endgroup$
4
  • $\begingroup$ I would suggest first to plot the data points. It cannot be $1$ and it could not be greater than $3$ since you only have four data points. $\endgroup$
    – Claude Leibovici
    Feb 13, 2014 at 14:23
  • $\begingroup$ @ClaudeLeibovici Ummmm, I believe it can have degree greater than 3. In that case, the equation will have infinite possible solutions. The extra variable added to solve these equations would be free. Please correct me if I am wrong. $\endgroup$
    – Gaurav
    Feb 13, 2014 at 14:34
  • $\begingroup$ You are perfectly correct $\endgroup$
    – Claude Leibovici
    Feb 13, 2014 at 14:37
  • $\begingroup$ Certainly, you CAN find a polynomial of degree more than $3$; however, the question is asking for the minimum degree. We can, via polynomial interpolation, always find a polynomial of degree at most $n$ that will match any $n+1$ data points; so, no matter what, you can always find a polynomial of degree $3$ in this case, and considering any higher degree goes against the question you were asked. $\endgroup$
    – Nick Peterson
    Feb 13, 2014 at 14:38

1 Answer 1

Reset to default
9
$\begingroup$

For a linear polynomial $p$, you'll always have $p(n+1) - p(n)$ the same. If you write down a table

 1    2    3    4    5
p(1) p(2) p(3) p(4) p(5)

which in your case would be this:

0    1    2    3   
5    4    9    20

and then write the differences $p(2) - p(1)$, $p(3) - p(2)$, etc in a row beneath, you'd get (again in your case)

0    1    2    3   
5    4    9    20
  -1    5   11

That new row is called the "first differences". For a linear function, the entries would all be the same. You can also write down second differences:

0    1    2    3   
5    4    9    20
  -1    5   11
     6    6

For a quadratic function, these second differences will all be the same. Your values actually are all the same, so your function can be expressed as a quadratic.

$\endgroup$
2
  • $\begingroup$ how to convince myself that this method works? Any proof would be helpful. :) $\endgroup$
    – rohith
    Oct 25, 2019 at 7:22
  • 3
    $\begingroup$ In general, if $p(n) = a_k n^k + \ldots + a_1 n + a_0$, then $p(n+1) - p(n)$ will be a degree $k-1$ polynomial. Example; $p(n) = 2n^2 -3n + 1$; then $p(n+1) - p(n) = 2(n+1)^2 - 3(n+1) + 1 - (2n^2 -3n + 1)$,$ = 2n^2 +4n + 2 -3n -3 + 2 - 2n^2 +3n - 1 = 4n$: the quadratic terms cancel. So if your data is fit by a degree-$k$ polynomial, the "first differences" will be fit with a degree $k-1$ polynomial, and so on. If some row of differences is all zeros, then the next row up is fit by a constant polynomial, the one after by a linear polynomial, and so on. $\endgroup$
    – John Hughes
    Oct 25, 2019 at 18:13

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .