Newton, once again...
April 2021
Another year has passed and the COVID-19 pandemic is yet to be gone. During this time, I’ve been daydreaming about my good old days when I was still going to school without any restriction.
It was during these moments that I remembered one thing I’ve always wanted to prove to myself. And, once again, it involved Isaac Newton.
Table of Contents
- The elementary problem
- Generalizing the problem
The elementary problem
There was a time when, during maths classes, the teacher would always have asked questions like this one:
Given $p(x)=x^2-4x+3$ and $\lambda_1, \lambda_2$ such that $p(\lambda_1)=p(\lambda_2)=0$ (i.e. $\lambda_1, \lambda_2$ are the roots of the polynomial $p(x)$), compute $\lambda_1^2+\lambda_2^2$.
It was not difficult to answer this problem and there were two main approaches to this problem.
Computing roots first
We can compute $\lambda_1$ and $\lambda_2$ using the quadratic formula. We get $\lambda_1=\frac{4 +\sqrt{(-4)^2 -4\cdot1\cdot3}}{2\cdot1}=3$ and $\lambda_2=\frac{4 - \sqrt{(-4)^2 -4\cdot1\cdot3}}{2\cdot1}=1$.
Hence, $\lambda_1^2+\lambda_2^2=3^2+1^2=10$.
The problem given by this kind of approach is that we have to find the roots of $p(x)$ in terms of sums, products and radicals, which is not always possible for polynomials with degree greater than $4$ by the Abel-Ruffini theorem.
Furthermore, we have to compute the result of the sum of all the roots raised to a certain power, which may be difficult to compute if we had irrational roots.
Vieta’s formulae
We know by the factor theorem that $(x-\lambda_1)(x-\lambda_1)=x^2-(\lambda_1 + \lambda_2)x+\lambda_1\lambda_2$. Therefore, $\lambda_1 + \lambda_2 = 4$ and $\lambda_1\lambda_2=3$.
We have to compute $\lambda_1^2 + \lambda_2^2$, which can be rearranged as $(\lambda_1 + \lambda_2)^2 - 2\lambda_1\lambda_2$ and therefore is equal to $4^2 - 2 \cdot 3 = 10$.
In general, given $f(x)=a_n x^n + a_{n-1} x^{n-1} + \ldots + a_1 x + a_0$, we have that $a_m = \displaystyle (-1)^{n-m} a_n \sum_{\mathrm{i>j>\cdots>k}} \underbrace{\lambda_i \lambda_j \cdots \lambda_k}_{(n - m)\ \text{times}} $ where $\lambda_w$ is a root of $f(x)$. These relationships are called Vieta’s formulae.
The benefit we get in using this approach is that we do not have to compute the roots of the polynomial $p(x)$.
Generalizing the problem
What if the problem asked to compute $\lambda_1^3 + \lambda_2^3$? We can once again factor $\lambda_1^3 + \lambda_2^3$ as $(\lambda_1 + \lambda_2)(\lambda_1^2 + \lambda_2^2 - \lambda_1\lambda_2)$, getting $4(10 - 3) = 28$. We can check the result using the roots we had already computed: $\lambda_1^3 + \lambda_2^3 = 3^3 + 1^3 = 28$.
It is worth noting that, in order to calculate $\lambda_1^3 + \lambda_2^3$, we had to make use of $\lambda_1^2 + \lambda_2^2$ and $\lambda_1 + \lambda_2$.
So, is there a generalization of this kind of relationship between the sums of powers of the roots of a polynomial? Of course there is, and it is the Newton-Girard identity. What I was seeking in the first place was its proof, that I’m now going to explain.
Newton-Girard identity
Newton’s identity states that given $e_m = |\frac{a_{n-m}}{a_n}|$ and $P_k = \lambda_1^k + \lambda_2^k + \ldots + \lambda_n^k = \displaystyle \sum_{i=1}^n \lambda_i^k$, the following identity holds:
\[m e_m = \displaystyle \sum_{i=1}^{m} (-1)^{i-1} e_{m-i} P_i\]We can even rearrange this identity by noticing that $e_0$ must always be equal to $1$ and get:
\[m e_m = \displaystyle \sum_{i=1}^{m-1} (-1)^{i-1} e_{m-i} P_i + (-1)^{m-1} P_m\]Hence, we obtain:
\[P_m = (-1)^m \left( \displaystyle \sum_{i=1}^{m-1} (-1)^{i-1} e_{m-i} P_i - m e_m \right)\]This proves the relationship between all the sums of the powers of the roots of a polynomial we wanted to prove to ourselves earlier and gives us a powerful tool to compute the result of the kind of problems we discussed earlier.
Proof of Newton-Girard identity
The following proof makes use of calculus, Taylor-Maclaurin series expansion, Vieta’s formulas, the $n$-th derivative of the natural logarithm and Leibniz’s rule.1
First step: defining a polynomial $p(x)$
The first thing we do is defining a polynomial $p(x) = \displaystyle \prod_{i=1}^n \left(1 + \lambda_i x \right)$. It is worth noting that $p(x)$ is equal to $e_0 + e_1 x + e_2 x^2 + \cdots + e_n x^n$. This expression can also be expressed as an infinite sum, given that $e_k = 0$ for $k > n$, therefore giving us the following identity:
\[p(x) = \displaystyle \sum_{i=0}^\infty e_i x^i\]Second step: defining the function $g(x)$
Then, we take the natural logarithm of the polynomial $p(x)$, getting:
\[\ln(p(x)) = \displaystyle \sum_{i=1}^n \ln(1+\lambda_i x)\]Hence, we compute the first derivative of each side of the equation and we define it as $g(x)$:
\[g(x)=\dfrac{\dot p(x)}{p(x)}=\displaystyle \sum_{i=1}^n \frac{\lambda_i}{1 + \lambda_i x}\]It is easily provable by induction that the following identity holds:
\[\overset{i}{\dot g}(x)=(-1)^i i! \displaystyle \sum_{j=1}^n \left[ \left( \frac{\lambda_j}{1+\lambda_j x} \right) ^{i+1} \right]\]If we set $x$ to be equal to $0$, we get:
\[\overset{i}{\dot g}(0)=(-1)^i i! \displaystyle \sum_{j=1}^n \lambda_j^{i+1}=(-1)^i P_{i+1}\]Third step: comparing $p(x)$ with its own Taylor-Maclaurin series
The polynomial $p(x)$ is also representable by its own Taylor-Maclaurin series (i.e. its Taylor series with $a$ set to be equal to $0$), which is $\displaystyle \sum_{i=0}^\infty \frac{\overset{i}{\dot p}(0)}{i!} x^i$.
Each term of the series must coincide with its corresponding term we found in the first step.
Hence, we get:
\[e_i = \frac{\overset{i}{\dot p}(0)}{i!} \Longrightarrow \overset{i}{\dot p}(0) = e_i i!\]Fourth step: taking the $i$-th derivative of $p(x)$
Due to the fact that we defined $g(x)$ as $\frac{\dot p(x)}{p(x)}$, we also know that $\dot p(x) = p(x) g(x)$. Taking the $n$-th derivative using the Leibniz’s rule, we get:
\[\overset{i}{\dot p}(x) = \displaystyle \sum_{j=1}^{i} \binom{i-1}{j-1} \overset{i-j}{\dot p}(x) \overset{j-1}{\dot g}(x)\]Hence, setting $x$ to be equal to $0$:
\[\overset{i}{\dot p}(0) = \displaystyle \sum_{j=1}^{i} \binom{i-1}{j-1} \overset{i-j}{\dot p}(0) \overset{j-1}{\dot g}(0)\]Final step: comparing the $i$-th derivative of $p(0)$
If we compare the $i$-th derivative of $p(0)$ we found in the third step and the one we found in the fourth step, we get:
\[e_i i! = \displaystyle \sum_{j=1}^{i} \binom{i-1}{j-1} \overset{i-j}{\dot p}(0) \overset{j-1}{\dot g}(0)\]Hence, by replacing all the terms with the corresponding ones we found in the third step and the second step and simplifying the expression we get, the following identity holds:
\[i e_i = \displaystyle \sum_{j=1}^{i} (-1)^{j-1} e_{i-j} P_j\] \[\tag*{$\blacksquare$}\]Application to the stated problem
We had to compute $P_2 = \lambda_1^2 + \lambda_2^2$ given that $\lambda_1$ and $\lambda_2$ are the roots of $p(x)=x^2-4x+3$.
Comparing the coefficients of $x$ in $p(x)$, we get $e_0 = 1$, as we’d already said earlier, $e_1 = 4$ and $e_2=3$.
Using the Newton-Girard identity, we notice that:
\[2 e_2 = e_1 P_1 - e_0 P_2 \Longrightarrow P_2 = e_1 P_1 - 2 e_2\]$P_1$ is the same as $e_1$, hence, rearranging the expression, we obtain:
\[P_2 = {e_1}^2 - 2 e_2 = 4^2 - 2 \cdot 3 = 10\]We can follow the same steps to compute $P_3 = \lambda_1^3 + \lambda_2^3$:
\[P_3 = 3 e_3 - e_2 P_1 + e_1 P_2\]Due to the fact that $e_k = 0$ for $k > n$, $e_3$ must be equal to $0$. Therefore, we obtain:
\[P_3 = - e_2 P_1 + e_1 P_2 = - 3 \cdot 4 + 4 \cdot 10 = 28\]In conclusion, we have found a generalized solution for the kind of problems we’d stated in the first place. Newton, we did it, once again!