Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

This is another problem from I.M Gelfand's book that I am stuck with.

Problem 169. Assume that $x_1,\ldots,x_{10}$ are different numbers, and $y_1,\ldots,y_{10}$ are arbitrary numbers. Prove that there is one and only one polynomial $P(x)$ of degree not exceeding $9$ such that $P(x_1)=y_1,P(x_2)=y_2,\ldots,P(x_{10})=y_{10}$.

Chapter is about polynomial interpolation. Any kind of hints would be appreciated. Thanks in advance.

share|improve this question
3  
Look up Lagrange Interpolation. –  André Nicolas Nov 10 '12 at 18:23
add comment

5 Answers 5

up vote 2 down vote accepted

Because of a mild allergy to subscripts, I will solve a smaller problem. Let $a,b,c,d$ be distinct numbers, and let $p,q,r,s$ be any numbers. Find a polynomial $P(x)$ of degree $\le 3$ such that $P(a)=p$, $P(b)=q$, $P(c)=r$, and $P(d)=s$.

We use the polynomial $$P(x)=A(x-b)(x-c)(x-d)+B(x-a)(x-c)(x-d)+C(x-a)(x-b)(x-d)+D(x-a)(x-b)(x-c),$$ where the numbers $A$, $B$, $C$, and $D$ will be chosen soon.

Note that when we substitute $a$ for $x$ in our expression for $P(x)$, the last three terms die. So $$P(a)=A(a-b)(a-c)(a-d).$$ We want $P(a)=p$. That is easy to arrange by choosing $$A=\frac{p}{(a-b)(a-c)(a-d)}.$$ In essentially the same way, we can determine $B$, $C$, and $D$. It is no harder to deal with $10$ points, or $100$.

The uniqueness part is standard field theory.

Remark: If we are in a subscript mood, we can write out a solution of the problem for general $n$. Let $$Q_i(x)=\frac{\prod_{j=1}^n (x-x_j)}{x-x_i}.$$ Despite appearances, $Q_i(x)$ is a polynomial, indeed one of degree $n-1$. It is the product of all terms $x-x_j$ except $x-x_i$. Let $$P(x)=A_1Q_1(x)+A_2Q_2(x)+A_3Q_3(x)+\cdots+A_nQ_n(x),$$ where the $A_i$ are constants that will be chosen soon. If we let $$A_i=\frac{y_i}{Q(x_i)},$$ then $P(x)$ has the desired properties. Nice compact proof. But it may be hard to see what is really going on without going through a few concrete examples, or general examples but for a small $n$, like the $n=4$ we dealt with above.

share|improve this answer
    
Thank you! I think I understand this proof, especially the subscript one, I will try to work out some concrete examples to fully understand it, thanks for help Nicolas. –  Paul Dirac Nov 11 '12 at 6:27
1  
Remark that such Lagrange interpolation is just a special case of CRT (Chinese Remainder Theorem). It is instructive to examine the relationship. –  Bill Dubuque Nov 11 '12 at 10:41
    
@BillDubuque I will read about it on wikipedia. Thanks. –  Paul Dirac Nov 11 '12 at 16:30
add comment

I want to thank everyone for help. I also discovered another way to prove this, by the method that @Thomas Andrews & @sperners lemma suggested in my earlier question.

Let's suppose that $q(x)$ is a polynomial of degree no greater then 9, such that $q(x_1)=y_1,\ldots ,q(x_{10})=y_{10}$, and also let $r(x)=p(x)-q(x).$ $r(x)$ is polynomial of degree no greater then 9 such that $r(x_1)=p(x_1)-q(x_1)=y_1-y_1=0,\ldots,r(x_{10})=p(x_{10})-q(x_{10})=y_{10}-y_{10}=0$. So $y_1,\ldots,y_{10}$ are all roots of $r(x)$ which is impossible since $r(x)$ is degree less then 10 unless $r(x)=0$, in which case, $p(x)-q(x)=0$, which means that $p(x)=q(x)$, this proves that there is only one polynomial of degree no greater than 9 that has such values.

share|improve this answer
add comment

Hint $\rm\ p(x_1) = y_1\Rightarrow\:p(x) - y_1 = (x\!-\!x_1)\, q(x)\:\Rightarrow\: y_k - y_1 = (x_k\!-\!x_1)\, q(x_k),\:$ for $\rm\:x_k\ne x_1.\:$ By induction on degree we can solve this for $\rm\:q\:$ such that $\rm\:q(x_k) = (y_k-y_1)/(x_k-x_1).$

share|improve this answer
add comment

Let $\mathbb R[X]_{\le 9}$ denote that the $\mathbb R$-vector space of polynomials with degree not exceeding $9$. Consider the $\mathbb R$-linear map $\Phi\colon \mathbb R[X]_{\le 9} \to \mathbb R^{10}$, $\Phi(P) = \bigl(P(x_1), \ldots, P(x_{10})\bigr)$. Then $\Phi$ is one to one: As $P \in \mathbb R[X]_{\le 9}$ with $\Phi(P) = 0$, we have $P(x_1) = \cdots = P(x_{10}) = 0$. As $P$ has degree at most 9, it can have it most 9 zeros (unless $P = 0$). As the $x_i$ are different, $P = 0$. So $\ker \Phi = \{0\}$ and $\Phi$ is one-to-one.

Note now, that we have $\dim \mathbb R[X]_{\le 9} = 10 = \dim\mathbb R^{10}$ (a basis of the former being $1 = X^0$, $X^1, \ldots$, $X^9$), so $\Phi$ is an isomorphism. So for each $y \in \mathbb R^{10}$, $P = \Phi^{-1}(y)$ is the only polynomial with $P(x_{i}) = y_i$ for $1 \le i \le 10$.

share|improve this answer
    
Thank you for your effort but as you can see, I tagged this question as [algebra-precalculus] so I can't really understand enough linear algebra to read what you wrote. but +1 anyway. –  Paul Dirac Nov 10 '12 at 18:33
add comment

In general let $P$ and $Q$ be degree $n$ polynomials that coincide in $n+1$ places, then $P-Q$ is a degree $\le n$ polynomial which is zero in $n+1$ places, but a polynomial can not have more zeros than its degree so $P-Q = 0$ and hence $P=Q$.

share|improve this answer
    
Thanks. I know that proof, I used it for previous problems but I don't understand how that applies to current problem. +1 and I will think about it, thanks for help. –  Paul Dirac Nov 10 '12 at 18:40
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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