# Exchange of Order of Indexed Summations/Rectangular Domain

## Theorem

Let $\mathbb A$ be one of the standard number systems $\N, \Z, \Q, \R, \C$.

Let $a, b, c, d \in \Z$ be integers.

Let $\closedint a b$ denote the integer interval between $a$ and $b$.

Let $D = \closedint a b \times \closedint c d$ be the cartesian product.

Let $f: D \to \mathbb A$ be a mapping

Then we have an equality of indexed summations:

$\displaystyle \sum_{i \mathop = a}^b \sum_{j \mathop = c}^d \map f {i, j} = \sum_{j \mathop = c}^d \sum_{i \mathop = a}^b \map f {i, j}$

## Outline of Proof

We use induction on $d$. In the induction step, we use Indexed Summation of Sum of Mappings.

## Proof

The proof proceeds by induction on $d$.

### Basis for the Induction

Let $d < c$.

Then the indexed summation in the right hand side is zero.

By Indexed Summation of Zero, so is the left hand side.

This is our basis for the induction.

### Induction Step

Let $d \ge c$.

We have:

 $\displaystyle \sum_{i \mathop = a}^b \sum_{j \mathop = c}^d \map f {i, j}$ $=$ $\displaystyle \sum_{i \mathop = a}^b \paren {\sum_{j \mathop = c}^{d - 1} \map f {i, j} + \map f {i, d} }$ Definition of Indexed Summation $\displaystyle$ $=$ $\displaystyle \sum_{i \mathop = a}^b \sum_{j \mathop = c}^{d - 1} \map f {i, j} + \sum_{i \mathop = a}^b \map f {i, d}$ Indexed Summation of Sum of Mappings $\displaystyle$ $=$ $\displaystyle \sum_{j \mathop = c}^{d - 1} \sum_{i \mathop = a}^b \map f {i, j} + \sum_{i \mathop = a}^b \map f {i, d}$ Induction Hypothesis $\displaystyle$ $=$ $\displaystyle \sum_{j \mathop = c}^d \sum_{i \mathop = a}^b \map f {i, j}$ Definition of Indexed Summation

By the Principle of Mathematical Induction, the proof is complete.

$\blacksquare$