nyuuzyou/wikis huggingface dataset:
Summation of Products of n Numbers taken m at a time with Repetitions

== Theorem ==
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:
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:
=== Recurrence Formula ===
=== Inverse Formula ===
=== Corollary ===
== Proof ==
=== Lemma 1 ===
=== Lemma 2 ===
Then:
Thus, by definition of generating function:
:$h_m = \ds \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 !}$
== Examples ==
== Also presented as ==
When usually presented, set $U$ is usually defined to be either $\set {x_0, x_1, \ldots, x_n}$ or $\set {x_1, x_2, \ldots, x_n}$.
This leads to the summation $h_m$ to be defined either as:
:$h_m = \ds \sum_{0 \mathop \le j_1 \mathop \le \mathop \cdots \mathop \le j_m \mathop \le n} \paren {\prod_{k \mathop = 1}^m x_{j_k} }$
or:
:$h_m = \ds\sum_{1 \mathop \le j_1 \mathop \le \mathop \cdots \mathop \le j_m \mathop \le n} \paren {\prod_{k \mathop = 1}^m x_{j_k} }$
and for the summations $S_r$ to be defined as either $\ds \sum_{k \mathop = 0}^n {x_k}^r$ or $\ds \sum_{k \mathop = 1}^n {x_k}^r$ accordingly.
However, this may cause confusion when the indices are presented differently between separate invocations of this general result.
For example, in 's of $1997$:
:in $\S 1.2.3$, $\ds \sum_{k \mathop = 0}^n$ is used for the cases $m = 2$ and $n = 3$
while:
:in $\S 1.2.9$, the same result has been taken over $\ds \sum_{k \mathop = 1}^n$
without explanatory comment.
Hence the decision has been made on to choose to define the set of indices over the general interval $\closedint a b$, to emphasise their essentially arbitrary nature.
== Sources ==
* : $\S 1.2.9$: Generating Functions: $(38)$
Category:Summations
Category:Summation of Products of n Numbers taken m at a time with Repetitions
Summation of Products of n Numbers taken m at a time with Repetitions/Corollary

== Corollary to 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.
Consider the result Summation of Products of n Numbers taken m at a time with Repetitions:
:$\ds \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} } = \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 !} }$
where:
:$S_r = \ds \sum_{k \mathop = a}^b {x_k}^r$
for $r \in \Z_{> 0}$
The number of terms in the summation on the is equal to the number of partitions of the integer $m$.
== Proof ==
Let $m$ be the sum of a number of instances of (strictly) positive integers between $1$ and $m$.
Let the count of instances of $r$ be $k_r$.
Then:
:$m = k_1 \times 1 + k_2 \times 2 + \cdots + k_m \times m$
Thus $k_1 + 2 k_2 \times 2 + \cdots + m k_m$ defines a partition of $m$.
By definition of summation, $\ds \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} }$ should run over all instances of $k_1, k_2, \ldots, k_m$ that fulfil the conditions.
That is, there is a summand for every partition of $m$.
== Examples ==
== Sources ==
* : $\S 1.2.9$: Generating Functions
Category:Summation of Products of n Numbers taken m at a time with Repetitions
Summation of Products of n Numbers taken m at a time with Repetitions/Corollary/Examples/12

== Examples of Corllary to Summation of Products of n Numbers taken m at a time with Repetitions ==
Consider the result 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} \paren {\prod_{k \mathop = 1}^m x_{j_k} } = \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} } \paren {\prod_{j \mathop = 1}^m \dfrac { {S_j}^{k_j} } {j^{k_j} k_j !} }$
where:
:$\ds S_r = \sum_{k \mathop = a}^b {x_k}^r$
for $r \in \Z_{> 0}$
Let $m = 12$.
Then one of the summands on the is:
:$\dfrac {S_1 {S_2}^3 S_5} {240}$
== Proof ==
$12$ can thus be expressed as
:$12 = 5 + 2 + 2 + 2 + 1$
We have that $k_j$ is the number of instances of $j$ in the partition.
Thus setting $k_1 = 1, k_2 = 3, k_5 = 5$:
Hence the summand:
</onlyinclude>
== Sources ==
* : $\S 1.2.9$: Generating Functions
Category:Summation of Products of n Numbers taken m at a time with Repetitions
Summation of Products of n Numbers taken m at a time with Repetitions/Examples/Order 2

== Theorem ==
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}, \dotsc, x_b}$.
Then:
:$\ds \sum_{i \mathop = a}^b \sum_{j \mathop = a}^i x_i x_j = \dfrac 1 2 \paren {\paren {\sum_{i \mathop = a}^b x_i}^2 + \paren {\sum_{i \mathop = a}^b {x_i}^2} }$
== Proof 1 ==
== Proof 2 ==
== Sources ==
* : $\S 1.2.9$: Generating Functions
Category:Summation of Products of n Numbers taken m at a time with Repetitions
Summation of Products of n Numbers taken m at a time with Repetitions/Examples/Order 2/Proof 1

== Theorem ==
== Proof ==
Let:
Then:
The result follows on multiplying by $\dfrac 1 2$.
== Sources ==
* : $\S 1.2.3$: Sums and Products: Example $2$. $(13)$
Category:Summation of Products of n Numbers taken m at a time with Repetitions
Summation of Products of n Numbers taken m at a time with Repetitions/Examples/Order 2/Proof 2

== Theorem ==
== 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$:
Category:Summation of Products of n Numbers taken m at a time with Repetitions
Summation of Products of n Numbers taken m at a time with Repetitions/Examples/Order 3

== Theorem ==
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}$.
Then:
:$\ds \sum_{i \mathop = a}^b \sum_{j \mathop = a}^i \sum_{k \mathop = a}^j x_i x_j x_k = \dfrac { {S_1}^3} 6 + \dfrac {S_1 S_2} 2 + \dfrac {S_3} 3$
where:
:$\ds S_r := \sum_{k \mathop = a}^b {x_k}^r$
== Proof 1 ==
== Proof 2 ==
== Sources ==
* : $\S 1.2.9$: Generating Functions
Category:Summation of Products of n Numbers taken m at a time with Repetitions
Summation of Products of n Numbers taken m at a time with Repetitions/Examples/Order 3/Proof 1

== Theorem ==
== Proof ==
Let:
Also, let:
Hence:
Let:
as calculated above.
Thus:
:$(1): \quad 2 A = A_1 + A_3$
Similarly:
Then:
Let:
as calculated above.
Thus:
:$(2): \quad A_1 + A = A_2 + A_4$
Then:
Now we have that:
and so:
Finally:
== Sources ==
* : $\S 1.2.3$: Sums and Products: Exercise $29$
Category:Summation of Products of n Numbers taken m at a time with Repetitions
Summation of Products of n Numbers taken m at a time with Repetitions/Examples/Order 3/Proof 2

== Theorem ==
== Proof ==
We have that:
:$\ds \sum_{i \mathop = a}^b \sum_{j \mathop = a}^i \sum_{k \mathop = a}^j x_i x_j x_k = \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}$
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 = 3$:
We need to find all sets of $k_1, k_2, k_3 \in \Z_{\ge 0}$ such that:
:$k_1 + 2 k_2 + 3 k_3 = 3$
Thus $\tuple {k_1, k_2, k_3}$ can be:
:$\tuple {3, 0, 0}$
:$\tuple {1, 1, 0}$
:$\tuple {0, 0, 1}$
Hence:
Category:Summation of Products of n Numbers taken m at a time with Repetitions
Summation of Products of n Numbers taken m at a time with Repetitions/Examples/Order 4

== Theorem ==
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}$.
Then:
:$\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$:
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:
== Sources ==
* : $\S 1.2.9$: Generating Functions: Exercise $9$
Category:Summation of Products of n Numbers taken m at a time with Repetitions
Summation of Products of n Numbers taken m at a time with Repetitions/Inverse Formula

== Theorem ==
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:
That is, $h_m$ is the product of all $m$-tuples of elements of $U$ taken $m$ at a time.
For $r \in \Z_{> 0}$, let:
:$S_r = \ds \sum_{j \mathop = a}^b {x_j}^r$
Let $S_m$ be expressed in the form:
:$S_m = \ds \sum_{k_1 \mathop + 2 k_2 \mathop + \mathop \cdots \mathop + m k_m \mathop = m} A_m {h_1}^{k_1} {h_2}^{k_2} \cdots {h_m}^{k_m}$
for $k_1, k_2, \ldots, k_m \ge 0$.
Then :
:$A_m = \paren {-1}^{k_1 + k_2 + \cdots + k_m - 1} \dfrac {m \paren {k_1 + k_2 + \cdots + k_m - 1}! } {k_1! \, k_2! \, \cdots k_m!}$
== Proof ==
Let $\map G z$ be the generating function for the sequence $\sequence {h_m}$.
== Examples ==
== Sources ==
* : $\S 1.2.9$: Generating Functions: Exercise $11$
Category:Summation of Products of n Numbers taken m at a time with Repetitions
Summation of Products of n Numbers taken m at a time with Repetitions/Inverse Formula/Examples

== Examples of Summation of Products of n Numbers taken m at a time with Repetitions: Inverse Formula ==
=== Degree $1$ ===
=== Degree $2$ ===
=== Degree $3$ ===
=== Degree $4$ ===
Category:Summation of Products of n Numbers taken m at a time with Repetitions
Summation of Products of n Numbers taken m at a time with Repetitions/Inverse Formula/Examples/Degree 1

== Example of Summation of Products of n Numbers taken m at a time with Repetitions: Inverse Formula ==
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:
That is, $h_m$ is the product of all $m$-tuples of elements of $U$ taken $m$ at a time.
For $r \in \Z_{> 0}$, let:
:$S_r = \ds \sum_{j \mathop = a}^b {x_j}^r$
Then:
:$S_1 = h_1$
== Proof ==
From Summation of Products of n Numbers taken m at a time with Repetitions: Inverse Formula:
:$S_m = \ds \sum_{k_1 \mathop + 2 k_2 \mathop + \mathop \cdots \mathop + m k_m \mathop = m} \paren {-1}^{k_1 + k_2 + \cdots + k_m - 1} \dfrac {m \paren {k_1 + k_2 + \cdots + k_m - 1}! } {k_1! \, k_2! \, \cdots k_m!} {h_1}^{k_1} {h_2}^{k_2} \cdots {h_m}^{k_m}$
where:
:$k_1 + 2 k_2 + \cdots + m k_m = m$
When $m = 1$ we have only one set of $k_j$:
:$k_1 = 1$
Thus:
== Sources ==
* 
* : $\S 1.2.9$: Generating Functions: Exercise $11$
Category:Summation of Products of n Numbers taken m at a time with Repetitions
Summation of Products of n Numbers taken m at a time with Repetitions/Inverse Formula/Examples/Degree 2

== Example of Summation of Products of n Numbers taken m at a time with Repetitions: Inverse Formula ==
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:
That is, $h_m$ is the product of all $m$-tuples of elements of $U$ taken $m$ at a time.
For $r \in \Z_{> 0}$, let:
:$S_r = \ds \sum_{j \mathop = a}^b {x_j}^r$
Then:
:$S_2 = 2 h_2 - {h_1}^2$
== Proof ==
From Summation of Products of n Numbers taken m at a time with Repetitions: Inverse Formula:
:$S_m = \ds \sum_{k_1 \mathop + 2 k_2 \mathop + \mathop \cdots \mathop + m k_m \mathop = m} \paren {-1}^{k_1 + k_2 + \cdots + k_m - 1} \dfrac {m \paren {k_1 + k_2 + \cdots + k_m - 1}! } {k_1! \, k_2! \, \cdots k_m!} {h_1}^{k_1} {h_2}^{k_2} \cdots {h_m}^{k_m}$
where:
:$k_1 + 2 k_2 + \cdots + m k_m = m$
When $m = 2$ we have two possible sets of $k_j$ that meet the criterion:
:$k_1 = 2, k_2 = 0$
:$k_1 = 0, k_2 = 1$
Thus:
== Sources ==
* 
* : $\S 1.2.9$: Generating Functions: Exercise $11$
Category:Summation of Products of n Numbers taken m at a time with Repetitions
Summation of Products of n Numbers taken m at a time with Repetitions/Inverse Formula/Examples/Degree 3

== Example of Summation of Products of n Numbers taken m at a time with Repetitions: Inverse Formula ==
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:
That is, $h_m$ is the product of all $m$-tuples of elements of $U$ taken $m$ at a time.
For $r \in \Z_{> 0}$, let:
:$S_r = \ds \sum_{j \mathop = a}^b {x_j}^r$
Then:
:$S_3 = 3 h_3 - 3 h_1 h_2 + {h_1}^3$
== Proof ==
From Summation of Products of n Numbers taken m at a time with Repetitions: Inverse Formula:
:$S_m = \ds \sum_{k_1 \mathop + 2 k_2 \mathop + \mathop \cdots \mathop + m k_m \mathop = m} \paren{-1}^{k_1 + k_2 + \cdots + k_m - 1} \dfrac {m \paren{k_1 + k_2 + \cdots + k_m - 1}! } {k_1! \, k_2! \, \cdots k_m!} {h_1}^{k_1} {h_2}^{k_2} \cdots {h_m}^{k_m}$
where:
:$k_1 + 2 k_2 + \cdots + m k_m = m$
We need to find all sets of $k_1, k_2, k_3 \in \Z_{\ge 0}$ such that:
:$k_1 + 2 k_2 + 3 k_3 = 3$
Thus $\tuple{k_1, k_2, k_3}$ can be:
:$\tuple{3, 0, 0}$
:$\tuple{1, 1, 0}$
:$\tuple{0, 0, 1}$
Hence:
== Sources ==
* 
* : $\S 1.2.9$: Generating Functions: Exercise $11$
Category:Summation of Products of n Numbers taken m at a time with Repetitions
Summation of Products of n Numbers taken m at a time with Repetitions/Inverse Formula/Examples/Degree 4

== Example of Summation of Products of n Numbers taken m at a time with Repetitions: Inverse Formula ==
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:
That is, $h_m$ is the product of all $m$-tuples of elements of $U$ taken $m$ at a time.
For $r \in \Z_{> 0}$, let:
:$S_r = \ds \sum_{j \mathop = a}^b {x_j}^r$
Then:
:$S_4 = 4 h_4 - 4 h_1 h_3 - 2 {h_2}^2 + 4 {h_1}^2 h_1 - {h_1}^4$
== Proof ==
From Summation of Products of n Numbers taken m at a time with Repetitions: Inverse Formula:
:$S_m = \ds \sum_{k_1 \mathop + 2 k_2 \mathop + \mathop \cdots \mathop + m k_m \mathop = m} \paren {-1}^{k_1 + k_2 + \cdots + k_m - 1} \dfrac {m \paren {k_1 + k_2 + \cdots + k_m - 1}! } {k_1! \, k_2! \, \cdots k_m!} {h_1}^{k_1} {h_2}^{k_2} \cdots {h_m}^{k_m}$
where:
:$k_1 + 2 k_2 + \cdots + m k_m = m$
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:
== Sources ==
* 
Category:Summation of Products of n Numbers taken m at a time with Repetitions
Summation of Products of n Numbers taken m at a time with Repetitions/Lemma 1

== Theorem ==
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:
That is, $h_m$ is the product of all $m$-tuples of elements of $U$ taken $m$ at a time.
Let $\map G z$ be the generating function for the sequence $\sequence {h_m}$.
Then:
== 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:
== Sources ==
* : $\S 1.2.9$: Generating Functions: Exercise $7$
Category:Summation of Products of n Numbers taken m at a time with Repetitions
Summation of Products of n Numbers taken m at a time with Repetitions/Lemma 2

== Theorem ==
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:
That is, $h_m$ is the product of all $m$-tuples of elements of $U$ taken $m$ at a time.
For $r \in \Z_{> 0}$, let:
:$S_r = \ds \sum_{j \mathop = a}^b {x_j}^r$
Let $\map G z$ be the generating function for the sequence $\sequence {h_m}$.
Then:
== Proof ==
== Sources ==
* : $\S 1.2.9$: Generating Functions: Exercise $7$
Category:Summation of Products of n Numbers taken m at a time with Repetitions
Summation of Products of n Numbers taken m at a time with Repetitions/Recurrence Formula

== Theorem ==
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:
That is, $h_m$ is the product of all $m$-tuples of elements of $U$ taken $m$ at a time.
For $r \in \Z_{> 0}$, let:
:$\ds S_r = \sum_{k \mathop = a}^b {x_k}^r$
A recurrence relation for $h_n$ can be given as:
for $n \ge 1$.
== Proof ==
== Sources ==
* : $\S 1.2.9$: Generating Functions: $(39)$
Category:Summation of Products of n Numbers taken m at a time with Repetitions
Summation of Reciprocal of Zero of Order 1 Bessel Function by Order 0 Bessel Function of it

== Theorem ==
:$\ds \sum_{n \mathop = 1}^\infty \dfrac 1 {x_n \map {J_0 } {x_n} } = 0 \cdotp 38479 \ldots$
where:
:$x_n$ is the $n$th zero of the order $1$ Bessel function of the first kind
:$\map {J_0 } {x_n}$ is the order $0$ Bessel function of the first kind of $x_n$.
== Historical Note ==
== Sources ==
* : $0,38479 \ldots$
Category:Bessel Functions
Summation of Reciprocal of Zero of Order 1 Bessel Function by Order 0 Bessel Function of it/Historical Note

== Historical Note on Summation of Reciprocal of Zero of Order 1 Bessel Function by Order 0 Bessel Function of it ==
This result is reported in of $1983$, with no indication of context.
It is not revealed why this result is significant.
Category:Historical Notes
Summation of Sum of Mappings on Finite Set

== Theorem ==
Let $\mathbb A$ be one of the standard number systems $\N, \Z, \Q, \R, \C$.
Let $S$ be a finite set.
Let $f, g: S \to \mathbb A$ be mappings.
Let $h = f + g$ be their sum.
Then we have the equality of summations on finite sets:
:$\ds \sum_{s \mathop \in S} \map h s = \sum_{s \mathop \in S} \map f s + \sum_{s \mathop \in S} \map g s$
== Outline of Proof ==
Using the definition of summation on a finite set, we reduce this to Indexed Summation of Sum of Mappings.
== Proof ==
Let $n$ be the cardinality of $S$.
Let $\sigma: \N_{< n} \to S$ be a bijection, where $\N_{< n}$ is an initial segment of the natural numbers.
By definition of summation, we have to prove the following equality of indexed summations:
:$\ds \sum_{i \mathop = 0}^{n - 1} \map h {\map \sigma i} = \sum_{i \mathop = 0}^{n - 1} \map f {\map \sigma i} + \sum_{i \mathop = 0}^{n - 1} \map g {\map \sigma i}$
By Sum of Mappings Composed with Mapping, $h \circ \sigma = f \circ \sigma + g \circ \sigma$.
The above equality now follows from Indexed Summation of Sum of Mappings.
== Also see ==
* Indexed Summation of Sum of Mappings
Category:Summations
Summation of Summation over Divisors of Function of Two Variables

== Theorem ==
Let $c, d, n \in \Z$.
Then:
:$\ds \sum_{d \mathop \divides n} \sum_{c \mathop \divides d} \map f {c, d} = \sum_{c \mathop \divides n} \sum_{d \mathop \divides \paren {n / c} } \map f {c, c d}$
where $c \divides d$ denotes that $c$ is a divisor of $d$.
== Proof ==
From Exchange of Order of Summation with Dependency on Both Indices:
We have that:
:$\map R d$ is the propositional function:
::$d \divides n$
:$\map S {d, c}$ is the propositional function:
::$c \divides d$
Thus $\map {R'} {d, c}$ is the propositional function:
::Both $d \divides n$ and $c \divides d$
This is the same as:
::$c \divides n$ and $\dfrac d c \divides \dfrac n c$
Similarly, $\map {S'} c$ is the propositional function:
::$\exists d$ such that both $d \divides n$ and $c \divides d$
This is the same as:
::$c \divides n$
This gives:
:$\ds \sum_{d \mathop \divides n} \sum_{c \mathop \divides d} \map f {c, d} = \sum_{c \mathop \divides n} \sum_{\paren {d / c} \mathrel \divides \paren {n / c} } \map f {c, d}$
Replacing $d / c$ with $d$:
:$\ds \sum_{d \mathop \divides n} \sum_{c \mathop \divides d} \map f {c, d} = \sum_{c \mathop \divides n} \sum_{d \mathop \divides \paren {n / c} } \map f {c, c d}$
== Sources ==
* : $\S 1.2.4$: Integer Functions and Elementary Number Theory: Exercise $32$
Category:Summations
Category:Divisors
Summation of Unity over Elements

== Theorem ==
Let $S \subseteq \Z$ be a set of integers.
Let:
:$n := \ds \sum_{j \mathop \in S} 1$
Then $n$ is equal to the cardinality of $S$.
== Proof ==
== Sources ==
* : $\S 1.2.3$: Sums and Products: Exercise $17$
Category:Summations
Summation of Zero/Finite Set

== Theorem ==
Let $\mathbb A$ be one of the standard number systems $\N, \Z, \Q, \R, \C$.
Let $S$ be a finite set.
Let $0 : S \to \mathbb A$ be the zero mapping.
Then the summation of $0$ over $S$ equals zero:
:$\ds \sum_{s \mathop \in S} 0 \left({s}\right) = 0$
== Proof ==
At least three proofs are possible:
:using the definition of summation and Indexed Summation of Zero
:using Indexed Summation of Sum of Mappings
:using Summation of Multiple of Mapping on Finite Set.
Category:Summations
Summation of Zero/Indexed Summation

== Theorem ==
Let $\mathbb A$ be one of the standard number systems $\N,\Z,\Q,\R,\C$.
Let $a, b$ be integers.
Let $\closedint a b$ denote the integer interval between $a$ and $b$.
Let $f_0 : \closedint a b \to \mathbb A$ be the zero mapping.
Then the indexed summation of $0$ from $a$ to $b$ equals zero:
:$\ds \sum_{i \mathop = a}^b \map {f_0} i = 0$
== Proof ==
At least three proofs are possible:
* by induction, using Identity Element of Addition on Numbers
* using Indexed Summation of Multiple of Mapping
* using Indexed Summation of Sum of Mappings
Category:Summations