0
$\begingroup$

On the Wikipedia page for Newton's identities, the following identity is stated $$ kh_k = \sum_{i=1}^k p_i h_{k-i}, \qquad k \in \mathbb{N} \tag{1} $$ where $h_k(x_1,x_2, \dots, x_n) = \sum_ {\substack{\ell_1+\dots \ell_n=k\\\ell_i \ge 0}} x_1^{\ell_1}x_2^{\ell_2} \dots x_n^{\ell_n}$ is the Complete homogeneous symmetric polynomial (which is the sum of all monomials of total degree $k$), and where $p_k(x_1,x_2, \dots, x_n)=\sum_{i=1}^{n}x_i^k$ is the Power sum symmetric polynomial. The article doesn't include a proof, so I wanted to attempt one.


The RHS of $(1)$ reminded me of the coefficients obtained from a Cauchy product of two power series, which states $$ \left(\sum_{i\ge 0} a_i x^i\right) \cdot \left(\sum_{j\ge0} b_j x^j\right) = \sum_{k\ge 0} \left( \sum_{l=0}^k a_l b_{k-l}\right) x^k $$ which gave me the idea to attempt a solution using generating functions for $h_k, p_k$. For $h_k$, working with formal power series you have the following $$ \sum_{k\ge 0} h_k(x_1,\ldots,x_n)t^k = \prod_{i=1}^n\sum_{j\ge 0}^\infty(x_it)^j = \prod_{i=1}^n\frac1{1-x_it} $$ by expanding the product of the sum and using the geometric series formula. For $p_k$ we get $$ \sum_{k\ge 0}p_k\left(x_1, \dots, x_n\right)t^k =\sum_{i=1}^{n}\sum_{k\ge 0}\left(x_i t\right)^k = \sum_{i=1}^{n} \frac{1}{1-x_i t} $$ So recalling the derivative of a product formula we get \begin{align*} \sum_{k \ge 0} \left[kh_k\left(x_1, \dots, x_n\right)\right]t^k & = t \frac{\mathrm{d}}{\mathrm{d}t} \sum_{k \ge 0} \left[h_k\left(x_1, \dots, x_n\right)\right]t^k\\ & = t \frac{\mathrm{d}}{\mathrm{d}t} \prod_{i=1}^{n} \frac{1}{1-x_i t}\\ & = t\left( \prod_{i=1}^{n} \frac{1}{1-x_i t}\right)\left( \sum_{i=1}^{n} \frac{x_i}{1-x_it}\right)\\ & = \left( \prod_{i=1}^{n} \frac{1}{1-x_i t}\right)\left( \sum_{i=1}^{n} \left[\frac{1}{1-x_it}\color{purple}{-1}\right]\right)\\ & = \left(\sum_{i\ge0}h_i t^i\right)\left(\color{purple}{-n} +\sum_{j\ge0}{p_j} t^j\right)\\ & = \left(\sum_{i\ge0}h_i t^i\right)\left(\sum_{j\ge0}\tilde{p_j} t^j\right) \end{align*} where $\tilde{p_j}(x_1, \dots, x_n) = \begin{cases} -n+p_0 =0 & j=0\\ p_j & j\ge 1 \end{cases}$. So by the Cauchy product formula, we have \begin{align*} \sum_{k \ge 0} \left[kh_k\right]t^k & = \sum_{k \ge 0} \left[\sum_{\ell=\color{green}{0}}^k \tilde{p_\ell }h_{k-\ell}\right]t^k = \sum_{k \ge 0} \left[ \sum_{\ell=\color{green}{1}}^k p_\ell h_{k-\ell}\right]t^k \end{align*} And equating coefficients gives the desired result.


The Wikipedia page mentions that the functions $h_k, p_k$ are studied in commutative algebra and combinatorics, which intuitively makes sense as they carry information about the number of ways you can combine stuff to get a certain quantity. I was wondering if there were some other (possibly simpler) ways of showing this result using some abstract algebra or combinatorics methods. So my question is, does anyone know other ways to show this result? Thanks!

$\endgroup$
1
  • 1
    $\begingroup$ See page 170 of "Classic Algebra" by P. M. Cohn. It is definitely worth checking out. $\endgroup$
    – Dilemian
    Commented Jul 1, 2023 at 13:31

2 Answers 2

2
$\begingroup$

Each $x_1^{\ell_1}x_2^{\ell_2} \dots x_n^{\ell_n}$ monomial in $h_k$ is a monomial in the product $x_j^{s_j}h_{k-s_j}$ where $1\leq s_j\leq\ell_j$ and $1\leq j\leq n$ and there are $\ell_1+\ell_2+\dots\ell_n=k$ such products. Therefore the monomial $x_1^{\ell_1}x_2^{\ell_2} \dots x_n^{\ell_n}$ occurs $k$ times in $\sum_{i=1}^k p_ih_{k-i}$. The result follows.

$\endgroup$
1
$\begingroup$

Generating functions

We need to prove $$ kh_k = \sum_{i=1}^k p_i h_{k-i}. $$ First of all, notice that $$ h_k(x_1, \dots, x_n) = [y^k]\prod\limits_{i=1}^n \frac{1}{1-x_i y} = [y^k]F(y). $$ But at the same time, $$ \log F(y) = \sum\limits_{i=1}^n \log \frac{1}{1-x_i y} = \sum\limits_{i=1}^n \sum\limits_{k=1}^\infty \frac{x_i^k y^k}{k} = \sum\limits_{k=1}^\infty \frac{y^k}{k}p_k(x_1, \dots, x_n). $$ So, we have

$$\begin{align} h_k &= [y^k] F(y), & p_k &= k [y^k] \log F(y). \end{align}$$

If we take the derivative of the logarithm, we will get

$$ (\log F(y))' = \frac{F'(y)}{F(y)} \implies F'(y) = F(y) (\log F(y))'. $$ Looking on the coefficient near $y^{k-1}$ on both sides, and using $[y^{k-1}] F'(y) = k [y^k] F(y)$, we get

$$ [y^{k-1}] F'(y) = k [y^k]F(y) = k h_k $$ and $$\begin{align} [y^{k-1}] F(y) (\log F(y))' &= \sum\limits_{i+j=k-1} [y^j] F(y) [y^i](\log F(y))' \\ &= \sum\limits_{i+j=k-1} h_j (i+1)[y^{i+1}]\log F(y) \\ &= \sum\limits_{i+j=k-1} h_j p_{i+1} = \sum\limits_{i=1}^k p_i h_{k-i}. \end{align}$$

This is somewhat similar to the solution in the post.

Bijection

From combinatorics perspective, let's say that $x_i$ is a formal variable enumerating atoms of type $i$. Then $h_k$ enumerates all $k$-tuples, in which first $l_1$ atoms are of type $1$, succeeded by $l_2$ atoms of type $2$, and so on. Then $k h_k$ is the number of such tuples, in which one of the atoms is "selected".

From this perspective, we can view the right-hand side as an alternative method of enumerating such tuples, in which we independently select the type (say, $j$) and the position (say, $i$) of the selected atom, and account for it (and all atoms of the same type that come before it) in the $x_j^i$ summand of the $p_i$, while all the other atoms come from $h_{k-i}$.

Thus, a maybe more "natural" identity from this bijection's perspective is

$$ k h_k = \sum\limits_{i,j} x_i^j h_{k-j}. $$

This connects with the generating function proof above through the fact that in analytic combinatorics, $y F'(y)$ is the generating function for the objects with a single "selected" atom (e.g. rooted trees), and it corresponds to the identity

$$ y F'(y) = F(y) \sum\limits_{i=1}^n \frac{1}{1-x_i y}, $$

which in turn rewrites back to

$$ \sum\limits_{i=1}^n \frac{1}{1-x_i y} = y(\log F(y))'. $$

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .