avewright/proofwiki-math huggingface dataset:
Theorem: Generating Function for Sequence of Harmonic Numbers

Let $\sequence {a_n}$ be the sequence defined as:
:$\forall n \in \N_{> 0}: a_n = H_n$
where $H_n$ denotes the $n$th harmonic number.
That is:
:$\sequence {a_n} = 1, 1 + \dfrac 1 2, 1 + \dfrac 1 2 + \dfrac 1 3, \ldots$
Then the generating function for $\sequence {a_n}$ is given as:
:$\map G z = \dfrac 1 {1 - z} \map \ln {\dfrac 1 {1 - z} }$

Proof:
Take the sequence:
:$S_n = 1, \dfrac 1 2, \dfrac 1 3, \dfrac 1 4, \ldots$
From Generating Function for Sequence of Reciprocals of Natural Numbers, this has the generating function:
:$\map H z = \map \ln {\dfrac 1 {1 - z} }$
By definition, $\sequence {a_n}$ is the sequence of partial sums of $\sequence {a_n}$.
The result follows from Generating Function for Sequence of Partial Sums of Series.
{{qed}}
Theorem: Binomial Theorem for Negative Index and Negative Parameter

Let $n \in \Z_{\ge 0}$ be a positive integer.
Let $z \in \R$ be a real number such that $\size z < 1$.
Then:
{{begin-eqn}}
{{eqn | l = \dfrac 1 {\paren {1 - z}^{n + 1} }
      | r = \sum_{k \mathop \ge 0} \binom {-n - 1} k \paren {-z}^k
      | c = 
}}
{{eqn | r = \sum_{k \mathop \ge 0} \binom {n + k} n z^k
      | c = 
}}
{{end-eqn}}
where $\dbinom {n + k} n$ denotes a binomial coefficient.

Proof:
{{begin-eqn}}
{{eqn | l = \dfrac 1 {\paren {1 - z}^{n + 1} }
      | r = \paren {1 + \paren {-z} }^{- n - 1}
      | c = 
}}
{{eqn | r = \sum_{k \mathop \ge 0} \binom {- n - 1} k \paren {-z}^k
      | c = General Binomial Theorem
}}
{{eqn | r = \sum_{k \mathop \ge 0} \dbinom {n + 1 + k - 1} k \paren {-1}^k \paren {-z}^k
      | c = Negated Upper Index of Binomial Coefficient
}}
{{eqn | r = \sum_{k \mathop \ge 0} \dbinom {n + k} k z^k
      | c = 
}}
{{end-eqn}}
{{qed}}
Theorem: Ultraproduct is Well-Defined

Ultraproduct is well-defined.

Proof:
Specifically, following the definitions on ultraproduct, it is to be proved that:
:$(1) \quad f^\MM$ is well-defined
:$(2) \quad R^\MM$ is well-defined
First of all, we need to prove:
Theorem: Cauchy's Integral Formula/General Result/Corollary

Let $\map G z$ be the generating function for the sequence $\sequence {a_n}$.
Let the coefficient of $z^n$ extracted from $\map G z$ be denoted:
:$\sqbrk {z^n} \map G z := a_n$
Let $\map G z$ be convergent for $z = z_0$ and $0 < r < \cmod {z_0}$.
Then:
:$\sqbrk {z^n} \map G z = \ds \frac 1 {2 \pi i} \oint_{\cmod z \mathop = r} \dfrac {\map G z \d z} {z^{n + 1} }$

Proof:
{{begin-eqn}}
{{eqn | l = \sqbrk {z^n} \map G z
      | r = \frac 1 {n!} \map {G^\paren n} 0
      | c = {{Corollary|Derivative of Generating Function/General Result|disp = Derivative of Generating Function: General Result}}
}}
{{eqn | r = \frac 1 {n!} \paren {\frac {n!} {2 \pi i} \oint_{\partial D} \frac {\map G z} {z^{n + 1} } \rd z}
      | c = Cauchy's Integral Formula for Derivatives
}}
{{eqn | r = \frac 1 {2 \pi i} \oint_{\cmod z \mathop = r} \frac {\map G z \d z} {z^{n + 1} }
      | c = 
}}
{{end-eqn}}
{{qed}}
Theorem: Summation of Products of n Numbers taken m at a time with Repetitions

Let $a, b \in \Z$ be integers such that $b \ge a$.
Let $U$ be a set of $n = b - a + 1$ numbers $\set {x_a, x_{a + 1}, \ldots, x_b}$.
Let $m \in \Z_{>0}$ be a (strictly) positive integer.
Let:
{{begin-eqn}}
{{eqn | l = h_m
      | r = \sum_{a \mathop \le j_1 \mathop \le \mathop \cdots \mathop \le j_m \mathop \le b} \paren {\prod_{k \mathop = 1}^m x_{j_k} }
      | c = 
}}
{{eqn | r = \sum_{a \mathop \le j_1 \mathop \le \mathop \cdots \mathop \le j_m \mathop \le b} x_{j_1} \cdots x_{j_m}
      | c = 
}}
{{end-eqn}}
That is, $h_m$ is the product of all $m$-tuples of elements of $U$ taken $m$ at a time, allowing for repetition.
For $r \in \Z_{> 0}$, let:
:$S_r = \ds \sum_{k \mathop = a}^b {x_k}^r$
Then:
{{begin-eqn}}
{{eqn | l = h_m
      | r = \sum_{\substack {k_1, k_2, \ldots, k_m \mathop \ge 0 \\ k_1 \mathop + 2 k_2 \mathop + \mathop \cdots \mathop + m k_m \mathop = m} } \paren {\prod_{j \mathop = 1}^m \dfrac { {S_j}^{k_j} } {j^{k_j} k_j !} }
      | c = 
}}
{{eqn | r = \sum_{\substack {k_1, k_2, \ldots, k_m \mathop \ge 0 \\ k_1 \mathop + 2 k_2 \mathop + \mathop \cdots \mathop + m k_m \mathop = m} } \dfrac { {S_1}^{k_1} } {1^{k_1} k_1 !} \dfrac { {S_2}^{k_2} } {2^{k_2} k_2 !} \cdots \dfrac { {S_m}^{k_m} } {m^{k_m} k_m !}
      | c = 
}}
{{end-eqn}}

Proof:
=== Lemma 1 ===
{{:Summation of Products of n Numbers taken m at a time with Repetitions/Lemma 1}}
Theorem: Summation of Products of n Numbers taken m at a time with Repetitions

Let $a, b \in \Z$ be integers such that $b \ge a$.
Let $U$ be a set of $n = b - a + 1$ numbers $\set {x_a, x_{a + 1}, \ldots, x_b}$.
Let $m \in \Z_{>0}$ be a (strictly) positive integer.
Let:
{{begin-eqn}}
{{eqn | l = h_m
      | r = \sum_{a \mathop \le j_1 \mathop \le \mathop \cdots \mathop \le j_m \mathop \le b} \paren {\prod_{k \mathop = 1}^m x_{j_k} }
      | c = 
}}
{{eqn | r = \sum_{a \mathop \le j_1 \mathop \le \mathop \cdots \mathop \le j_m \mathop \le b} x_{j_1} \cdots x_{j_m}
      | c = 
}}
{{end-eqn}}
That is, $h_m$ is the product of all $m$-tuples of elements of $U$ taken $m$ at a time, allowing for repetition.
For $r \in \Z_{> 0}$, let:
:$S_r = \ds \sum_{k \mathop = a}^b {x_k}^r$
Then:
{{begin-eqn}}
{{eqn | l = h_m
      | r = \sum_{\substack {k_1, k_2, \ldots, k_m \mathop \ge 0 \\ k_1 \mathop + 2 k_2 \mathop + \mathop \cdots \mathop + m k_m \mathop = m} } \paren {\prod_{j \mathop = 1}^m \dfrac { {S_j}^{k_j} } {j^{k_j} k_j !} }
      | c = 
}}
{{eqn | r = \sum_{\substack {k_1, k_2, \ldots, k_m \mathop \ge 0 \\ k_1 \mathop + 2 k_2 \mathop + \mathop \cdots \mathop + m k_m \mathop = m} } \dfrac { {S_1}^{k_1} } {1^{k_1} k_1 !} \dfrac { {S_2}^{k_2} } {2^{k_2} k_2 !} \cdots \dfrac { {S_m}^{k_m} } {m^{k_m} k_m !}
      | c = 
}}
{{end-eqn}}

Proof:
Let:
{{begin-eqn}}
{{eqn | l = S_1
      | o = :=
      | r = \sum_{i \mathop = a}^b \sum_{j \mathop = a}^i x_i x_j
      | c = 
}}
{{eqn | r = \sum_{j \mathop = a}^b \sum_{i \mathop = j}^b x_i x_j
      | c = Summation of i from 1 to n of Summation of j from 1 to i
}}
{{eqn | r = \sum_{i \mathop = a}^b \sum_{j \mathop = i}^b x_i x_j
      | c = Change of Index Variable of Summation
}}
{{eqn | o = =:
      | r = S_2
      | c = 
}}
{{end-eqn}}
Then:
{{begin-eqn}}
{{eqn | l = 2 S_1
      | r = S_1 + S_2
      | c = 
}}
{{eqn | r = \sum_{i \mathop = a}^b \paren {\sum_{j \mathop = a}^i x_i x_j + \sum_{j \mathop = i}^b x_i x_j}
      | c = 
}}
{{eqn | r = \sum_{i \mathop = a}^b \paren {\paren {\sum_{j \mathop = a}^b x_i x_j} + x_i x_i}
      | c = Sum of Summations over Overlapping Domains: Example
}}
{{eqn | r = \sum_{i \mathop = a}^b \sum_{j \mathop = a}^b x_i x_j + \sum_{i \mathop = a}^b x_i x_i
      | c = Sum of Summations equals Summation of Sum
}}
{{eqn | r = \paren {\sum_{i \mathop = a}^b x_i} \paren {\sum_{j \mathop = a}^b x_j} + \paren {\sum_{i \mathop = a}^b {x_i}^2}
      | c = General Distributivity Theorem and Change of Index Variable of Summation
}}
{{end-eqn}}
The result follows on multiplying by $\dfrac 1 2$.
{{qed}}
Theorem: Summation of Products of n Numbers taken m at a time with Repetitions

Let $a, b \in \Z$ be integers such that $b \ge a$.
Let $U$ be a set of $n = b - a + 1$ numbers $\set {x_a, x_{a + 1}, \ldots, x_b}$.
Let $m \in \Z_{>0}$ be a (strictly) positive integer.
Let:
{{begin-eqn}}
{{eqn | l = h_m
      | r = \sum_{a \mathop \le j_1 \mathop \le \mathop \cdots \mathop \le j_m \mathop \le b} \paren {\prod_{k \mathop = 1}^m x_{j_k} }
      | c = 
}}
{{eqn | r = \sum_{a \mathop \le j_1 \mathop \le \mathop \cdots \mathop \le j_m \mathop \le b} x_{j_1} \cdots x_{j_m}
      | c = 
}}
{{end-eqn}}
That is, $h_m$ is the product of all $m$-tuples of elements of $U$ taken $m$ at a time, allowing for repetition.
For $r \in \Z_{> 0}$, let:
:$S_r = \ds \sum_{k \mathop = a}^b {x_k}^r$
Then:
{{begin-eqn}}
{{eqn | l = h_m
      | r = \sum_{\substack {k_1, k_2, \ldots, k_m \mathop \ge 0 \\ k_1 \mathop + 2 k_2 \mathop + \mathop \cdots \mathop + m k_m \mathop = m} } \paren {\prod_{j \mathop = 1}^m \dfrac { {S_j}^{k_j} } {j^{k_j} k_j !} }
      | c = 
}}
{{eqn | r = \sum_{\substack {k_1, k_2, \ldots, k_m \mathop \ge 0 \\ k_1 \mathop + 2 k_2 \mathop + \mathop \cdots \mathop + m k_m \mathop = m} } \dfrac { {S_1}^{k_1} } {1^{k_1} k_1 !} \dfrac { {S_2}^{k_2} } {2^{k_2} k_2 !} \cdots \dfrac { {S_m}^{k_m} } {m^{k_m} k_m !}
      | c = 
}}
{{end-eqn}}

Proof:
We have that:
:$\ds \sum_{i \mathop = a}^b \sum_{j \mathop = a}^i x_i x_j = \sum_{a \mathop \le j_1 \mathop \le j_2 \mathop \le b} x_{j_1} x_{j_2}$
From Summation of Products of n Numbers taken m at a time with Repetitions:
:$\ds \sum_{a \mathop \le j_1 \mathop \le \cdots \mathop \le j_m \mathop \le b} x_{j_1} \cdots x_{j_m} = \sum_{\substack {k_1, k_2, \ldots, k_m \mathop \ge 0 \\ k_1 \mathop + 2 k_2 \mathop + \cdots \mathop + m k_m \mathop = m} } \dfrac { {S_1}^{k_1} } {1^{k_1} k_1 !} \dfrac { {S_2}^{k_2} } {2^{k_2} k_2 !} \cdots \dfrac { {S_m}^{k_m} } {m^{k_m} k_m !}$
where:
:$S_r = \ds \sum_{k \mathop = a}^b {x_k}^r$ for $r \in \Z_{\ge 0}$.
Setting $m = 2$:
{{begin-eqn}}
{{eqn | l = \sum_{a \mathop \le j_1 \mathop \le j_2 \mathop \le b} x_{j_1} x_{j_2}
      | r = \sum_{\substack {k_1, k_2 \mathop \ge 0 \\ k_1 \mathop + 2 k_2 \mathop = 2} } \dfrac { {S_1}^{k_1} } {1^{k_1} k_1 !} \dfrac { {S_2}^{k_2} } {2^{k_2} k_2 !}
      | c = 
}}
{{eqn | r = \dfrac { {S_1}^2 {S_2}^0} {\paren {1^2 \times 2!} \paren {2^0 \times 0!} } + \dfrac { {S_1}^0 {S_2}^1} {\paren {1^0 \times 0!} \paren {2^1 \times 1!} }
      | c = as $k_1 = 2, k_2 = 0$ and $k_1 = 0, k_2 = 1$ are the only $k_1$ and $k_2$ to fulfil the criteria
}}
{{eqn | r = \frac 1 2 \paren { {S_1}^2 + S_2}
      | c = simplifying
}}
{{end-eqn}}
{{qed}}
Theorem: Derivative of Generating Function for Sequence of Harmonic Numbers

Let $\sequence {a_n}$ be the sequence defined as:
:$\forall n \in \N_{> 0}: a_n = H_n$
where $H_n$ denotes the $n$th harmonic number.
Let $\map G z$ be the generating function for $\sequence {a_n}$:
:$\map G z = \dfrac 1 {1 - z} \map \ln {\dfrac 1 {1 - z} }$
from Generating Function for Sequence of Harmonic Numbers.
Then the derivative of $\map G z$ {{WRT|Differentiation}} $z$ is given by:
:$\map {G'} z = \dfrac 1 {\paren {1 - z}^2} \map \ln {\dfrac 1 {1 - z} } + \dfrac 1 {\paren {1 - z}^2}$

Proof:
{{begin-eqn}}
{{eqn | l = \map {G'} z
      | r = \map {\dfrac \d {\d z} } {\dfrac 1 {1 - z} \map \ln {\dfrac 1 {1 - z} } }
      | c = 
}}
{{eqn | r = \dfrac 1 {1 - z} \map {\dfrac \d {\d z} } {\map \ln {\dfrac 1 {1 - z} } } + \map \ln {\dfrac 1 {1 - z} } \map {\dfrac \d {\d z} } {\dfrac 1 {1 - z} }
      | c = Product Rule for Derivatives
}}
{{eqn | r = \dfrac 1 {1 - z} \paren {\paren {-1} \dfrac {-1} {\paren {1 - z}^2} \paren {\dfrac 1 {1 - z} }^{-1} } + \map \ln {\dfrac 1 {1 - z} } \paren {-1} \paren {\dfrac {-1} {\paren {1 - z}^2} }
      | c = Derivative of Logarithm Function, Chain Rule for Derivatives, Derivative of Power
}}
{{eqn | r = \dfrac 1 {\paren {1 - z}^2} \map \ln {\dfrac 1 {1 - z} } + \dfrac 1 {\paren {1 - z}^2}
      | c = simplifying
}}
{{end-eqn}}
{{qed}}
Theorem: Generating Function for Sequence of Sum over k to n of Reciprocal of k by n-k

Let $\sequence {a_n}$ be the sequence whose terms are defined as:
:$\forall n \in \Z_{\ge 0}: a_n = \ds \sum_{k \mathop = 1}^{n - 1} \dfrac 1 {k \paren {n - k} }$
Then $\sequence {a_n}$ has the generating function $\map G z$ such that:
:$\map G z = \paren {\ln \dfrac 1 {1 - z} }^2$
and whose terms are:
:$a_n = \dfrac {2 H_{n - 1} } n$

Proof:
From Product of Generating Functions:
:$\map G z = \paren {\map {G_1} z}^2$
where $\map {G_1} z$ is the generating function for $\ds \sum_{k \mathop \ge 1} \dfrac 1 k$.
From Generating Function for Sequence of Reciprocals of Natural Numbers:
:$\map {G_1} z = \map \ln {\dfrac 1 {1 - z} }$
Hence:
:$\map G z = \paren {\ln \dfrac 1 {1 - z} }^2$
Differentiating $\map G z$ {{WRT|Differentiation}} $z$ gives:
{{begin-eqn}}
{{eqn | l = \map {G'} z
      | r = \dfrac \d {\d z} \paren {\paren {\ln \dfrac 1 {1 - z} }^2}
      | c = 
}}
{{eqn | r = 2 \ln \dfrac 1 {1 - z} \dfrac \d {\d z} \paren {\ln \dfrac 1 {1 - z} }
      | c = Chain Rule for Derivatives, Derivative of Power
}}
{{eqn | r = 2 \paren {\ln \dfrac 1 {1 - z} } \times \paren {\dfrac 1 {1 - z} }^{-1} \dfrac \d {\d z} \dfrac 1 {1 - z}
      | c = Chain Rule for Derivatives, Derivative of Logarithm Function
}}
{{eqn | r = 2 \paren {\ln \dfrac 1 {1 - z} } \times \paren {\dfrac 1 {1 - z} }^{-1} \times \dfrac {-1} {\paren {1 - z}^2} \map {\dfrac \d {\d z} } {1 - z}
      | c = Chain Rule for Derivatives, Derivative of Power
}}
{{eqn | r = 2 \paren {\ln \dfrac 1 {1 - z} } \times \paren {\dfrac 1 {1 - z} }^{-1} \times \dfrac {-1} {\paren {1 - z}^2} \times \paren {-1}
      | c = Chain Rule for Derivatives, Derivative of Power
}}
{{eqn | r = 2 \paren {\dfrac 1 {1 - z} \ln \dfrac 1 {1 - z} }
      | c = simplifying
}}
{{eqn | r = 2 \sum_{n \mathop \ge 0} H_n z^n
      | c = Generating Function for Sequence of Harmonic Numbers
}}
{{end-eqn}}
Integrating again {{WRT|Integration}} $z$ gives:
{{begin-eqn}}
{{eqn | l = \map G z
      | r = \int_0^z \paren {2 \sum_{n \mathop \ge 0} H_n z^n}
      | c = 
}}
{{eqn | r = 2 \sum_{n \mathop \ge 0} H_n \paren {\int_0^z z^n}
      | c = 
}}
{{eqn | r = 2 \sum_{n \mathop \ge 0} H_n \dfrac {z^{n + 1} } {n + 1}
      | c = Primitive of Power
}}
{{eqn | r = 2 \sum_{n \mathop \ge 1} H_{n - 1} \dfrac {z^n} n
      | c = Translation of Index Variable of Summation
}}
{{end-eqn}}
{{qed}}
Theorem: Summation of Products of n Numbers taken m at a time with Repetitions/Examples/Order 4

:$\ds \sum_{a \mathop \le j_1 \mathop \le j_2 \mathop \le j_3 \mathop \le j_4 \mathop \le b} x_{j_1} x_{j_2} x_{j_3} x_{j_4} = \dfrac { {S_1}^4} {24} + \dfrac { {S_1}^2 S_2} 4 + \dfrac { {S_2}^2} 8 + \dfrac {S_1 S_3} 3 + \dfrac {S_4} 4$
where:
:$\ds S_r := \sum_{k \mathop = a}^b {x_k}^r$.

Proof:
From Summation of Products of n Numbers taken m at a time with Repetitions:
:$\ds \sum_{a \mathop \le j_1 \mathop \le \cdots \mathop \le j_m \mathop \le b} x_{j_1} \cdots x_{j_m} = \sum_{\substack {k_1, k_2, \ldots, k_m \mathop \ge 0 \\ k_1 \mathop + 2 k_2 \mathop + \cdots \mathop + m k_m \mathop = m} } \dfrac { {S_1}^{k_1} } {1^{k_1} k_1 !} \dfrac { {S_2}^{k_2} } {2^{k_2} k_2 !} \cdots \dfrac { {S_m}^{k_m} } {m^{k_m} k_m !}$
where:
:$S_j = \ds \sum_{k \mathop = a}^b {x_k}^j$ for $j \in \Z_{\ge 0}$.
Setting $m = 4$:
{{begin-eqn}}
{{eqn | l = \sum_{a \mathop \le j_1 \mathop \le j_2 \mathop \le j_3 \mathop \le j_4 \mathop \le b} x_{j_1} x_{j_2} x_{j_3} x_{j_4}
      | r = \sum_{\substack {k_1, k_2, k_3, k_4 \mathop \ge 0 \\ k_1 \mathop + 2 k_2 \mathop + 3 k_3 \mathop + 4 k_4 \mathop = 4} } \dfrac { {S_1}^{k_1} } {1^{k_1} k_1 !} \dfrac { {S_2}^{k_2} } {2^{k_2} k_2 !} \dfrac { {S_3}^{k_3} } {3^{k_3} k_3 !} \dfrac { {S_4}^{k_4} } {4^{k_4} k_4 !}
      | c = 
}}
{{end-eqn}}
We need to find all sets of $k_1, k_2, k_3, k_4 \in \Z_{\ge 0}$ such that:
:$k_1 + 2 k_2 + 3 k_3 + 4 k_4 = 4$
Thus $\tuple {k_1, k_2, k_3, k_4}$ can be:
:$\tuple {4, 0, 0, 0}$
:$\tuple {2, 1, 0, 0}$
:$\tuple {0, 2, 0, 0}$
:$\tuple {1, 0, 1, 0}$
:$\tuple {0, 0, 0, 1}$
Hence:
{{begin-eqn}}
{{eqn | l = \sum_{a \mathop \le j_1 \mathop \le j_2 \mathop \le j_3 \mathop \le b} x_{j_1} x_{j_2} x_{j_3}
      | r = \dfrac { {S_1}^4 {S_2}^0 {S_3}^0 {S_4}^0} {\paren {1^4 \times 4!} \paren {2^0 \times 0!} \paren {3^0 \times 0!} \paren {4^0 \times 0!} }
      | c = 
}}
{{eqn | o = 
      | ro= +
      | r = \dfrac { {S_1}^2 {S_2}^1 {S_3}^0 {S_4}^0} {\paren {1^2 \times 2!} \paren {2^1 \times 1!} \paren {3^0 \times 0!} \paren {4^0 \times 0!} }
      | c = 
}}
{{eqn | o = 
      | ro= +
      | r = \dfrac { {S_1}^0 {S_2}^2 {S_3}^0 {S_4}^0} {\paren {1^0 \times 0!} \paren {2^2 \times 2!} \paren {3^0 \times 0!} \paren {4^0 \times 0!} }
      | c = 
}}
{{eqn | o = 
      | ro= +
      | r = \dfrac { {S_1}^1 {S_2}^0 {S_3}^1 {S_4}^0} {\paren {1^1 \times 1!} \paren {2^0 \times 0!} \paren {3^1 \times 1!} \paren {4^0 \times 0!} }
      | c = 
}}
{{eqn | o = 
      | ro= +
      | r = \dfrac { {S_1}^0 {S_2}^0 {S_3}^0 {S_4}^1} {\paren {1^0 \times 0!} \paren {2^0 \times 0!} \paren {3^0 \times 0!} \paren {4^1 \times 1!} }
      | c = 
}}
{{eqn | r = \dfrac { {S_1}^4} {24} + \dfrac { {S_1}^2 S_2} 4 + \dfrac { {S_2}^2} 8 + \dfrac {S_1 S_3} 3 + \dfrac {S_4} 4
      | c = 
}}
{{end-eqn}}
{{qed}}
Theorem: Summation of Products of n Numbers taken m at a time with Repetitions/Recurrence Formula

A recurrence relation for $h_n$ can be given as:
{{begin-eqn}}
{{eqn | l = h_n
      | r = \sum_{k \mathop = 1}^n \dfrac {S_k h_{n - k} } n
      | c = 
}}
{{eqn | r = \dfrac 1 n \paren {S_1 h_{n - 1} + S_2 h_{n - 2} + \cdots S_n h_0}
      | c = 
}}
{{end-eqn}}
for $n \ge 1$.

Proof:
{{begin-eqn}}
{{eqn | l = \map \ln {\map G z}
      | r = \sum_{k \mathop \ge 1} \dfrac {S_k z^k} k
      | c = Summation of Products of n Numbers taken m at a time with Repetitions: Lemma 2
}}
{{eqn | ll= \leadsto
      | l = \map {\dfrac \d {\d z} } {\map \ln {\map G z} }
      | r = \map {\dfrac \d {\d z} } {\sum_{k \mathop \ge 1} \dfrac {S_k z^k} k}
      | c = 
}}
{{eqn | ll= \leadsto
      | l = \dfrac 1 {\map G z} \map {\dfrac \d {\d z} } {\map G z}
      | r = \sum_{k \mathop \ge 1} \map {\dfrac \d {\d z} } {\dfrac {S_k z^k} k}
      | c = Derivative of Logarithm Function, Chain Rule for Derivatives
}}
{{eqn | ll= \leadsto
      | l = \dfrac 1 {\sum_{m \mathop \ge 0} h_m z^m} \sum_{m \mathop \ge 0} \paren {m + 1} h_{m + 1} z^m
      | r = \sum_{k \mathop \ge 1} S_k z^{k - 1}
      | c = Derivative of Generating Function, Power Rule for Derivatives
}}
{{eqn | ll= \leadsto
      | l = \sum_{m \mathop \ge 0} \paren {m + 1} h_{m + 1} z^m
      | r = \sum_{k \mathop \ge 1} S_k z^{k - 1} \sum_{m \mathop \ge 0} h_m z^m
      | c = 
}}
{{end-eqn}}
{{finish|Follows from Product of Generating Functions}}
Theorem: Summation of Products of n Numbers taken m at a time with Repetitions/Lemma 1

Let $\map G z$ be the generating function for the sequence $\sequence {h_m}$.
Then:
{{begin-eqn}}
{{eqn | l = \map G z
      | r = \prod_{k \mathop = a}^b \dfrac 1 {1 - x_k z}
      | c = 
}}
{{eqn | r = \dfrac 1 {\paren {1 - x_a z} \paren {1 - x_{a + 1} z} \cdots \paren {1 - x_b z} }
      | c = 
}}
{{end-eqn}}

Proof:
For each $k \in \set {a, a + 1, \ldots, b}$, the product of $x_k$ taken $m$ at a time is simply ${x_k}^m$.
Thus for $n = 1$ we have:
:$h_m = {x_k}^m$
Let the generating function for such a $\sequence {h_m}$ be $\map {G_k} z$.
From Generating Function for Sequence of Powers of Constant:
:$\map {G_k} z = \dfrac 1 {1 - x_k z}$
By Product of Summations, we have:
:$\ds \sum_{a \mathop \le j_1 \mathop \le \cdots \mathop \le j_m \mathop \le b} x_{j_1} \cdots x_{j_m} = \prod_{k \mathop = a}^b \sum_{j \mathop = 1}^m x_j$
Hence:
{{begin-eqn}}
{{eqn | l = \map G z
      | r = \sum_{k \mathop \ge 0} h_k z^k
      | c = {{Defof|Generating Function}}
}}
{{eqn | r = \prod_{k \mathop = a}^b \dfrac 1 {1 - x_k z}
      | c = Product of Generating Functions: General Rule
}}
{{eqn | r = \dfrac 1 {\paren {1 - x_a z} \paren {1 - x_{a + 1} z} \dotsm \paren {1 - x_b z} }
      | c = 
}}
{{end-eqn}}
{{qed}}
{{Proofread}}
Theorem: Summation of Products of n Numbers taken m at a time with Repetitions/Lemma 2

{{begin-eqn}}
{{eqn | l = \map \ln {\map G z}
      | r = \sum_{k \mathop \ge 1} \dfrac {S_k z^k} k
      | c = 
}}
{{end-eqn}}

Proof:
{{begin-eqn}}
{{eqn | l = \map G z
      | r = \dfrac 1 {\paren {1 - x_a z} \paren {1 - x_{a + 1} z} \cdots \paren {1 - x_b z} }
      | c = Lemma 1
}}
{{eqn | ll= \leadsto
      | l = \map \ln {\map G z}
      | r = \ln \dfrac 1 {1 - x_a z} + \ln \dfrac 1 {1 - x_{a + 1} z} + \cdots + \ln \dfrac 1 {1 - x_b z}
      | c = Sum of Logarithms
}}
{{eqn | r = \paren {\sum_{k \mathop \ge 1} \dfrac { {x_a}^k z^k} k} + \paren {\sum_{k \mathop \ge 1} \dfrac { {x_{a + 1} }^k z^k} k} + \cdots + \paren {\sum_{k \mathop \ge 1} \dfrac { {x_b}^k z^k} k}
      | c = Generating Function for Sequence of Reciprocals of Natural Numbers
}}
{{eqn | r = \sum_{k \mathop \ge 1} \dfrac {z^k} k \paren { {x_a}^k + {x_{a + 1} }^k + \cdots + {x_b}^k}
      | c = 
}}
{{eqn | r = \sum_{k \mathop \ge 1} \dfrac {z^k} k \sum_{j \mathop = a}^b {x_j}^k
      | c = 
}}
{{eqn | r = \sum_{k \mathop \ge 1} \dfrac {S_k z^k} k
      | c = by definition of $S_k$
}}
{{end-eqn}}
{{qed}}
Theorem: Generating Function for Elementary Symmetric Function

Let $U$ be a set of $n$ numbers $\set {x_1, x_2, \ldots, x_n}$.
Let $\map {e_m} U$ be the elementary symmetric function of degree $m$ on $U$:
{{begin-eqn}}
{{eqn | l = \map {e_m} U
      | r = \sum_{1 \mathop \le j_1 \mathop < j_2 \mathop < \mathop \cdots \mathop < j_m \mathop \le n} \paren {\prod_{i \mathop = 1}^m x_{j_i} }
      | c = 
}}
{{eqn | r = \sum_{1 \mathop \le j_1 \mathop < j_2 \mathop < \mathop \cdots \mathop < j_m \mathop \le n} x_{j_1} x_{j_2} \cdots x_{j_m}
      | c = 
}}
{{end-eqn}}
Let $a_m := \map {e_m} U$ for $m = 0, 1, 2, \ldots$
Let $\map G z$ be a generating function for the sequence $\sequence {a_m}$:
:$\ds \map G z = \sum_{m \mathop = 0}^\infty a_m z^m$
Then:
:$\ds \map G z = \prod_{k \mathop = 1}^n \paren {1 + x_k z}$

Proof:
The summation for $\map G z$ is a finite sum $m = 0, 1, \ldots, n$, which settles convergence issues.
Begin with Viète's Formulas:
:$\ds \prod_{k \mathop = a}^b \paren {x - x_k} = x^n + \sum_{m \mathop = 0}^{n - 1} \paren {-1}^{n - m} \map {e_{n - m} } U \, x^m$
Change variables $x = -1 / z$:
{{begin-eqn}}
{{eqn | l = \prod_{k \mathop = 1}^n \paren {-\frac 1 z  - x_k}
      | r = \paren {-z}^{-n} + \sum_{m \mathop = 0}^{n - 1} \paren {-1}^{n - m} \map {e_{n - m} } U \, \paren {-z}^{-m}
}}
{{eqn | ll= \leadsto
      | l = \prod_{k \mathop = 1}^n \paren {1 + x_k z}
      | r = z^n + \sum_{m \mathop = 0}^{n - 1} \map {e_{n - m} } U \, \paren z^{n - m}
      | c = all signs cancel
}}
{{eqn | ll= \leadsto
      | l = \prod_{k \mathop = 1}^n \paren {1 + x_k z}
      | r = \sum_{m \mathop = 0}^n \map {e_m} U \, z^m
}}
{{end-eqn}}
{{qed}}
Theorem: Generating Function for Elementary Symmetric Function

Let $U$ be a set of $n$ numbers $\set {x_1, x_2, \ldots, x_n}$.
Let $\map {e_m} U$ be the elementary symmetric function of degree $m$ on $U$:
{{begin-eqn}}
{{eqn | l = \map {e_m} U
      | r = \sum_{1 \mathop \le j_1 \mathop < j_2 \mathop < \mathop \cdots \mathop < j_m \mathop \le n} \paren {\prod_{i \mathop = 1}^m x_{j_i} }
      | c = 
}}
{{eqn | r = \sum_{1 \mathop \le j_1 \mathop < j_2 \mathop < \mathop \cdots \mathop < j_m \mathop \le n} x_{j_1} x_{j_2} \cdots x_{j_m}
      | c = 
}}
{{end-eqn}}
Let $a_m := \map {e_m} U$ for $m = 0, 1, 2, \ldots$
Let $\map G z$ be a generating function for the sequence $\sequence {a_m}$:
:$\ds \map G z = \sum_{m \mathop = 0}^\infty a_m z^m$
Then:
:$\ds \map G z = \prod_{k \mathop = 1}^n \paren {1 + x_k z}$

Proof:
We have by definition of generating function that:
:$\map G z = \ds \sum_{n \mathop \ge 0} a_n z^n$
We have that:
:$a_0 = 1$
{{explain|We need $a_0 {{=}} 1$ but I can't get my head around as to why at the moment}}
Suppose $n = 1$.
Let $\map G z$ be the generating function for $\sequence {a_m}$ under this condition.
Then:
:$1 \mathop \le j_1 \mathop < j_2 \mathop < \mathop \cdots \mathop < j_m \mathop \le 1$
can be fulfilled by only one set $\set {j_1, j_2, \ldots, j_m}$, that is:
:$j_1 = 1$
Thus in this case:
{{begin-eqn}}
{{eqn | l = a_m
      | r = x_1 \delta_{m 1}
      | c = where $\delta_{m 1}$ is the Kronecker delta.
}}
{{eqn | ll= \leadsto
      | l = \map G z
      | r = \sum_{n \mathop \ge 0} x_1 \delta_{n 1} z^n
      | c = 
}}
{{eqn | ll= \leadsto
      | l = \map G z
      | r = 1 + x_1 z
      | c = 
}}
{{end-eqn}}
Then by Product of Generating Functions, it follows that:
:$\map G z = \paren {1 + x_1 z} \paren {1 + x_2 z} \cdots \paren {1 + x_n z}$
{{finish|Explain exactly how. I'm having difficulty getting my head around this. Help would be appreciated here.}}
Theorem: Newton-Girard Identities/Lemma 1

Let $\map G z$ be the generating function for the sequence $\sequence {h_m}$.
Then:
{{begin-eqn}}
{{eqn | l = \map G z
      | r = \prod_{k \mathop = a}^b \paren {1 + x_k z}
      | c = 
}}
{{eqn | r = \paren {1 + x_a z} \paren {1 + x_{a + 1} z} \cdots \paren {1 + x_b z}
      | c = 
}}
{{end-eqn}}

Proof:
This is an instance of Generating Function for Elementary Symmetric Function.
{{qed}}
Category:Newton-Girard Identities
gtks9s10xucbklmenzhlazwqcxzg73t