Rules for Manipulating Summations

Theorem

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

Let $\ds \sum_{\map R i} 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

$\ds \sum_{\map R i} a_i = \sum_{\map R j} a_j$

Permutation of Indices of Summation

$\ds \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_{\substack {1 \mathop \le i \mathop \le m \\ 1 \mathop \le j \mathop \le n} } \paren {a_i * b_j}$

Exchange of Order of Summation

$\ds \sum_{\map R i} \sum_{\map S j} a_{i j} = \sum_{\map S j} \sum_{\map R i} a_{i j}$

Exchange of Order of Summation with Dependency on Both Indices

$\ds \sum_{\map R i} \sum_{\map S {i, j} } a_{i j} = \sum_{\map {S'} j} \sum_{\map {R'} {i, j} } a_{i j}$

where:

$\map {S'} j$ denotes the propositional function:

there exists an $i$ such that both $\map R i$ and $\map S {i, j}$ hold

$\map {R'} {i, j}$ denotes the propositional function:

both $\map R i$ and $\map S {i, j}$ hold.

Sum of Summations over Overlapping Domains

$\ds \sum_{\map R j} a_j + \sum_{\map S j} a_j = \sum_{\map R j \mathop \lor \map S j} a_j + \sum_{\map R j \mathop \land \map S j} a_j$

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