Exchange of Order of Summation with Dependency on Both Indices/Proof

From ProofWiki
Jump to navigation Jump to search

Theorem

$\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.


Proof

\(\ds \sum_{\map R i} \sum_{\map S {i, j} } a_{i j}\) \(=\) \(\ds \sum_{i, j \mathop \in \Z} a_{i j} \sqbrk {\map R i} \sqbrk {\map S {i, j} }\)
\(\ds \) \(=\) \(\ds \sum_{i, j \mathop \in \Z} a_{i j} \sqbrk {\map R i \land \map S {i, j} }\)
\(\ds \) \(=\) \(\ds \sum_{i, j \mathop \in \Z} a_{i j} \sqbrk {\map {S'} j} \sqbrk {\map {R'} {i, j} }\)
\(\ds \) \(=\) \(\ds \sum_{\map {S'} j} \sum_{\map {R'} {i, j} } a_{i j}\)

$\blacksquare$


Sources