30
$\begingroup$

Is it true that for every sequence $a$ of $n$ numbers there is exactly one polynomial function $f(x)$ of degree $\leq n$ such that all $f(1)=a_1,f(2)=a_2,\dots f(n)=a_{n}$? If so, is there an algorithm to, given the sequence, generate the coefficients of this function?

Intuitively, I feel like this is true, because:

  • Given $a$ and $b$, you can find a polynomial function $f$ that has degree $1$ such that $f(0)=a$ and $f(1)=b$.
  • By induction: given coefficients $a_1,a_2\dots a_n$, you can find a polynomial function of degree $n$ such that $f(x)$ yields a constant value for all $x$ in $\{1,2\dots n-1\}$.

Mostly, the reason I want to be able to find such a function is so when my math teacher says "find the function rule" and presents us with an obviously linear function I can give her some strange polynomial that just happens to give the correct answers for those values.

$\endgroup$
  • 5
    $\begingroup$ en.wikipedia.org/wiki/Lagrange_polynomial $\endgroup$ – JMoravitz Mar 16 '17 at 4:55
  • 11
    $\begingroup$ A linear function is a polynomial function, so if your assertion about uniqueness is indeed true, then your smartass plan won’t work. $\endgroup$ – amd Mar 16 '17 at 4:56
  • 3
    $\begingroup$ Note that if f has degree 1 such that f(0)=a and f(1)=b then $f(x)+ x(x-1)g(x)$ will take the same values at $0,1$ for any $g(x)$. P.S. You've got the degrees off-by-1 a couple of times in the question. $\endgroup$ – dxiv Mar 16 '17 at 4:58
  • 3
    $\begingroup$ @amd If I admit higher degrees of polynomials than the length of the sequence (which I intend to), then I can just pick an arbitrary value for $a_{n+1}$ and find a new function. $\endgroup$ – Challenger5 Mar 16 '17 at 5:00
  • 3
    $\begingroup$ Not $\le n$, but $<n$. math.stackexchange.com/questions/144257/… $\endgroup$ – zhoraster Mar 16 '17 at 5:00
26
$\begingroup$

A polynomial degree $\leq n$ modeling $a_1,a_2, \cdots a_n$ would not be unique. Consider $f(1)=1$, $f(2)=4$. Obviously $f(x)=3(x-1)+1$ works, but we can let $f(x)=x^2$.

A polynomial of lowest degree that models $\{a_1,a_2,a_3,...a_n\}$ is unique. A polynomial of lowest degree that fits a set of points is called the Lagrange Polynomial for that set of points. Here we want the Lagrange Polynomial for a very special set of points. A "closed form" is possible:

$$f(x)=\sum_{i=0}^{n-1} {x-1 \choose i} \Delta^i(1)$$

Here $\Delta^0(1)=f(1)$. Also $\Delta$ is defined as the operation mapping $f(x)$ to $f(x+1)-f(x)$. This operation is called the forward difference.Then $\Delta^i(1)$ is the operation iterated $i$ times then evaluated at $1$.

Ex: Find the Lagrange polynomial for $1,3,5$.

$$\color{red}{1},3,5$$

Taking forward differences once gets.

$$\color{red}{2},2$$

Twice,

$$\color{red}{0},$$

This gives a Lagrange polynomial,

$$f(x)=\color{red}{1}{x-1 \choose 0}+\color{red}{2}{x-1 \choose 1}+\color{red}{0}{x-1 \choose 2}$$

$$=2x-1$$

Using this formula, you can troll your teacher. For example if your teacher asks find the rule for $1,3,5,$ then you can use the formula to find a rule for a sequence that goes $1,3,5,\pi$.

$$1,3,5,\pi$$

$$2,2,\pi-5$$

$$0,\pi-7$$

$$\pi-7$$

This gives,

$$f(x)=1+2{x-1 \choose 1}+0+(\pi-7){x-1 \choose 3}$$

$$=1+2(x-1)+(\pi-7)\frac{(x-1)(x-2)(x-3)}{3!}$$

$\endgroup$
  • 1
    $\begingroup$ More generally, for the last example, you can take $2x-1+(x-1)(x-2)(x-3)P(x)$ for any polynomial $P$. This way you can have an arbitrarily high degree polynomial. For instance taking $P(x)=x^9-3x^2+1$ you obtain $x^{12}-6 x^{11}+11 x^{10}-6 x^9-3 x^5+18 x^4-32 x^3+12 x^2+13 x-7$ and you can check it works. $\endgroup$ – Antoine Mar 17 '17 at 17:42
11
$\begingroup$

Regarding trolling your math teacher, if you have a linear function $f$ such that $f(1)=a_1,f(2)=a_2,\cdots, f(n)=a_n$ you can create a polynomial function of higher degree with the same property by adding $g(x)=(x-1)(x-2)\cdots(x-n)$ to $f(x)$. Then $f(i)+g(i)=a_i+0=a_i$.

$\endgroup$
  • $\begingroup$ Sorry, but isn't this just making the problem worse ? I feel like f(x) is the thing you were searching for in the first place and now you just calculated g(x) for nothing ? $\endgroup$ – HopefullyHelpful Mar 16 '17 at 9:53
  • $\begingroup$ @HopefullyHelpful: I was responding to the question about finding a higher-order polynomial that fits the same linear data. This is the last sentence of the original post. $\endgroup$ – Cheerful Parsnip Mar 17 '17 at 0:43
  • $\begingroup$ Yeah, my reading comprehension is off, I thought OP searched for a super quick way to make polynomes from data in his head. duh. $\endgroup$ – HopefullyHelpful Mar 17 '17 at 0:54
9
$\begingroup$

Trolling here is far easier than you're making it out to be. If all you're given is a finite set of points and your teacher asks simply for a function -- not necessarily polynomial -- that fits them, you can just set $f(x_i)=y_i$ for $(x_i,y_i)$ in your list and $f(x)=0$ otherwise.

$\endgroup$
  • 2
    $\begingroup$ (That said, I wouldn't do this if you think your teacher will react badly or doesn't know the material well enough to understand your answer.) $\endgroup$ – symplectomorphic Mar 16 '17 at 6:01
  • 2
    $\begingroup$ "But functions are continuous!" - the teacher, upon seeing this $\endgroup$ – Aza Mar 16 '17 at 6:46
  • $\begingroup$ @Emrakul: whether you're joking at the teacher's expense or taking that attitude yourself, I refer you to my comment above. $\endgroup$ – symplectomorphic Mar 16 '17 at 6:47
  • 1
    $\begingroup$ reminds me of xkcd.com/221 $\endgroup$ – Brian Flynn Mar 16 '17 at 10:09
0
$\begingroup$

You could define a polynomial function

$h(x)=f(x)-a_x$ for your given sequence $a_x$

now if you have $n$ terms in your sequence,

$h(x)$ will be an $n$ th degree polynomial with roots equal to $i$ for $i=1$ to $n$

$h(x)=(x-1)(x-2)\dots (x-n)=f(x)-a_x$ or

$f(x)=(x-1)(x-2)\dots (x-n)+a_x$

as long as your sequence $a_x$ is a polynomial you can find the coefficients this way.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.