Newton's Identities

Newton's identities, also known as Newton-Girard formulae, is an efficient way to find the power sum of roots of polynomials without actually finding the roots. If \(x_1,x_2,\ldots, x_n\) are the roots of a polynomial equation, then Newton's identities are used to find the summations like \[\displaystyle \sum_{i=1}^n x_i^k=x_1^k +x_2^k +\cdots +x_n^k.\]

It is mainly used in conjunction with Vieta's formula while working with the (complex) roots \((\textrm{say } a_1,a_2,\ldots,a_k)\) of a \(k^{\text{th}}\) degree polynomial. The main idea is that the elementary symmetric polynomials form an algebraic basis to produce all symmetric polynomials. Newton's identity gives us the calculation via a recurrence relation with known coefficients.

Suppose that you have a quadratic polynomial \(P(x)\) with (complex) roots \(\alpha_1\) and \(\alpha_2\). Now, you are asked to find the value of \(\alpha_1^2+\alpha_2^2\). This seems very easy since you can use Vieta's formula along with the identity \((a+b)^2=a^2+b^2+2ab\) to find the required result. But what if you need to find \(\left(\alpha_1^{10}+\alpha_2^{10}\right)?\) This would take a while if you were to simply use algebraic manipulations. But there's a clever way, using Newton's sums.

Let \(P(x)=ax^2+bx+c\). Then using Vieta's formula, we can get \(\alpha_1+\alpha_2=-\frac{b}{a}\) and \(\alpha_1\alpha_2=\frac{c}{a}\). Now, denote \(P_i\) as the \(i^{\textrm{th}}\) power sum of the roots, namely \(P_i=\alpha_1^i+\alpha_2^i.\) Then we can obtain \( P_i \) recursively as follows:

\[ \begin{array} {l l l l } P_0 &= \alpha_1 ^ 0 + \alpha_2 ^ 0 & & = 2 \\ P_1 & = \alpha_1 ^ 1 + \alpha_2 ^ 1 & & = - \frac{b}{a} \\ P_2 & = \alpha_1 ^2 + \alpha_2 ^2 & = ( \alpha_1 + \alpha_2)(\alpha_1 + \alpha_2) - 2 \alpha_1 \alpha_2 & = - \frac{b}{a} P_1 - \frac{c}{a} P_0 \\ P_3 & = \alpha_1 ^3 + \alpha_2 ^3 & = ( \alpha_1 + \alpha_2) (\alpha_1 ^2 + \alpha_2 ^2 ) - \alpha_1\alpha_2 ( \alpha_1 + \alpha_2) & = - \frac{b}{a} P_2 - \frac{c}{a} P_1 \\ &\ \vdots &\ \vdots &\ \vdots \\ P_i & = \alpha_1 ^i + \alpha_2 ^ i & = ( \alpha_1 + \alpha_2) ( \alpha_1 ^ {i-1} + \alpha_2 ^ { i - 1} ) - \alpha_1\alpha_2 ( \alpha_1 ^ { i -2 } + \alpha_2 ^ { i-2 } ) & = - \frac{b}{a} P_{i-1} - \frac{c}{a} P_{i-2}. \\ \end{array} \]

This is a linear recurrence relation that gives us the \(i^\text{th}\) power sum. Note that solving this recurrence to get a closed-form solution is equivalent to finding the roots of the quadratic polynomial.

For a quadratic polynomial \(f(x)=ax^2+bx+c\) with (complex) roots \(\alpha_1,\alpha_2\), we denote the \(i^{\textrm{th}}\) power sum of the roots as \(P_i=\displaystyle \sum_{k=1}^2 \alpha_k^i\) and the sum and product of the roots as \(A\) and \(B,\) respectively. Then we have

\[\begin{align} P_1&=A \\ P_2&=AP_1-2B \\ &\ \ \vdots \\ P_i&=AP_{i-1}-BP_{i-2} ~~ \forall i\geq 2. \end{align}\]

Let a polynomial \(P(x)\) be defined as \(P(x)=x^2-2x+6\) with its (complex) roots \(a\) and \(b\). Then what is the value of \(a^{10}+b^{10}?\)

-------
By Vieta's formula, the sum of the roots is \(2=A\textrm{ (say)}\) and the product of the roots is \(6=B\textrm{ (say)}\). Now, using the recurrence relation found above and Newton's identities, we have

\[\begin{array} &P_i=AP_{i-1}-BP_{i-2}=2P_{i-1}-6P_{i-2} ~~\forall i\geq 2, &P_0=2, &P_1=A=2.\end{array}\]

Now, we can simply use this recurrence relation obtained repeatedly to find \(P_2,P_3,\ldots,P_9\) and then finally \(P_{10}\) which is the required answer. The answer comes out to be \(2(-3808)-6(-2528)\).

Hence, our final answer is \(7552\). \( _\square \)

Now that we have learned the use of Newton's identities for a quadratic polynomial, let's take it up a notch. Consider a cubic polynomial \(P(x) = ax^3 + bx^2 + cx + d\) with (complex) roots \(\alpha_1,\alpha_2\textrm{ and }\alpha_3\). Once again, how would we calculate \(\alpha_1^{10}+\alpha_2^{10}+\alpha_3^{10}\)? Again, like last time, we will first use Vieta's formula to find the following values:

\[ \begin{align} \alpha_1+\alpha_2+\alpha_3& =-\dfrac{b}{a} \\ \alpha_1\alpha_2+\alpha_2\alpha_3+\alpha_3\alpha_1 & =\dfrac{c}{a} \\ \alpha_1\alpha_2\alpha_3 & =-\dfrac{d}{a}.\end{align} \]

As before, denote \(P_i\) as the \(i^{\textrm{th}}\) power sum of the roots, namely \(P_i= \alpha_1 ^ i + \alpha _2 ^ i + \alpha_3 ^ i \). Then we can obtain \(P_i\) recursively as follows:

\[\begin{array} { l l l} P_0 & = \alpha_1 ^ 0 + \alpha_2 ^ 0 + \alpha_3 ^ 0 & = 3 \\ P_1 & = \alpha_1 ^ 1 + \alpha_2 ^ 1 + \alpha_3 ^ 1 & = - \frac{b}{a}\\ P_2 & = \alpha_1 ^ 2 + \alpha_2 ^ 2 + \alpha_3 ^ 2 & = (\alpha_1 + \alpha_2 + \alpha_3)(\alpha_1 + \alpha_2 + \alpha_3) - 2 ( \alpha_1 \alpha_2 + \alpha_2 \alpha_3 + \alpha_3 \alpha_1)\\ & & = - \frac{b}{a} P_1 - \frac{c}{a} 2 \\ P_3 & = \alpha_1 ^ 3 + \alpha_2 ^ 3 + \alpha_3 ^ 3 & = (\alpha_1 + \alpha_2 + \alpha_3) \big(\alpha_1^2 + \alpha_2^2 + \alpha_3^2\big) - ( \alpha_1 \alpha_2 + \alpha_2 \alpha_3 + \alpha_3 \alpha_1)(\alpha_1 + \alpha_2 + \alpha_3) + 3 \alpha_1 \alpha_2 \alpha_3 \\ & & = - \frac{b}{a} P_2 - \frac{c}{a} P_1 - \frac{d}{a} P_0 \\ P_4 & = \alpha_1 ^ 4 + \alpha_2 ^4 + \alpha_3 ^ 4 & = (\alpha_1 + \alpha_2 + \alpha_3) \big(\alpha_1^3 + \alpha_2^3 + \alpha_3^3\big) - ( \alpha_1 \alpha_2 + \alpha_2 \alpha_3 + \alpha_3 \alpha_1)\big(\alpha_1 ^2 + \alpha_2 ^2 + \alpha_3 ^2\big) + \alpha_1 \alpha_2 \alpha_3 ( \alpha_1 + \alpha_2 + \alpha_3) \\ & & = - \frac{b}{a} P_3 - \frac{c}{a} P_2 - \frac{d}{a} P_1 \\ &\ \vdots &\ \vdots \\ \end{array} \]

In particular, for \( i \geq 3 \), we have

\[ P_i = - \frac{b}{a} P_{i-1} - \frac{c}{a} P_{i-2} - \frac{d}{a} P_{i-3}. \]

This is a linear recurrence relation that gives us the \( i^{\text{th}} \) power sum. Note that while the final recurrence has similarities with the quadratic case above, the equations for \(P_2\) and \(P_3 \) currently are not easily guessed.

If the roots of the polynomial \(P(x)=x^3-3x^2+6x-9\) are \(a,b\textrm{ and }c,\) what is the value of \(a^5+b^5+c^5?\)

---

Using Vieta's formulas, we get that the sum of the roots is \(3\), the sum of all distinct products of \(2\) different roots is \(6,\) and the product of the roots is \(9\). From the above formula, we calculate that

\[ \begin{array} { l l l } P_1 & & = 3 \\ P_ 2 & = 3 \times P_1 - 6 \times 2 &= -3 \\ P_3 & = 3 \times P_2 - 6 \times P_1 + 9 \times P_0 & = 0 \\ P_4 & = 3 \times P_3 - 6 \times P_2 + 9 \times P_1 & = 45 \\ P_5 & = 3 \times P_4 - 6 \times P_3 + 9 \times P_2 & = 108. \ _\square \end{array} \]

Now that we have seen Newton's identities in action for a quadratic and a cubic polynomial, let us learn the general form to tackle the power sum of the roots of a polynomial of any degree. Consider a \(k^{\textrm{th}}\) degree polynomial with \(k\) (complex) roots \( \alpha_1, \alpha_2, \ldots , \alpha_k \). The polynomial can be defined as

\[P(x)=a_kx^k+a_{k-1}x^{k-1}+a_{k-2}x^{k-2}+\cdots+a_1x+a_0.\]

Denote by \(P_i\) the \(i^{\textrm{th}}\) power sum of the roots, i.e. \(P_i=\displaystyle\sum_{j=1}^k \alpha_j^i\). Also, denote by \(e_i\) the \(i^{\textrm{th}}\) elementary symmetric polynomial, which is the sum of all the products of \(i\) (different) roots. From Vieta's formula, we have

\[ \begin{array} { l l l } e_1 & = \sum \alpha_i & = - \frac{a_{k-1}}{a_k} \\ e_2 & = \sum \alpha_i \alpha_j & = \frac{ a_{k-2} } { a_k} \\ e_3 & = \sum \alpha_i \alpha_j \alpha_k & = - \frac{ a_{k-3} } { a_k} \\ &\ \vdots &\ \vdots \\ e_k & = \sum \prod \alpha_i & = (-1)^k \frac{a_0 } { a_k}. \end{array} \]

Newton's identities give us a relation between the power sum of the roots and the elementary symmetric polynomials. As before, there are 2 parts to the formulas for \( P_i \), namely for \( i \leq k-1 \) and \( i \geq k \).

For \( i \leq k - 1 \), we have the formulas

\[ \begin{array} { l l l l } P_0 & = k \\ P_1 & = e_1 \times 1 \\ P_2 & = e_1 P_1 - e_2 \times 2 \\ P_3 & = e_1 P_2 - e_2 P_1 + e_3 \times 3 \\ &\ \vdots \\ P_{k-1} & = e_1 P_{k-2} - e_2 P_{k-3} + \cdots + (-1)^{k-3} e_{k-2} P_1 + (-1)^{k-2} e_{k-1} \times (k-1). \end{array} \]

For \( i \geq k \), we have the formula

\[ P_i = \sum_{j=1}^k (-1)^{j+1} e_j P_{i-j} = e_1 P_{i-1} - e_2 P_{i-2} + \cdots + (-1)^{k+1} e_k P_{i-k}. \ _\square\]

To make our proof simpler, we are going to consider the case when the polynomial \(P(x)\) is of degree 4. Once the reader understands this simpler case, he or she should be able to generalize the proof to an arbitrary value of \(k.\) So let us assume that our polynomial is \(P(x)=a_4x^4+a_3x^3+a_2x^2+a_1x+a_0.\) Of course \(a_4\neq0.\) Another assumption that we are going to make is that \(a_0\neq0. \) Of course, if \(a_0=0,\) we can reduce the degree of the polynomial by dividing by a certain power of \(x,\) so we eliminate all possible zero roots. By assuming that \(a_0\neq0,\) we are also assuming that all the roots of \(P(x)\) are different from zero. Let us denote any root of \(P(x),\) as above, by \(\alpha_m,\) where \(m\) is an integer satisfying that \(1\leq m\leq4.\)

Dividing the polynomial \(P(x)\) by \(a_4\) and using Vieta's Formulas, we can express the polynomial in the form \(Q(x)=x^4-e_1x^3+e_2x^2-e_3x+e_4.\) We are going to divide the proof into two cases.

Case 1. Where \(i\geq 4\).

We know that as \(\alpha_m\) is a root of the given polynomial for any integer value \(m,\) where \(1\leq m \leq 4,\) it follows that \(\alpha_m^4=e_1\alpha_m^3-e_2\alpha_m^2+e_3\alpha_m-e_4.\) Multiplying both sides of this equation by \(\alpha_m^{i-4},\) we obtain \(\alpha_m^i=e_1\alpha_m^{i-1}-e_2\alpha_m^{i-2}+e_3\alpha_m^{i-3}-e_4\alpha_m^{i-4}.\) Now, adding with respect to \(m,\) we obtain that \(P_i=e_1P_{i-1}-e_2P_{i-2}+e_3P_{i-3}-e_4P_{i-4}.\) This proves the second part of the conclusion of the theorem above in the case that \(i\geq k=4\) that corresponds to this case 1.

Case 2. Where \(i<4\)

Now differentiating both sides of the equation \(Q(x)=(x-\alpha_1)(x-\alpha_2)(x-\alpha_3)(x-\alpha_4),\) we get that \[Q'(x)=\frac{Q(x)}{(x-\alpha_1)}+\frac{Q(x)}{(x-\alpha_2)}+\frac{Q(x)}{(x-\alpha_3)}+\frac{Q(x)}{(x-\alpha_4)}.\qquad (1)\] Using synthetic division, we get that \[\frac{Q(x)}{x-\alpha_m}=x^3+(-e_1+\alpha_m)x^2+\big(e_2-e_1\alpha_m+\alpha_m^2\big)x+\big(-e_3+e_2\alpha_m-e_1\alpha_m ^2+\alpha_m^3\big).\] Adding with respect to \(m,\) we get that \[\sum_{m=1}^4\frac{Q(x)}{x-\alpha_m}=4x^3+(-4e_1+P_1)x^2+(4e_2-e_1P_1+P_2)x+(-4e_3+e_2P_1-e_1P_2+P_3).\qquad (2)\] From \((1)\) and \((2)\) and making the coefficients of \(1, x,\) and \(x^2\) equal, we obtain the following: \[\begin{align} -3e_1&=-4e_1+P_1\\ 2e_2&=4e_2-e_1P_1+P_2\\ -e_3&=-4e_3+e_2P_1-e_1P_2+P_3, \end{align}\] which can be solved for \(P_1, P_2, P_3.\) Then we get \[\begin{align} P_1&=e_1\\ P_2&=e_1P_1-2e_2\\ P_3&=e_1P_2-e_2P_1+3e_3. \end{align}\] Additionally, it is obvious that \(P_0=4,\) because all the roots are different from zero.

This completes the proof of Case 2, and then the proof of the theorem is complete for \(k=4.\)

Newton's identities give us the power sums \( P_i \) in terms of the elementary symmetric polynomials \( e_i \). This also allows us to reverse the equations, to get \(e_i \) in terms of \( P_i \).

If

\[ \begin{align} a + b + c &= 1\\ a^2 + b^2 + c^2 &= 2\\ a^3 + b^3 + c^3 &= 3, \end{align} \]

what is the value of \( abc?\)

---

For \( k = 3 \), Newton's identities tell us that

\[\begin{array} &P_0 = 3, &P_1 = e_1, &P_2 = e_1 P_1 - e_2 2, &P_3 = e_1 P_2 - e_2 P_1 + e_3 3. \end{array}\]

As such, we can calculate that

\[ \begin{array} {l l l l } e_1 & = P_1 && = 1 \\ e_2 & = \frac{ P_2 - e_1 P_1 } { -2} & = \frac{ 2 - 1 \times 1 } { -2} & = - \frac{1}{2} \\ e_3 & = \frac{ P_3 - e_1 P_2 + e_2P_1 } { 3} & = \frac{ 3 - 1 \times 2 + \left(- \frac{1}{2} \right) \times 1 } { 3} & = \frac{1}{6}. \ _\square \end{array}\]

Isn't that amazing? The values of \(a, b, c \) are complex, and are the roots of the polynomial \( x^3 - x^2 - \frac{1}{2} x - \frac{1}{6} \). That would have been hard to determine otherwise.

Evaluate \( \left( 1 + \sqrt{5} i \right) ^ { 10} + \left( 1 - \sqrt{5} i \right) ^ {10} \).

---

Of course, one way of approaching this would be to simply use the binomial theorem to expand both terms, simplify everything, and hope you did not make a calculation mistake. We will present another approach that uses the idea of Newton's identities.

Let \( \alpha = 1 + \sqrt{5} i \) and \( \beta = 1 - \sqrt{5} i \). Then, since \( \alpha \beta = 6\) and \(\alpha + \beta = 2 \), we know that these are the roots of the quadratic equation \( x^2 - 2x + 6 = 0 \).

We can then apply Newton's identities to obtain a recurrence relation to find \( P_{10} \). From the problem at the top, this is equal to \(7552\). \(_ \square \)

Vieta's Formula