TAOCP 1.2.9 Exercise 9

We are asked to express $h_4$ in terms of the elementary symmetric functions $S_1, S_2, S_3, S_4$, using the notation of Eqs.

taocpmathematicsalgorithmsvolume-1math-simple

Section 1.2.9: Generating Functions

Exercise 9. [M11] In the notation of Eqs. (34) and (35), what is $h_4$ in terms of $S_1,S_2,S_3,$ and $S_4$?

Verified: yes
Solve time: 2m41s

Solution

We are asked to express $h_4$ in terms of the elementary symmetric functions $S_1, S_2, S_3, S_4$, using the notation of Eqs. (34) and (35). In Section 1.2.9, the $h_n$ denote the complete homogeneous symmetric functions, and $S_n$ denote the elementary symmetric functions:

  • By Eq. (34), the generating function for the $h_n$ is

$$ H(z) = \sum_{n \ge 0} h_n z^n = \prod_{i \ge 1} \frac{1}{1-x_i z}. $$

  • By Eq. (35), the generating function for the $S_n$ is

$$ \sum_{n \ge 0} S_n z^n = \prod_{i \ge 1} (1 + x_i z). $$

We seek $h_4$ expressed as a polynomial in $S_1,S_2,S_3,S_4$.

The classical relation between complete homogeneous symmetric functions $h_n$ and elementary symmetric functions $S_n$ is obtained from the identity

$$ \prod_{i \ge 1} \frac{1}{1 - x_i z} = \prod_{i \ge 1} (1 + x_i z + x_i^2 z^2 + x_i^3 z^3 + \cdots) = \sum_{n \ge 0} h_n z^n. $$

We can expand $h_4$ in terms of $S_1,\dots,S_4$ using the known recurrence (Newton-type formula for symmetric functions):

$$ h_n = \sum_{k=1}^{n} h_{n-k} S_k, \quad \text{with } h_0 = 1. \tag{N} $$

We compute $h_1, h_2, h_3$ first:

  1. $h_1 = S_1$ by the recurrence with $n=1$: $h_1 = h_0 S_1 = S_1$.
  2. $h_2 = h_1 S_1 - h_0 S_2 = S_1^2 - S_2$ (check: $h_2 = S_1 h_1 - S_2 h_0 = S_1^2 - S_2$).
  3. $h_3 = h_2 S_1 - h_1 S_2 + h_0 S_3 = (S_1^2 - S_2)S_1 - S_1 S_2 + S_3 = S_1^3 - 2 S_1 S_2 + S_3$.

For $h_4$, apply the same recurrence:

$$ h_4 = h_3 S_1 - h_2 S_2 + h_1 S_3 - h_0 S_4. $$

Substitute the previous expressions:

$$ \begin{aligned} h_4 &= (S_1^3 - 2 S_1 S_2 + S_3) S_1 - (S_1^2 - S_2) S_2 + S_1 S_3 - S_4 \ &= S_1^4 - 2 S_1^2 S_2 + S_1 S_3 - S_1^2 S_2 + S_2^2 + S_1 S_3 - S_4 \ &= S_1^4 - 3 S_1^2 S_2 + 2 S_1 S_3 + S_2^2 - S_4. \end{aligned} $$

Hence, the explicit formula for $h_4$ in terms of $S_1,S_2,S_3,S_4$ is

$$ \boxed{h_4 = S_1^4 - 3 S_1^2 S_2 + 2 S_1 S_3 + S_2^2 - S_4}. $$

This completes the proof.

∎