Polynomials? That sounds familiar!

Another CMI problem: (and I could solve this)

Define polynomials \( P_n(x) \) in this way:

  1. P0(x)=1 \displaystyle P_0(x) = 1

  2. Pn(x)=x(x1)(x2)(xn)n! \displaystyle P_n(x) = \dfrac{x(x-1)(x-2)\ldots(x-n)} {n!} where n n is a positive integer.

Prove that for any polynomial f(x) f(x) , there always exist unique real numbers b0,b1,bn b_0, b_1, \ldots b_n such that:

f(x)=0inbipi(x) \displaystyle f(x) = \sum_{0 \le i \le n} b_i p_i (x)

Further prove that the bi b_i 's are all integers, if it is given that f(m) f(m) is an integer for each integer m m .

Note by Parth Thakkar
7 years, 2 months ago

No vote yet
1 vote

  Easy Math Editor

This discussion board is a place to discuss our Daily Challenges and the math and science related to those challenges. Explanations are more than just a solution — they should explain the steps and thinking strategies that you used to obtain the solution. Comments should further the discussion of math and science.

When posting on Brilliant:

  • Use the emojis to react to an explanation, whether you're congratulating a job well done , or just really confused .
  • Ask specific questions about the challenge or the steps in somebody's explanation. Well-posed questions can add a lot to the discussion, but posting "I don't understand!" doesn't help anyone.
  • Try to contribute something new to the discussion, whether it is an extension, generalization or other idea related to the challenge.
  • Stay on topic — we're all here to learn more about math and science, not to hear about your favorite get-rich-quick scheme or current world events.

MarkdownAppears as
*italics* or _italics_ italics
**bold** or __bold__ bold

- bulleted
- list

  • bulleted
  • list

1. numbered
2. list

  1. numbered
  2. list
Note: you must add a full line of space before and after lists for them to show up correctly
paragraph 1

paragraph 2

paragraph 1

paragraph 2

[example link](https://brilliant.org)example link
> This is a quote
This is a quote
    # I indented these lines
    # 4 spaces, and now they show
    # up as a code block.

    print "hello world"
# I indented these lines
# 4 spaces, and now they show
# up as a code block.

print "hello world"
MathAppears as
Remember to wrap math in \( ... \) or \[ ... \] to ensure proper formatting.
2 \times 3 2×3 2 \times 3
2^{34} 234 2^{34}
a_{i-1} ai1 a_{i-1}
\frac{2}{3} 23 \frac{2}{3}
\sqrt{2} 2 \sqrt{2}
\sum_{i=1}^3 i=13 \sum_{i=1}^3
\sin \theta sinθ \sin \theta
\boxed{123} 123 \boxed{123}


Sort by:

Top Newest

Log in to reply

did any one get a seat in CMI (i got one wihtout interview) i solved nearly 6 of the ques....

Priyadarshi Anubhav - 7 years ago

Log in to reply

I did (without interview). Didn't expect it though! Pretty much set on joining there.

Parth Thakkar - 7 years ago

Log in to reply

Part (a): Proving the existence and uniqueness of bi{b_i}:

Let f(x)=c0+c1x+c2x2+...+cnxn f(x)= c_0 +c_1x +c_2x^2+...+c_nx^n and take note of the fact that:

pn(x)=(xn)(xn)p_n(x)= \dbinom{x}{n}(x-n). Since p0(x)=1p_0(x)=1, we may write:

0in(bi)(pi(x))=(b0)+1in(bi)(pi(x))\sum_{0 \le i \le n}(b_i)(p_i(x)) = (b_0)+ \sum_{1 \le i \le n}(b_i)(p_i(x))

Expanding 1in(bi)(pi(x))\sum_{1 \le i \le n}(b_i)(p_i(x)): (Without loss of generality, assume 1in(bi)(pi(x))\sum_{1 \le i \le n}(b_i)(p_i(x))= i=1n(bi)(pi(x))\sum_{i=1}^{n}(b_i)(p_i(x)))

i=1n(bi)(pi(x))\sum_{i=1}^{n}(b_i)(p_i(x)))= b1(x2x)+b22(x33x2+2x)+b36(x46x3+11x26x)+b424(x510x4+35x350x2+24x)+...+bnx!(xn)n!(xn)!b_1(x^2-x)+\frac{b_2}{2}(x^3-3x^2+2x)+\frac{b_3}{6}(x^4-6x^3+11x^2-6x)+\frac{b_4}{24}(x^5-10x^4+35x^3-50x^2+24x)+... +\frac{b_nx!(x-n)}{n!(x-n)!}

Equating coefficients of f(x), cic_i, with those of i=1n(bi)(pi(x))\sum_{i=1}^{n}(b_i)(p_i(x))):




c3=b22b3+3524b4....c_3= \frac{b_2}{2} - b_3 +\frac{35}{24}b_4-....

c4=b361024b4+.....c_4= \frac{b_3}{6} - \frac{10}{24}b_4+.....

c5=b424+....c_5= \frac{b_4}{24}+....

This is a linear system of n equations (excluding c0=b0c_0=b_0) in n unknowns. Therefore, we may construct an n x n matrix A such that: Ab=cA\vec{b}=\vec{c}, where b\vec{b} contains all bib_i and c\vec{c} contains all cic_i. A=A=

(111...α1132116...α20121...α30016...α4...............000....αn) \begin{pmatrix} -1 & 1 & -1&...&\alpha_1 \\ 1 & \frac{-3}{2} & \frac{11}{6}&...&\alpha_2 \\ 0 & \frac{1}{2} & -1&...&\alpha_3\\ 0&0&\frac{1}{6}&...&\alpha_4\\ .&.&.&.&.\\ .&.&.&.&.\\ .&.&.&.&.\\ 0&0&0&....&\alpha_n\\ \end{pmatrix}

Ab=cA\vec{b}=\vec{c} has a unique solution if and only if A is an invertible matrix. A is invertible if and only if det(A)0det(A)\neq 0. Then Ab=cA\vec{b}=\vec{c} has a unique solution if and only if det(A)0det(A)\neq 0. If we use Gaussian Elimination to reduce A, that is, if we add line (1) to line (2), then line (2) to line (3), then line (3) to line (4), etc. we see that A will be reduced to an upper triangular matrix with every term on the main diagonal of A of the form: Aji=1i!A_{ji}=\frac{-1}{i!}, where i corresponds to the column number of AjiA_{ji}. Hence det(A)=i=1n1i!det(A)=\prod_{i=1}^n\frac{-1}{i!}.

Since det(A)=i=1n1i!det(A)=\prod_{i=1}^n\frac{-1}{i!} and i1i\ge1, det(A)0det(A)\neq 0. Then A is invertible and Ab=cA\vec{b}=\vec{c} has a unique solution, hence b=A1c\vec{b}=A^{-1}\vec{c}, which of course exists. This proves the existence of bib_i but does not prove the uniqueness of all bib_i. We will now proceed to prove this.

Let Aji1A_{ji}^{-1} denote the element of A1A^{-1} in the jthj^{th} row and ithi^{th} column. Since b=A1c\vec{b}=A^{-1}\vec{c}, we have:

bn=An11c1+An21c2+An31c3+...+Ann1cnb_n=A_{n1}^{-1}c_1 + A_{n2}^{-1}c_2+A_{n3}^{-1}c_3+...+A_{nn}^{-1}c_n

Suppose \exists bib_i such that bi=bnb_i=b_n but ini \neq n, i.e. suppose all bib_i are not unique. Then, since bnb_n is described by the above equation:

Ai11c1=An11c1 A_{i1}^{-1}c_1=A_{n1}^{-1}c_1

Ai21c2=An21c2 A_{i2}^{-1}c_2=A_{n2}^{-1}c_2

Ai31c3=An31c3 A_{i3}^{-1}c_3=A_{n3}^{-1}c_3

And in general: Ain1cn=Ann1cn A_{in}^{-1}c_n=A_{nn}^{-1}c_n \Rightarrow Ain1=Ann1 A_{in}^{-1}=A_{nn}^{-1}

If Ain1=Ann1 A_{in}^{-1}=A_{nn}^{-1} and ini \neq n, then A1A^{-1} contains at least two identical rows, which implies det(A1)=0det(A^{-1})=0. Then A1A^{-1} is not invertible, which is impossible because (A1)1=A(A^{-1})^{-1}=A. This is a contradiction, hence we are forced to conclude that all bib_i are unique. Part (b) coming soon.


A Former Brilliant Member - 6 years, 11 months ago

Log in to reply

Note that the polynomials Pi(x),0inP_i(x), 0\leq i \leq n have increasing degrees and hence they are linearly independent in the vector space of polynomials of degree nn. Hence they form a basis and the proof for the first part follows.

Abhishek Sinha - 6 years, 11 months ago

Log in to reply

Solved this one. Nice question.

Vijay Raghavan - 7 years, 2 months ago

Log in to reply

How do you solve this question? Can you give the solution? Or atleast an hint

Mridul Sachdeva - 7 years, 2 months ago

Log in to reply

Hint: Notice that Pk(x) P_k (x) vanishes at x=k x = k , and also do the "higher" P P 's. That is, Pk+1,Pk+2 P_{k+1}, P_{k+2} and so on. But the "lower" P P 's don't. If you use this properly, you're done!

Parth Thakkar - 7 years, 2 months ago

Log in to reply

@Parth Thakkar Nice :)

Mridul Sachdeva - 7 years, 2 months ago

Log in to reply


Problem Loading...

Note Loading...

Set Loading...