Rules for Manipulating Summations

Theorem

Let $R: \Z \to \left\{ {\mathrm T, \mathrm F}\right\}$ and $S: \Z \to \left\{ {\mathrm T, \mathrm F}\right\}$ be propositional functions on the set of integers.

Let $S: \Z \times \Z \to \left\{ {\mathrm T, \mathrm F}\right\}$ be a propositional functions on the Cartesian product of the set of integers with itself.

Let $\displaystyle \sum_{R \left({i}\right)} x_i$ denote a summation over $R$.

Let $\pi$ be a permutation on the fiber of truth of $R$.

Change of Index Variable of Summation

$\displaystyle \sum_{R \left({i}\right)} a_i = \sum_{R \left({j}\right)} a_j$

Permutation of Indices of Summation

$\displaystyle \sum_{\map R j} a_j = \sum_{\map R {\map \pi j} } a_{\map \pi j}$

General Distributivity Theorem

$\ds \paren {\sum_{i \mathop = 1}^m a_i} * \paren {\sum_{j \mathop = 1}^n b_j} = \sum_{ {1 \mathop \le i \mathop \le m} \atop {1 \mathop \le j \mathop \le n} } \paren {a_i * b_j}$

Exchange of Order of Summation

$\displaystyle \sum_{R \left({i}\right)} \sum_{S \left({j}\right)} a_{i j} = \sum_{S \left({j}\right)} \sum_{R \left({i}\right)} a_{i j}$

Exchange of Order of Summation with Dependency on Both Indices

$\displaystyle \sum_{R \left({i}\right)} \sum_{S \left({i, j}\right)} a_{i j} = \sum_{S' \left({j}\right)} \sum_{R' \left({i, j}\right)} a_{i j}$

where:

$S' \left({j}\right)$ denotes the propositional function:

there exists an $i$ such that both $R \left({i}\right)$ and $S \left({i, j}\right)$ hold

$R' \left({i, j}\right)$ denotes the propositional function:

both $R \left({i}\right)$ and $S \left({i, j}\right)$ hold.

Sum of Summations over Overlapping Domains

$\displaystyle \sum_{R \left({j}\right)} a_j + \sum_{S \left({j}\right)} a_j = \sum_{R \left({j}\right) \mathop \lor S \left({j}\right)} a_j + \sum_{R \left({j}\right) \mathop \land S \left({j}\right)} a_j$

where $\lor$ and $\land$ signify logical disjunction and logical conjunction respectively.