# Show that there is a polynomial of degree at most $n-1$ for which $f(x_i) = a_i$ for all $i$

Let $a_1,\ldots,a_n$ real numbers and $x_1,\ldots,x_n$ be distinct real numbers. Show that there is a polynomial of degree at most $n-1$ for which $f(x_i) = a_i$ for all $i$.

My idea was to prove the statement for $a_1 = 1$ and $a_2 = \cdots = a_n = 0$. We then have $f(x_1) = 1$ and $f(x_m) = 0$ for $1 < n \leq m$. Then I have to construct such a function and see how to construct a function for any sequence of $a_i's$ and $x_i's$.

• Lagrange interpolation. – André Nicolas Mar 4 '16 at 21:55
• Can you show it the way the question wants me to? – user19405892 Mar 4 '16 at 22:00
• The Lagrange interpolation uses precisely that idea. Just specialize it to $a_i=1$ and the rest $0$. – André Nicolas Mar 4 '16 at 22:01
• @AndréNicolas Can you explain how it uses my idea because I don't see it. – user19405892 Mar 4 '16 at 22:02
• But how do we prove it for all sequences? – user19405892 Mar 4 '16 at 22:03

For your specific approach, let $$f_1(x)=\frac{(x-x_2)(x-x_3)\cdots(x-x_n)}{(x_1-x_2)(x_1-x_3)\cdots (x_1-x_n)}.$$ Then $f_1(x)=1$ when $x=x_1$ and $f_1(x)=0$ for all the other $x_i$.

Construct $f_i(x)$ similarly. Then our interpolating polynomial is a suitable linear combination of the $f_i(x)$.

• The degree is EXACTLY $n-1$, not at most so why does the question say that? – user19405892 Mar 4 '16 at 22:18
• Certainly the $f_i(x)$ have degree exactly $n-1$. But when you take the linear combination $\sum a_if_i(x)$, there may be cancellation that results in a lower degree polynomial. Spectacularly so if all the $a_i$ are $0$! – André Nicolas Mar 4 '16 at 22:21
• What if I have another sequence of real numbers $b_1,b_2,\ldots,b_n$. Show that there is a polynomial of degree at most $2n-1$ for which $f(x_i) = a_i$ and $f'(x_i) = b_i$. – user19405892 Mar 4 '16 at 22:23
• Post it and you will get answers. – André Nicolas Mar 4 '16 at 22:25
• As a new question? – user19405892 Mar 4 '16 at 22:28

$f(X)= \sum_i a_i{{(X-x_1)...\overline{(X-x_i)}..(X-x_n)}\over{(x_i-x_1)..(x_i-x_n)}}$

where $\overline{(X-x_i)}$ means the expression $(X-x_i)$ does not appears in the product.