Newton Sums (Sym Poly Part 2) Week#7

Well.. 

I was asked to prove Newton Sums, so since I latexed the proof, why not post it :P.

Newton Sums: Consider a polynomial $P(x)$ of degree $n$, with roots $x_1,x_2,\dots,x_n$

$$P(x) = a_nx^n + a_{n-1}x^{n-1} + \cdots + a_1x + a_0.$$   Define $p_d=x_1^d+\dots+x_n^d.$ Then we have,  

$$a_np_1 + a_{n-1} = 0$$   $$a_np_2 + a_{n-1}p_1 + 2a_{n-2}=0$$ $$a_np_3 + a_{n-1}p_2 + a_{n-2}p_1 + 3a_{n-3}=0$$

$$\vdots$$

(Define $a_j = 0$ for $j<0$.)

Proof : Note that

$$p_1=x_1+x_2+\dots+x_n=\frac{-a_{n-1}}{a_n}\implies \boxed{a_n\cdot p_1+a_{n-1}=0}$$

Note that

$$p_2=x_1^2+\dots+x_n^2=(x_1+\dots+x_n)^2-2(x_1\cdot x_2+x_1\cdot x_3+\dots+x_{n-1}\cdot x_{n})=$$ $$p_1 \cdot \frac{-a_{n-1}}{a_n}-2\cdot \frac{a_{n-2}}{a_n}\implies \boxed{p_2\cdot a_n+p_1\cdot a_{n-1}+2\cdot a_{n-2}=0}$$

Note that

$$p_3=x_1^3+\dots+x_n^3=(x_1^2+\dots+x_n^2)(x_1+\dots+x_n)-(x_1\cdot x_2+x_1\cdot x_3+\dots+$$ $$x_{n-1}\cdot x_{n})(x_1+x_2+\dots+x_n)+3(x_1\cdot x_2\cdot x_3+\dots+x_{n-2}\cdot x_{n-1}\cdot x_n)=$$ $$p_2\cdot \frac{-a_{n-1}}{a_n} -p_1\cdot \frac{a_{n-2}}{a_n}+3\cdot \frac{-a_{n-3}}{a_n}$$

$$p_{k+1}=(a_1^k+a_2^k+\dots+a_n^k)(a_1+\dots+a_n)-(a_1^{k-1}+\dots+a_n^{k-1})(a_1\cdot a_2+\dots +a_{n-1}a_{n})+(a_1^{k-2}+$$ $$\dots+a_n^{k-2})(a_1\cdot a_2\cdot a_3+\dots+a_{n-2}\cdot a_{n-1}\cdot a_n)+$$ $$\dots-(-1)^{k+1}\cdot (k+1)(a_1\cdots a_{k+1}+\dots+a_{n-k}\dots a_n)$$  

$$=p_k\cdot \frac{-a_{n-1}}{a_n}-p_{k-1}\cdot \frac{a_{n-2}}{a_n}+p_{k-2}\cdot \frac{-a_{n-3}}{a_n}+\dots+-(-1)^{k+1}\frac{a_{n-k}}{a_n}\cdot (k+1)\implies$$  

$$\boxed{ p_{k+1}\cdot a_n+p_k\cdot (a_{n-1})+\dots + (k+1)(a_{n-k-1})}=0$$