Newton's identities

Formulation in terms of symmetric polynomials Let x1, ..., xn be variables, denote for k ≥ 1 by pk(x1, ..., xn) the k-th power sum: : p_k(x_1,\ldots,x_n)=\sum_{i=1}^n x_i^k = x_1^k+\cdots+x_n^k, and for k ≥ 0 denote by ek(x1, ..., xn) the elementary symmetric polynomial (that is, the sum of all distinct products of k distinct variables), so : \begin{align} e_0(x_1, \ldots, x_n) &= 1,\\ e_1(x_1, \ldots, x_n) &= x_1 + x_2 + \cdots + x_n,\\ e_2(x_1,\ldots,x_n) &= \sum_{1 \leq in.\\ \end{align} Then Newton's identities can be stated as : ke_k(x_1,\ldots,x_n) = \sum_{i=1}^k(-1)^{i-1} e_{k - i} (x_1, \ldots, x_n) p_i(x_1, \ldots, x_n), valid for all . Also, one has : 0 = \sum_{i=k-n}^k(-1)^{i-1} e_{k - i} (x_1, \ldots, x_n) p_i(x_1, \ldots, x_n), for all . Concretely, one gets for the first few values of k: : \begin{align} e_1(x_1, \ldots, x_n) &= p_1(x_1, \ldots, x_n),\\ 2e_2(x_1, \ldots, x_n) &= e_1(x_1, \ldots, x_n)p_1(x_1, \ldots, x_n) - p_2(x_1, \ldots, x_n),\\ 3e_3(x_1, \ldots, x_n) &= e_2(x_1, \ldots, x_n)p_1(x_1, \ldots, x_n) - e_1(x_1, \ldots, x_n)p_2(x_1, \ldots, x_n) + p_3(x_1, \ldots, x_n). \end{align} The form and validity of these equations do not depend on the number n of variables (although the point where the left-hand side becomes 0 does, namely after the n-th identity), which makes it possible to state them as identities in the ring of symmetric functions. In that ring one has :\begin{align} e_1 &= p_1,\\ 2e_2 &= e_1p_1-p_2 = p_1^2-p_2,\\ 3e_3 &= e_2p_1 - e_1p_2 + p_3 = \tfrac12 p_1^3-\tfrac32p_1p_2+p_3,\\ 4e_4 &= e_3p_1 - e_2p_2 + e_1p_3 - p_4 = \tfrac16p_1^4 - p_1^2p_2 + \tfrac43p_1p_3+\tfrac12p_2^2-p_4,\\ \end{align} and so on; here the left-hand sides never become zero. These equations allow to recursively express the ei in terms of the pk; to be able to do the inverse, one may rewrite them as :\begin{align} p_1 &= e_1,\\ p_2 &= e_1p_1-2e_2 = e_1^2 - 2e_2,\\ p_3 &= e_1p_2 - e_2p_1 + 3e_3 = e_1^3-3e_1e_2+3e_3,\\ p_4 &= e_1p_3 - e_2p_2 + e_3p_1 - 4e_4 = e_1^4-4e_1^2e_2+4e_1e_3+2e_2^2-4e_4, \\ & {}\ \ \vdots \end{align} In general, we have : p_k(x_1,\ldots,x_n) = (-1)^{k-1}ke_k(x_1,\ldots,x_n)+\sum_{i=1}^{k-1}(-1)^{k-1+i} e_{k - i} (x_1, \ldots, x_n) p_i(x_1, \ldots, x_n), valid for all n ≥k ≥ 1. Also, one has : p_k(x_1,\ldots,x_n) = \sum_{i=k-n}^{k-1}(-1)^{k-1+i} e_{k - i} (x_1, \ldots, x_n) p_i(x_1, \ldots, x_n), for all k > n ≥ 1. Application to the roots of a polynomial The polynomial with roots xi may be expanded as : \prod_{i=1}^n (x - x_i) = \sum_{k=0}^n (-1)^k e_k x^{n-k}, where the coefficients e_k(x_1,\ldots,x_n) are the symmetric polynomials defined above. Given the power sums of the roots : p_k(x_1,\ldots,x_n)= \sum_{i=1}^n x_i^k, the coefficients of the polynomial with roots x_1,\ldots,x_n may be expressed recursively in terms of the power sums as :\begin{align} e_0 &= 1,\\[4pt] -e_1 &=-p_1,\\[4pt] e_2 &= \frac{1}{2}(e_1 p_1 - p_2),\\[4pt] -e_3 &=-\frac{1}{3}(e_2 p_1 - e_1 p_2 + p_3),\\[4pt] e_4 &= \frac{1}{4}(e_3 p_1 - e_2 p_2 + e_1 p_3 - p_4), \\ & {} \ \ \vdots \end{align} Formulating polynomials in this way is useful in using the method of Delves and Lyness to find the zeros of an analytic function. Application to the characteristic polynomial of a matrix When the polynomial above is the characteristic polynomial of a matrix \mathbf{A} (in particular when \mathbf{A} is the companion matrix of the polynomial), the roots x_i are the eigenvalues of the matrix, counted with their algebraic multiplicity. For any positive integer k, the matrix \mathbf{A}^k has as eigenvalues the powers x_i^k, and each eigenvalue x_i of \mathbf{A} contributes its multiplicity to that of the eigenvalue x_i^k of \mathbf{A}^k. Then the coefficients of the characteristic polynomial of \mathbf{A}^k are given by the elementary symmetric polynomials in those powers x_i^k. In particular, the sum of the x_i^k, which is the k-th power sum p_k of the roots of the characteristic polynomial of \mathbf{A}, is given by its trace: p_k = \operatorname{tr} ( \mathbf{A}^k )\,. The Newton identities now relate the traces of the powers \mathbf{A}^k to the coefficients of the characteristic polynomial of \mathbf{A}. Using them in reverse to express the elementary symmetric polynomials in terms of the power sums, they can be used to find the characteristic polynomial by computing only the powers \mathbf{A}^k and their traces. This computation requires computing the traces of matrix powers \mathbf{A}^k and solving a triangular system of equations. Both can be done in complexity class NC (solving a triangular system can be done by divide-and-conquer). Therefore, characteristic polynomial of a matrix can be computed in NC. By the Cayley–Hamilton theorem, every matrix satisfies its characteristic polynomial, and a simple transformation allows to find the adjugate matrix in NC. Rearranging the computations into an efficient form leads to the Faddeev–LeVerrier algorithm (1840), a fast parallel implementation of it is due to L. Csanky (1976). Its disadvantage is that it requires division by integers, so in general the field should have characteristic 0. Relation with Galois theory For a given n, the elementary symmetric polynomials ek(x1,...,xn) for k = 1,..., n form an algebraic basis for the space of symmetric polynomials in x1,.... xn: every polynomial expression in the xi that is invariant under all permutations of those variables is given by a polynomial expression in those elementary symmetric polynomials, and this expression is unique up to equivalence of polynomial expressions. This is a general fact known as the fundamental theorem of symmetric polynomials, and Newton's identities provide explicit formulae in the case of power sum symmetric polynomials. Applied to the monic polynomial t^n+\sum_{k=1}^n (-1)^k a_k t^{n-k} with all coefficients ak considered as free parameters, this means that every symmetric polynomial expression S(x1,...,xn) in its roots can be expressed instead as a polynomial expression P(a1,...,an) in terms of its coefficients only, in other words without requiring knowledge of the roots. This fact also follows from general considerations in Galois theory (one views the ak as elements of a base field with roots in an extension field whose Galois group permutes them according to the full symmetric group, and the field fixed under all elements of the Galois group is the base field). The Newton identities also permit expressing the elementary symmetric polynomials in terms of the power sum symmetric polynomials, showing that any symmetric polynomial can also be expressed in the power sums. In fact the first n power sums also form an algebraic basis for the space of symmetric polynomials. == Related identities ==

There are a number of (families of) identities that, while they should be distinguished from Newton's identities, are very closely related to them. A variant using complete homogeneous symmetric polynomials Denoting by hk the complete homogeneous symmetric polynomial (that is, the sum of all monomials of degree k), the power sum polynomials also satisfy identities similar to Newton's identities, but not involving any minus signs. Expressed as identities of in the ring of symmetric functions, they read :kh_k = \sum_{i=1}^kh_{k-i}p_i, valid for all n ≥ k ≥ 1. Contrary to Newton's identities, the left-hand sides do not become zero for large k, and the right-hand sides contain ever more non-zero terms. For the first few values of k, one has :\begin{align} h_1 &= p_1,\\ 2h_2 &= h_1p_1 + p_2,\\ 3h_3 &= h_2p_1 + h_1p_2 + p_3.\\ \end{align} These relations can be justified by an argument analogous to the one by comparing coefficients in power series given above, based in this case on the generating function identity :\sum_{k=0}^\infty h_k(x_1, \ldots, x_n)t^k = \prod_{i=1}^n\frac1{1 - x_it}. Proofs of Newton's identities, like these given below, cannot be easily adapted to prove these variants of those identities. Expressing elementary symmetric polynomials in terms of power sums As mentioned, Newton's identities can be used to recursively express elementary symmetric polynomials in terms of power sums. Doing so requires the introduction of integer denominators, so it can be done in the ring ΛQ of symmetric functions with rational coefficients: :\begin{align} e_1 &= p_1,\\ e_2 &= \textstyle\frac12p_1^2 - \frac12p_2 &&= \textstyle\frac12 ( p_1^2 - p_2 ),\\ e_3 &= \textstyle\frac16p_1^3 - \frac12p_1 p_2 + \frac13p_3 &&= \textstyle\frac{1}{6} ( p_1^3 - 3 p_1 p_2 + 2 p_3 ),\\ e_4 &= \textstyle\frac1{24}p_1^4 - \frac14p_1^2 p_2 + \frac18p_2^2 + \frac13p_1 p_3 - \frac14p_4 &&= \textstyle\frac1{24} ( p_1^4 - 6 p_1^2 p_2 + 3 p_2^2 + 8 p_1 p_3 - 6 p_4 ),\\ &~~\vdots\\ e_n &= (-1)^n \sum_{m_1 + 2m_2 + \cdots + nm_n = n \atop m_1 \ge 0, \ldots, m_n \ge 0} \prod_{i=1}^n \frac{(-p_i)^{m_i}}{m_i ! \, i^{m_i}} \\ \end{align} and so forth. The general formula can be conveniently expressed as :e_k = \frac{(-1)^k}{k!} B_{k}(- p_1, -1! \, p_2, - 2! \, p_3, \ldots, - (k-1)! \, p_k ), where the Bn is the complete exponential Bell polynomial. This expression also leads to the following identity for generating functions: : \sum_{k=0}^\infty e_k \,t^k = \exp\left(\sum_{k=1}^\infty \frac{(-1)^{k+1}}{k} p_k \,t^k \right). Applied to a monic polynomial, these formulae express the coefficients in terms of the power sums of the roots: replace each ei by ai and each pk by sk. Expressing complete homogeneous symmetric polynomials in terms of power sums The analogous relations involving complete homogeneous symmetric polynomials can be similarly developed, giving equations :\begin{align} h_1 &= p_1,\\ h_2 &= \textstyle\frac12p_1^2 + \frac12p_2 &&= \textstyle\frac12 ( p_1^2 + p_2 ),\\ h_3 &= \textstyle\frac16p_1^3 + \frac12p_1 p_2 + \frac13p_3 &&= \textstyle\frac{1}{6} ( p_1^3 + 3 p_1 p_2 + 2 p_3 ),\\ h_4 &= \textstyle\frac1{24}p_1^4 + \frac14p_1^2 p_2 + \frac18p_2^2 + \frac13p_1 p_3 + \frac14p_4 &&= \textstyle\frac1{24} ( p_1^4 + 6 p_1^2 p_2 + 3 p_2^2 + 8 p_1 p_3 + 6 p_4 ),\\ &~~\vdots\\ h_k &= \sum_{m_1 + 2m_2 + \cdots + km_k = k \atop m_1\ge 0, \ldots, m_k\ge 0} \prod_{i=1}^k \frac{p_i^{m_i}}{m_i ! \, i^{m_i}} \end{align} and so forth, in which there are only plus signs. In terms of the complete Bell polynomial, :h_k = \frac{1}{k!} B_{k}(p_1, 0! \, p_2, 1! \, p_3, \ldots, (k-1)! \, p_k ). These expressions correspond exactly to the cycle index polynomials of the symmetric groups, if one interprets the power sums pi as indeterminates: the coefficient in the expression for hk of any monomial p1m1p2m2...''p'l'm''l is equal to the fraction of all permutations of k that have m1 fixed points, m2 cycles of length 2, ..., and ml cycles of length l. Explicitly, this coefficient can be written as 1/N where N = \prod_{i=1}^l (m_i!\,i^{m_i}); this N is the number permutations commuting with any given permutation  of the given cycle type. The expressions for the elementary symmetric functions have coefficients with the same absolute value, but a sign equal to the sign of , namely (−1)m2+m4+.... It can be proved by considering the following inductive step: :\begin{align} mf(m; m_1, \ldots, m_n) &= f(m-1; m_1 - 1, \ldots, m_n) + \cdots + f(m - n; m_1, \ldots, m_n - 1) \\ m_1\prod_{i=1}^n \frac{1}{i^{m_i} m_i!} + \cdots + nm_n \prod_{i=1}^n \frac{1}{i^{m_i} m_i!} &= m\prod_{i=1}^n \frac{1}{i^{m_i} m_i!} \end{align} By analogy with the derivation of the generating function of the e_n, we can also obtain the generating function of the h_n, in terms of the power sums, as: : \sum_{k=0}^\infty h_k \,t^k = \exp\left(\sum_{k=1}^\infty \frac{p_k}{k} \,t^k \right). This generating function is thus the plethystic exponential of p_1 t = (x_1 + \cdots + x_n)t. Expressing power sums in terms of elementary symmetric polynomials One may also use Newton's identities to express power sums in terms of elementary symmetric polynomials, which does not introduce denominators: :\begin{align} p_1 &= e_1,\\ p_2 &= e_1^2 - 2 e_2,\\ p_3 &= e_1^3 - 3 e_2 e_1 + 3 e_3,\\ p_4 &= e_1^4 - 4 e_2 e_1^2 + 4 e_3 e_1 + 2 e_2^2 - 4 e_4,\\ p_5 &= e_1^5 - 5 e_2 e_1^3 + 5 e_3 e_1^2 + 5 e_2^2 e_1 - 5 e_4 e_1 - 5 e_3e_2 + 5 e_5,\\ p_6 &= e_1^6 - 6 e_2 e_1^4 + 6 e_3 e_1^3 + 9 e_2^2 e_1^2 - 6 e_4 e_1^2 - 12 e_3 e_2 e_1 + 6 e_5 e_1 - 2 e_2^3 + 3 e_3^2 + 6 e_4 e_2 - 6e_6. \end{align} The first four formulas were obtained by Albert Girard in 1629 (thus before Newton). The general formula (for all positive integers m) is: :p_m = (-1)^m m \sum_{r_1 + 2r_2 + \cdots + mr_m = m \atop r_1\ge 0, \ldots, r_m\ge 0} \frac{(r_1 + r_2 + \cdots + r_m - 1)!}{r_1!\,r_2! \cdots r_m!} \prod_{i=1}^m (-e_i)^{r_i}. This can be conveniently stated in terms of ordinary Bell polynomials as :p_m = (-1)^m m \sum_{k=1}^m \frac{1}{k} \hat{B}_{m,k}(-e_1,\ldots,-e_{m-k+1}), or equivalently as the generating function: : \begin{align} \sum_{k=1}^{\infty} (-1)^{k-1} p_k \frac{t^k}{k} & = \ln\left(1+e_1t+e_2t^2+e_3t^3+\cdots\right) \\ & = e_1 t - \frac{1}{2}\left(e_1^2-2e_2\right) t^2 + \frac{1}{3}\left(e_1^3-3e_1e_2+3e_3\right) t^3 + \cdots, \end{align} which is analogous to the Bell polynomial exponential generating function given in the previous subsection. The multiple summation formula above can be proved by considering the following inductive step: :\begin{align} f(m;\; r_1,\ldots,r_n) = {} & f(m - 1;\; r_1 - 1, \cdots, r_n) + \cdots + f(m - n;\; r_1, \ldots, r_n - 1)\\[8pt] = {} & \frac{1}{(r_1 - 1)!\cdots r_n!}(m - 1)(r_1 + \cdots + r_n - 2)! + \cdots \\ & \cdots + \frac{1}{r_1!\cdots(r_n - 1)!}(m - n)(r_1 + \cdots + r_n - 2)!\\[8pt] = {} & \frac{1}{r_1!\cdots r_n!}\left[r_1(m - 1) + \cdots + r_n(m-n)\right]\left[r_1 + \cdots + r_n - 2\right]!\\[8pt] = {} & \frac{1}{r_1!\cdots r_n!}\left[m(r_1 + \cdots + r_n) - m\right]\left[r_1 + \cdots + r_n - 2\right]!\\[8pt] = {} & \frac{m(r_1 + \cdots + r_n - 1)!}{r_1!\cdots r_n!} \end{align} Expressing power sums in terms of complete homogeneous symmetric polynomials Finally one may use the variant identities involving complete homogeneous symmetric polynomials similarly to express power sums in term of them: :\begin{align} p_1 &= + h_1,\\ p_2 &= - h_1^2 + 2 h_2,\\ p_3 &= + h_1^3 - 3 h_2 h_1 + 3 h_3,\\ p_4 &= - h_1^4 + 4 h_2 h_1^2 - 4 h_3 h_1 - 2 h_2^2 + 4 h_4,\\ p_5 &= + h_1^5 - 5 h_2 h_1^3 + 5 h_2^2 h_1 + 5 h_3 h_1^2 - 5 h_3h_2 - 5 h_4 h_1 + 5 h_5,\\ p_6 &= - h_1^6 + 6 h_2 h_1^4 - 9 h_2^2 h_1^2 - 6 h_3 h_1^3 + 2 h_2^3 + 12 h_3 h_2 h_1 + 6 h_4 h_1^2 - 3 h_3^2 - 6 h_4 h_2 - 6 h_1 h_5 + 6h_6,\\ \end{align} and so on. Apart from the replacement of each ei by the corresponding hi, the only change with respect to the previous family of identities is in the signs of the terms, which in this case depend just on the number of factors present: the sign of the monomial \prod_{i=1}^l h_i^{m_i} is −(−1)m1+m2+m3+.... In particular the above description of the absolute value of the coefficients applies here as well. The general formula (for all non-negative integers m) is: :p_m = -\sum_{r_1 + 2r_2 + \cdots + mr_m = m \atop r_1\ge 0, \ldots, r_m \ge 0} \frac{m(r_1 + r_2 + \cdots + r_m - 1)!}{r_1!\,r_2!\cdots r_m!} \prod_{i=1}^m (-h_i)^{r_i} Expressions as determinants One can obtain explicit formulas for the above expressions in the form of determinants, by considering the first n of Newton's identities (or it counterparts for the complete homogeneous polynomials) as linear equations in which the elementary symmetric functions are known and the power sums are unknowns (or vice versa), and apply Cramer's rule to find the solution for the final unknown. For instance taking Newton's identities in the form :\begin{align} e_1 &= 1p_1,\\ 2e_2 &= e_1p_1 - 1p_2,\\ 3e_3 &= e_2p_1 - e_1p_2 + 1p_3,\\ & \,\,\,\vdots \\ ne_n &= e_{n-1}p_1 - e_{n-2} p_2 + \cdots + (-1)^ne_1p_{n - 1} + (-1)^{n - 1}p_n \end{align} we consider p_1, -p_2, p_3, \ldots, (-1)^np_{n-1} and p_n as unknowns, and solve for the final one, giving :\begin{align} (-1)^{n-1}p_n ={} &\begin{vmatrix} 1 & 0 & \cdots & & e_1 \\ e_1 & 1 & 0 & \cdots & 2e_2 \\ e_2 & e_1 & 1 & & 3e_3 \\ \vdots & & \ddots & \ddots & \vdots\\ e_{n - 1} & \cdots & e_2 & e_1 & ne_n \end{vmatrix}\begin{vmatrix} 1 & 0 & \cdots & \\ e_1 & 1 & 0 & \cdots \\ e_2 & e_1 & 1 & \\ \vdots & & \ddots & \ddots \\ e_{n - 1} & \cdots & e_2 & e_1 & 1 \end{vmatrix}^{-1} \\[7pt] p_n = {(-1)^{n-1}} &\begin{vmatrix} 1 & 0 & \cdots & & e_1 \\ e_1 & 1 & 0 & \cdots & 2e_2 \\ e_2 & e_1 & 1 & & 3e_3 \\ \vdots & & \ddots &\ddots & \vdots \\ e_{n - 1} & \cdots & e_2 & e_1 & ne_n \end{vmatrix} \\[7pt] ={} &\begin{vmatrix} e_1 & 1 & 0 & \cdots \\ 2e_2 & e_1 & 1 & 0 & \cdots \\ 3e_3 & e_2 & e_1 & 1 \\ \vdots & & & \ddots & \ddots \\ ne_n & e_{n - 1} & \cdots & & e_1 \end{vmatrix}. \end{align} Solving for e_n instead of for p_n is similar, as the analogous computations for the complete homogeneous symmetric polynomials; in each case the details are slightly messier than the final results, which are (Macdonald 1979, p. 20): :\begin{align} e_n = \frac1{n!}&\begin{vmatrix} p_1 & 1 & 0 & \cdots \\ p_2 & p_1 & 2 & 0 & \cdots \\ \vdots & & \ddots & \ddots \\ p_{n-1} & p_{n-2} & \cdots & p_1 & n-1 \\ p_n & p_{n-1} & \cdots & p_2 & p_1 \end{vmatrix} \\[7pt] p_n = (-1)^{n-1}&\begin{vmatrix} h_1 & 1 & 0 & \cdots \\ 2h_2 & h_1 & 1 & 0 & \cdots \\ 3h_3 & h_2 & h_1 & 1 \\ \vdots & & & \ddots & \ddots \\ nh_n & h_{n-1} & \cdots & & h_1 \end{vmatrix} \\[7pt] h_n = \frac1{n!}&\begin{vmatrix} p_1 & -1 & 0 & \cdots \\ p_2 & p_1 & -2 & 0 & \cdots \\ \vdots & & \ddots & \ddots \\ p_{n - 1} & p_{n-2} & \cdots & p_1 & 1 - n \\ p_n & p_{n-1} & \cdots & p_2 & p_1 \end{vmatrix}. \end{align} Note that the use of determinants makes that the formula for h_n has additional minus signs compared to the one for e_n, while the situation for the expanded form given earlier is opposite. As remarked in (Littlewood 1950, p. 84) one can alternatively obtain the formula for h_n by taking the permanent of the matrix for e_n instead of the determinant, and more generally an expression for any Schur polynomial can be obtained by taking the corresponding immanant of this matrix. == Derivation of the identities ==

Each of Newton's identities can easily be checked by elementary algebra; however, their validity in general needs a proof. Here are some possible derivations. === From the special case n = k === One can obtain the k-th Newton identity in k variables by substitution into : \prod_{i=1}^k (t - x_i) = \sum_{i=0}^k (-1)^{k-i} e_{k-i}(x_1,\ldots,x_k)t^i as follows. Substituting xj for t gives :0= \sum_{i=0}^k (-1)^{k-i} e_{k-i}(x_1,\ldots,x_k){x_j}^i \quad\text{for }1\leq j\leq k Summing over all j gives :0= (-1)^kke_k(x_1,\ldots,x_k)+\sum_{i=1}^k(-1)^{k-i} e_{k-i}(x_1,\ldots,x_k)p_i(x_1,\ldots,x_k), where the terms for i = 0 were taken out of the sum because p0 is (usually) not defined. This equation immediately gives the k-th Newton identity in k variables. Since this is an identity of symmetric polynomials (homogeneous) of degree k, its validity for any number of variables follows from its validity for k variables. Concretely, the identities in n < k variables can be deduced by setting k − n variables to zero. The k-th Newton identity in n > k variables contains more terms on both sides of the equation than the one in k variables, but its validity will be assured if the coefficients of any monomial match. Because no individual monomial involves more than k of the variables, the monomial will survive the substitution of zero for some set of n − k (other) variables, after which the equality of coefficients is one that arises in the k-th Newton identity in k (suitably chosen) variables. Comparing coefficients in series Another derivation can be obtained by computations in the ring of formal power series R, where R is Z[x1,..., xn], the ring of polynomials in n variables x1,..., xn over the integers. Starting again from the basic relation : \prod_{i=1}^n (t - x_i) = \sum_{k=0}^n (-1)^{k} a_k t^{n-k} and "reversing the polynomials" by substituting 1/t for t and then multiplying both sides by tn to remove negative powers of t, gives : \prod_{i=1}^n (1- x_it) = \sum_{k=0}^n (-1)^{k} a_k t^k. (the above computation should be performed in the field of fractions of R; alternatively, the identity can be obtained simply by evaluating the product on the left side) Swapping sides and expressing the ai as the elementary symmetric polynomials they stand for gives the identity :\sum_{k=0}^n (-1)^{k} e_k(x_1,\ldots,x_n) t^k=\prod_{i=1}^n (1- x_it). One formally differentiates both sides with respect to t, and then (for convenience) multiplies by t, to obtain :\begin{align} \sum_{k=0}^n (-1)^{k}k e_k(x_1,\ldots,x_n) t^k &= t \sum_{i=1}^n \left[(-x_i) \prod\nolimits_{j \neq i}(1 - x_jt)\right]\\ &= -\left(\sum_{i=1}^n \frac{x_it}{1 - x_it}\right) \prod\nolimits_{j=1}^n (1 - x_jt)\\ &= -\left[\sum_{i=1}^n \sum_{j=1}^\infty(x_it)^j\right]\left[\sum_{\ell=0}^n (-1)^\ell e_\ell(x_1,\ldots,x_n) t^\ell\right]\\ &= \left[\sum_{j=1}^\infty p_j(x_1, \ldots, x_n)t^j\right] \left[\sum_{\ell=0}^n (-1)^{\ell - 1} e_\ell(x_1, \ldots, x_n) t^\ell\right],\\ \end{align} where the polynomial on the right hand side was first rewritten as a rational function in order to be able to factor out a product out of the summation, then the fraction in the summand was developed as a series in t, using the formula :\frac{X}{1 - X} = X + X^2 + X^3 + X^4 + X^5 + \cdots, and finally the coefficient of each t j was collected, giving a power sum. (The series in t is a formal power series, but may alternatively be thought of as a series expansion for t sufficiently close to 0, for those more comfortable with that; in fact one is not interested in the function here, but only in the coefficients of the series.) Comparing coefficients of tk on both sides one obtains :(-1)^{k}k e_k(x_1,\ldots,x_n) = \sum_{j=1}^k (-1)^{k-j-1} p_j(x_1,\ldots,x_n)e_{k-j}(x_1,\ldots,x_n), which gives the k-th Newton identity. As a telescopic sum of symmetric function identities The following derivation, given essentially in (Mead, 1992), is formulated in the ring of symmetric functions for clarity (all identities are independent of the number of variables). Fix some k > 0, and define the symmetric function r(i) for 2 ≤ i ≤ k as the sum of all distinct monomials of degree k obtained by multiplying one variable raised to the power i with k − i distinct other variables (this is the monomial symmetric function mγ where γ is a hook shape (i,1,1,...,1)). In particular r(k) = pk; for r(1) the description would amount to that of ek, but this case was excluded since here monomials no longer have any distinguished variable. All products ''p'i'e''k−i can be expressed in terms of the r(j) with the first and last case being somewhat special. One has :p_ie_{k-i}=r(i)+r(i+1)\quad\text{for }1 since each product of terms on the left involving distinct variables contributes to r(i), while those where the variable from pi already occurs among the variables of the term from ek−i contributes to r(i + 1), and all terms on the right are so obtained exactly once. For i = k one multiplies by e0 = 1, giving trivially :p_ke_0=p_k=r(k). Finally the product p1ek−1 for i = 1 gives contributions to r(i + 1) = r(2) like for other values i < k, but the remaining contributions produce k times each monomial of ek, since any one of the variables may come from the factor p1; thus :p_1e_{k-1}=ke_k+r(2). The k-th Newton identity is now obtained by taking the alternating sum of these equations, in which all terms of the form r(i) cancel out. Combinatorial proof A short combinatorial proof of Newton's identities was given by Doron Zeilberger in 1984. == See also ==