Newton's Sums

by SomeonecoolLovesMaths, Mar 18, 2024, 5:35 PM

Newton sums give us a clever and efficient way of finding the sums of roots of a polynomial raised to a power. They can also be used to derive several factoring identities.

Statement
Consider a polynomial $P(x)$ of degree $n$ ,

$P(x) = a_nx^n + a_{n-1}x^{n-1} + \cdots + a_1x + a_0$
Let $P(x)=0$ have roots $x_1,x_2,\ldots,x_n$ . Define the sum:

$P_k = x_1^k + x_2^k + \cdots + x_n^k.$ Newton's sums tell us that,

$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$ $\boxed{a_nP_k+a_{n-1}P_{k-1}+\cdots+a_{n-k+1}P_1+k\cdot a_{n-k}=0}$ (Define $a_j = 0$ for $j<0$ .)

We also can write:

$P_1 = S_1$ $P_2 = S_1P_1 - 2S_2$ $P_3 = S_1P_2 - S_2P_1 + 3S_3$ $P_4 = S_1P_3 - S_2P_2 + S_3P_1 - 4S_4$ $P_5 = S_1P_4 - S_2P_3 + S_3P_2 - S_4P_1 + 5S_5$ $\vdots$ where $S_n$ denotes the $n$ -th elementary symmetric sum.

Proof
Let $\alpha,\beta,\gamma,...,\omega$ be the roots of a given polynomial $P(x)=a_nx^n+a_{n-1}x^{n-1}+..+a_1x+a_0$ . Then, we have that

$P(\alpha)=P(\beta)=P(\gamma)=...=P(\omega)=0$

Thus,

$\begin{cases}a_n\alpha^n+a_{n-1}\alpha^{n-1}+...+a_0=0\\a_n\beta^n+a_{n-1}\beta^{n-1}+...+a_0=0\\~~~~~~~~~~~~~~~~~~\vdots\\a_n\omega^n+a_{n-1}\omega^{n-1}+...+a_0=0\end{cases}$

Multiplying each equation by $\alpha^{k-n},\beta^{k-n},...,\omega^{k-n}$ , respectively,

$\begin{cases}a_n\alpha^{n+k-n}+a_{n-1}\alpha^{n-1+k-n}+...+a_0\alpha^{k-n}=0\\a_n\beta^{n+k-n}+a_{n-1}\beta^{n-1+k-n}+...+a_0\beta^{k-n}=0\\~~~~~~~~~~~~~~~~~~\vdots\\a_n\omega^{n+k-n}+a_{n-1}\omega^{n-1+k-n}+...+a_0\omega^{k-n}=0\end{cases}$

$\begin{cases}a_n\alpha^{k}+a_{n-1}\alpha^{k-1}+...+a_0\alpha^{k-n}=0\\a_n\beta^{k}+a_{n-1}\beta^{k-1}+...+a_0\beta^{k-n}=0\\~~~~~~~~~~~~~~~~~~\vdots\\a_n\omega^{k}+a_{n-1}\omega^{k-1}+...+a_0\omega^{k-n}=0\end{cases}$

Sum,

$a_n\underbrace{(\alpha^k+\beta^k+...+\omega^k)}_{P_k}+a_{n-1}\underbrace{(\alpha^{k-1}+\beta^{k-1}+...+\omega^{k-1})}_{P_{k-1}}+a_{n-2}\underbrace{(\alpha^{k-2}+\beta^{k-2}+...+\omega^{k-2})}_{P_{k-2}}+...+a_0\underbrace{(\alpha^{k-n}+\beta^{k-n}+...+\omega^{k-n})}_{P_{k-n}}=0$

Therefore,

$a_nP_k+a_{n-1}P_{k-1}+a_{n-2}P_{k-2}+...+a_0P_{k-n}=0.$

Comment

0 Comments

Submit

I will bookmarked this blog
by giangtruong13, Mar 17, 2025, 7:37 AM
W blog op
by quasar_lord, Mar 10, 2025, 5:32 PM
orz blog
how so orzzzz
by Erratum, Jan 31, 2025, 9:47 AM
shouts; your post is too short , it must be atleast 8 characters
by mqoi_KOLA, Dec 5, 2024, 6:37 PM
Guys it took my like 10 hours to do this! Idk why did I even do this, but now it looks kinda satisfying ngl.
by SomeonecoolLovesMaths, Nov 25, 2024, 5:07 PM
add this one new thing to the intergrals that is lim n tends to infinity b-a/n summation k=1 to n f(a+k(b-a)/n))= int_{a}^b f(x) dx
by Levieee, Nov 21, 2024, 8:37 PM
woahh hi HSM main orz blog!!!
by eg4334, Nov 17, 2024, 3:31 PM
Me in 4 years of Aops - 555 posts.

This guy in 10 months of Aops - 2608 posts
by HoRI_DA_GRe8, Oct 17, 2024, 10:22 AM
Remember; the one who falls and gets back up is stronger than the ones who never tried... Good luck for next year's IOQM
by alexanderhamilton124, Oct 15, 2024, 7:03 AM
fourth shout
by QueenArwen, Sep 2, 2024, 4:05 PM
Hii
!!!!!!!!!!!
by Yummo, Apr 2, 2024, 2:43 PM
i am shouting. it is very loud.
by fruitmonster97, Mar 21, 2024, 7:49 PM
real!!!!!
by SirAppel, Mar 17, 2024, 6:22 PM

13 shouts

My First Blog

Newton's Sums

by SomeonecoolLovesMaths, Mar 18, 2024, 5:35 PM

0 Comments