Newton Girard formula states that for $k>2$: \begin{equation} p_k=p_{k-1}e_1-p_{k-2}e_2+\cdots +(-1)^{k}p_1e_{k-1}+(-1)^{k+1}ke_{k} \end{equation} where $e_i$ are elementary symmetric functions and $p_0=n$ with $p_k=x_1^k+\cdots+x_n^k$.

I am using induction to prove this result. I am stuck at the inductive step, that is to show:

\begin{equation} p_{k}e_1-p_{k-1}e_2+\cdots +(-1)^{k+1}p_1e_k+(-1)^{k+2}(k+1)e_{k+1}= x_1^{k+1}+\cdots+x_n^{k+1} \end{equation} I am not able to see how I can use my inductive hypothesis in the left hand side of the above expression.

  • 1
    $\begingroup$ I don't think induction on $k$ is that helpful here. The proof I remember involves expanding out the terms $p_i e_{k-i}$, and observing the subsequent cancellation. $\endgroup$ – Rolf Hoyer Apr 19 '15 at 23:45

By way of enrichment here is an alternate formulation using cycle indices.

Recall that the OGF of the cycle index $Z(P_n)$ of the unlabeled set operator $\mathfrak{P}_{=n}$ is given by $$G(w) = \sum_{n\ge 0} Z(P_n) w^n = \exp\left(\sum_{q\ge 1} (-1)^{q+1} a_q \frac{w^q}{q}\right).$$

Differentiating we obtain $$G'(w) = \sum_{n\ge 0} (n+1) Z(P_{n+1}) w^n = G(w) \left(\sum_{q\ge 1} (-1)^{q+1} a_q w^{q-1}\right).$$

Extracting coefficients we thus have $$[w^n] G'(w) = (n+1) Z(P_{n+1}) = \sum_{q=1}^{n+1} (-1)^{q+1} a_q Z(P_{n+1-q})$$ This is apparently due to Lovasz.

Substitute the cycle indices with the variables $X_1$ to $X_m$ to get $$(n+1) Z(P_{n+1})(X_1+\cdots+X_m) \\= \sum_{q=1}^{n+1} (-1)^{q+1} (X_1^q+\cdots+X_m^q) Z(P_{n+1-q})(X_1+\cdots+X_m)$$

This yields $$(n+1) e_{n+1}(X_1,\ldots,X_m) = \sum_{q=1}^{n+1} (-1)^{q+1} p_q(X_1,\ldots,X_m) e_{n+1-q}(X_1,\ldots,X_m).$$

Now a choice of variable names yields the result.

Remark. The identity for $G(w)$ follows from the EGF for the labeled species for permutations where all cycles are marked with a variable indicating length of the cycle.

This yields $$\mathfrak{P} \left(A_1 \mathfrak{C}_{=1}(\mathcal{W}) + A_2 \mathfrak{C}_{=2}(\mathcal{W}) + A_3 \mathfrak{C}_{=3}(\mathcal{W}) + \cdots \right).$$

Translating to generating functions we obtain $$G(w) = \exp\left(a_1 + a_2 \frac{w^2}{2} + a_3 \frac{w^3}{3} + \cdots\right).$$

The fact that $$Z(P_n) = \left.Z(S_n)\right|_{a_q := (-1)^{q+1} a_q}$$ then confirms the claim.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.