# Permutation of Indices of Summation

Jump to navigation
Jump to search

## Theorem

Let $R: \Z \to \set {\T, \F}$ be a propositional function on the set of integers.

Let the fiber of truth of $R$ be finite.

Then:

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

where:

- $\displaystyle \sum_{\map R j} a_j$ denotes the summation over $a_j$ for all $j$ that satisfy the propositional function $\map R j$
- $\pi$ is a permutation on the fiber of truth of $R$.

### Infinite Series

Let the fiber of truth of $R$ be infinite.

Let $\displaystyle \sum_{\map R i} a_i$ be absolutely convergent.

Then:

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

## Proof

\(\displaystyle \sum_{R \left({\pi \left({j}\right)}\right)} a_{\pi \left({j}\right)}\) | \(=\) | \(\displaystyle \sum_{j \mathop \in \Z} a_{\pi \left({j}\right)} \left[{R \left({\pi \left({j}\right)}\right)}\right]\) | Definition of Summation by Iverson's Convention | ||||||||||

\(\displaystyle \) | \(=\) | \(\displaystyle \sum_{j \mathop \in \Z} \sum_{i \mathop \in \Z} a_i \left[{R \left({i}\right)}\right] \left[{i = \pi \left({j}\right)}\right]\) | |||||||||||

\(\displaystyle \) | \(=\) | \(\displaystyle \sum_{i \mathop \in \Z} a_i \left[{R \left({i}\right)}\right] \sum_{j \mathop \in \Z} \left[{i = \pi \left({j}\right)}\right]\) | |||||||||||

\(\displaystyle \) | \(=\) | \(\displaystyle \sum_{i \mathop \in \Z} a_i \left[{R \left({i}\right)}\right]\) | |||||||||||

\(\displaystyle \) | \(=\) | \(\displaystyle \sum_{R \left({i}\right)} a_i\) | |||||||||||

\(\displaystyle \) | \(=\) | \(\displaystyle \sum_{R \left({j}\right)} a_j\) | Change of Index Variable of Summation |

$\blacksquare$

## Also known as

The operation of **permutation of indices** of a summation can be seen referred to as a **permutation of the range**.

However, as the term **range** is ambiguous in the literature, and as its use here is not strictly accurate (it is the **fiber of truth** of $R$, not its **range**, which is being permuted, its use on $\mathsf{Pr} \infty \mathsf{fWiki}$ is discouraged.

## Sources

- 1997: Donald E. Knuth:
*The Art of Computer Programming: Volume 1: Fundamental Algorithms*(3rd ed.) ... (previous) ... (next): $\S 1.2.3$: Sums and Products: $(5)$