Derivation of the identities Newton's identities

1 derivation of identities

1.1 special case n = k
1.2 comparing coefficients in series
1.3 telescopic sum of symmetric function identities

derivation of identities

each of newton s identities can checked elementary algebra; however, validity in general needs proof. here possible derivations.

from special case n = k

one can obtain k-th newton identity in k variables substitution into

∏

i
=
1


k


(
t
−

x

i


)
=

∑

i
=
0


k


(
−
1

)

k
−
i



e

k
−
i


(

x

1


,
…
,

x

k


)

t

i




{\displaystyle \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 t gives

0
=

∑

i
=
0


k


(
−
1

)

k
−
i



e

k
−
i


(

x

1


,
…
,

x

k


)



x

j




i




for 

1
≤
j
≤
k


{\displaystyle 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 on j gives

0
=
(
−
1

)

k


k

e

k


(

x

1


,
…
,

x

k


)
+

∑

i
=
1


k


(
−
1

)

k
−
i



e

k
−
i


(

x

1


,
…
,

x

k


)

p

i


(

x

1


,
…
,

x

k


)
,


{\displaystyle 0=(-1)^{k}ke_{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 terms i = 0 taken out of sum because p0 (usually) not defined. equation gives k-th newton identity in k variables. since identity of symmetric polynomials (homogeneous) of degree k, validity number of variables follows validity k variables. concretely, identities in n < k variables can deduced setting k − n variables zero. k-th newton identity in n > k variables contains more terms on both sides of equation 1 in k variables, validity assured if coefficients of monomial match. because no individual monomial involves more k of variables, monomial survive substitution of 0 set of n − k (other) variables, after equality of coefficients 1 arises in k-th newton identity in k (suitably chosen) variables.

comparing coefficients in series

another derivation can obtained computations in ring of formal power series r[[t]], r z[x1,…, xn], ring of polynomials in n variables x1,…, xn on integers.

starting again basic relation

∏

i
=
1


n


(
t
−

x

i


)
=

∑

k
=
0


n


(
−
1

)

k



a

k



t

n
−
k




{\displaystyle \prod _{i=1}^{n}(t-x_{i})=\sum _{k=0}^{n}(-1)^{k}a_{k}t^{n-k}}

and reversing polynomials substituting 1/t t , multiplying both sides t remove negative powers of t, gives

∏

i
=
1


n


(
1
−

x

i


t
)
=

∑

k
=
0


n


(
−
1

)

k



a

k



t

k


.


{\displaystyle \prod _{i=1}^{n}(1-x_{i}t)=\sum _{k=0}^{n}(-1)^{k}a_{k}t^{k}.}

(the above computation should performed in field of fractions of r[[t]]; alternatively, identity can obtained evaluating product on left side)

swapping sides , expressing ai elementary symmetric polynomials stand gives identity

∑

k
=
0


n


(
−
1

)

k



e

k


(

x

1


,
…
,

x

n


)

t

k


=

∏

i
=
1


n


(
1
−

x

i


t
)
.


{\displaystyle \sum _{k=0}^{n}(-1)^{k}e_{k}(x_{1},\ldots ,x_{n})t^{k}=\prod _{i=1}^{n}(1-x_{i}t).}

one formally differentiates both sides respect t, , (for convenience) multiplies t, obtain

∑

k
=
0


n


(
−
1

)

k


k

e

k


(

x

1


,
…
,

x

n


)

t

k





=
t

∑

i
=
1


n



[
(
−

x

i


)

∏

j
≠
i


(
1
−

x

j


t
)
]







=
−

(

∑

i
=
1


n






x

i


t


1
−

x

i


t



)


∏

j
=
1


n


(
1
−

x

j


t
)






=
−

[

∑

i
=
1


n



∑

j
=
1


∞


(

x

i


t

)

j


]


[

∑

ℓ
=
0


n


(
−
1

)

ℓ



e

ℓ


(

x

1


,
…
,

x

n


)

t

ℓ


]







=

[

∑

j
=
1


∞



p

j


(

x

1


,
…
,

x

n


)

t

j


]


[

∑

ℓ
=
0


n


(
−
1

)

ℓ
−
1



e

ℓ


(

x

1


,
…
,

x

n


)

t

ℓ


]

,






{\displaystyle {\begin{aligned}\sum _{k=0}^{n}(-1)^{k}ke_{k}(x_{1},\ldots ,x_{n})t^{k}&=t\sum _{i=1}^{n}\left[(-x_{i})\prod \nolimits _{j\neq i}(1-x_{j}t)\right]\\&=-\left(\sum _{i=1}^{n}{\frac {x_{i}t}{1-x_{i}t}}\right)\prod \nolimits _{j=1}^{n}(1-x_{j}t)\\&=-\left[\sum _{i=1}^{n}\sum _{j=1}^{\infty }(x_{i}t)^{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{aligned}}}

where polynomial on right hand side first rewritten rational function in order able factor out product out of summation, fraction in summand developed series in t, using formula

x

1
−
x



=
x
+

x

2


+

x

3


+

x

4


+

x

5


+
⋯


{\displaystyle {\frac {x}{1-x}}=x+x^{2}+x^{3}+x^{4}+x^{5}+\cdots }

,

and coefficient of each t  collected, giving power sum. (the series in t formal power series, may alternatively thought of series expansion t sufficiently close 0, more comfortable that; in fact 1 not interested in function here, in coefficients of series.) comparing coefficients of t on both sides 1 obtains

(
−
1

)

k


k

e

k


(

x

1


,
…
,

x

n


)
=

∑

j
=
1


k


(
−
1

)

k
−
j
−
1



p

j


(

x

1


,
…
,

x

n


)

e

k
−
j


(

x

1


,
…
,

x

n


)
,


{\displaystyle (-1)^{k}ke_{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 k-th newton identity.

as telescopic sum of symmetric function identities

the following derivation, given in (mead, 1992), formulated in ring of symmetric functions clarity (all identities independent of number of variables). fix k > 0, , define symmetric function r(i) 2 ≤ i ≤ k sum of distinct monomials of degree k obtained multiplying 1 variable raised power i k − i distinct other variables (this monomial symmetric function mγ γ hook shape (i,1,1,…1)). in particular r(k) = pk; r(1) description amount of ek, case excluded since here monomials no longer have distinguished variable. products piek−i can expressed in terms of r(j) first , last case being special. 1 has

p

i



e

k
−
i


=
r
(
i
)
+
r
(
i
+
1
)


for 

1
<
i
<
k


{\displaystyle p_{i}e_{k-i}=r(i)+r(i+1)\quad {\text{for }}1<i<k}

since each product of terms on left involving distinct variables contributes r(i), while variable pi occurs among variables of term ek−i contributes r(i + 1), , terms on right obtained once. i = k 1 multiplies e0 = 1, giving trivially

p

k



e

0


=

p

k


=
r
(
k
)


{\displaystyle p_{k}e_{0}=p_{k}=r(k)}

.

finally product p1ek−1 i = 1 gives contributions r(i + 1) = r(2) other values i < k, remaining contributions produce k times each monomial of ek, since 1 of variables may come factor p1; thus

p

1



e

k
−
1


=
k

e

k


+
r
(
2
)


{\displaystyle p_{1}e_{k-1}=ke_{k}+r(2)}

.

the k-th newton identity obtained taking alternating sum of these equations, in terms of form r(i) cancel out.