Change of Variables in Indexed Summation

From ProofWiki
Jump to: navigation, search


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

Let $a,b,c,d$ be integers.

Let $\left[{a \,.\,.\, b}\right]$ denote the integer interval between $a$ and $b$.

Let $f : \left[{a \,.\,.\, b}\right] \to \mathbb A$ be a mapping.

Let $g : \left[{c \,.\,.\, d}\right] \to \left[{a \,.\,.\, b}\right]$ be a bijection.

Then we have an equality of indexed summations:

$\displaystyle \sum_{i \mathop = a}^b f(i) = \sum_{i \mathop = c}^{d} f(g(i))$

Outline of Proof

We use Indexed Summation over Translated Interval to translate $\left[{c \,.\,.\, d}\right]$ to $\left[{a \,.\,.\, b}\right]$.

This reduces the problem to Indexed Summation does not Change under Permutation.


Because $g : \left[{c \,.\,.\, d}\right] \to \left[{a \,.\,.\, b}\right]$ is a bijection, these sets are equivalent.

By Cardinality of Integer Interval, $\left[{a \,.\,.\, b}\right]$ has cardinality $b-a+1$.

Thus $b-a+1 = d-c+1$.

Thus $c-a = d-b$.

By Indexed Summation over Translated Interval:

$\displaystyle \sum_{i \mathop = c}^{d} f(g(i)) = \sum_{i \mathop = a}^{b} f(g(i + c-a))$

By Translation of Integer Interval is Bijection, the mapping $T : \left[{a \,.\,.\, b}\right] \to \left[{c \,.\,.\, d}\right]$ defined as:

$T(k) = k+c-a$

is a bijection.

By Composite of Bijections is Bijection, $g\circ T$ is a permutation of $\left[{a \,.\,.\, b}\right]$.

We have:

\(\displaystyle \sum_{i \mathop = c}^{d} f(g(i))\) \(=\) \(\displaystyle \sum_{i \mathop = a}^{b} f(g(i + c-a))\) Indexed Summation over Translated Interval
\(\displaystyle \) \(=\) \(\displaystyle \sum_{i \mathop = a}^{b} f(g(T(i)))\) definition of $T$
\(\displaystyle \) \(=\) \(\displaystyle \sum_{i \mathop = a}^{b} f(i)\) Indexed Summation does not Change under Permutation


Also see