# Is there a unique polynomial function $f(x)$ of degree $\lt n$ such that $f(n) = a_n$ where $\{a_n\}$ is a sequence?

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.

• en.wikipedia.org/wiki/Lagrange_polynomial – JMoravitz Mar 16 '17 at 4:55
• A linear function is a polynomial function, so if your assertion about uniqueness is indeed true, then your smartass plan won’t work. – amd Mar 16 '17 at 4:56
• 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. – dxiv Mar 16 '17 at 4:58
• @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. – Challenger5 Mar 16 '17 at 5:00
• Not $\le n$, but $<n$. math.stackexchange.com/questions/144257/… – zhoraster Mar 16 '17 at 5:00

## 4 Answers

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!}$$

• 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. – Antoine Mar 17 '17 at 17:42

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$.

• 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 ? – HopefullyHelpful Mar 16 '17 at 9:53
• @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. – Cheerful Parsnip Mar 17 '17 at 0:43
• Yeah, my reading comprehension is off, I thought OP searched for a super quick way to make polynomes from data in his head. duh. – HopefullyHelpful Mar 17 '17 at 0:54

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.

• (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.) – symplectomorphic Mar 16 '17 at 6:01
• "But functions are continuous!" - the teacher, upon seeing this – Aza Mar 16 '17 at 6:46
• @Emrakul: whether you're joking at the teacher's expense or taking that attitude yourself, I refer you to my comment above. – symplectomorphic Mar 16 '17 at 6:47
• reminds me of xkcd.com/221 – Brian Flynn Mar 16 '17 at 10:09

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.