Polynomials? That sounds familiar!

Other problems I found interesting:

1. And you thought limits were always easy

2. A fun problem - Find the formula of number of functions from a power set to another set

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

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

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

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

$\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 $\sum_{1 \le i \le n}(b_i)(p_i(x))$: (Without loss of generality, assume $\sum_{1 \le i \le n}(b_i)(p_i(x))$= $\sum_{i=1}^{n}(b_i)(p_i(x))$)

$\sum_{i=1}^{n}(b_i)(p_i(x))$)= $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), $c_i$, with those of $\sum_{i=1}^{n}(b_i)(p_i(x))$):

$c_0=b_0$

$c_1=-b_1+b_2-b_3+b_4+....=\sum_{i=1}^{n}(-1)^ib_i$

$c_2=b_1-\frac{3}{2}b_2+\frac{11}{6}b_3-\frac{50}{24}b_4+....$

$c_3= \frac{b_2}{2} - b_3 +\frac{35}{24}b_4-....$

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

$c_5= \frac{b_4}{24}+....$

This is a linear system of n equations (excluding $c_0=b_0$) in n unknowns. Therefore, we may construct an n x n matrix A such that: $A\vec{b}=\vec{c}$, where $\vec{b}$ contains all $b_i$ and $\vec{c}$ contains all $c_i$. $A=$

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

$A\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)\neq 0$. Then $A\vec{b}=\vec{c}$ has a unique solution if and only if $det(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: $A_{ji}=\frac{-1}{i!}$, where i corresponds to the column number of $A_{ji}$. Hence $det(A)=\prod_{i=1}^n\frac{-1}{i!}$.

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

Let $A_{ji}^{-1}$ denote the element of $A^{-1}$ in the $j^{th}$ row and $i^{th}$ column. Since $\vec{b}=A^{-1}\vec{c}$, we have:

$b_n=A_{n1}^{-1}c_1 + A_{n2}^{-1}c_2+A_{n3}^{-1}c_3+...+A_{nn}^{-1}c_n$

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

$A_{i1}^{-1}c_1=A_{n1}^{-1}c_1$

$A_{i2}^{-1}c_2=A_{n2}^{-1}c_2$

$A_{i3}^{-1}c_3=A_{n3}^{-1}c_3$

And in general: $A_{in}^{-1}c_n=A_{nn}^{-1}c_n$ $\Rightarrow$ $A_{in}^{-1}=A_{nn}^{-1}$

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

QED

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

Solved this one. Nice question.