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{aligned} P_1&=A \\ P_2&=AP_1-2B \\ &\ \ \vdots \\ P_i&=AP_{i-1}-BP_{i-2} ~~ \forall i\geq 2. \end{aligned}$$

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}{c}&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{aligned} \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{aligned}$$

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{aligned} -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{aligned}$$ which can be solved for $P_1, P_2, P_3.$ Then we get $$\begin{aligned} P_1&=e_1\\ P_2&=e_1P_1-2e_2\\ P_3&=e_1P_2-e_2P_1+3e_3. \end{aligned}$$ 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{aligned} a + b + c &= 1\\ a^2 + b^2 + c^2 &= 2\\ a^3 + b^3 + c^3 &= 3, \end{aligned}$$

what is the value of $abc?$

---

For $k = 3$, Newton's identities tell us that

$$\begin{array}{c}&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