Indexed Summation of Sum of Mappings

From ProofWiki
Jump to navigation Jump to search

Theorem

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

Let $a, b$ be integers.

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

Let $f, g: \closedint a b \to \mathbb A$ be mappings.

Let $h = f + g$ be their pointwise sum.


Then we have the equality of indexed summations:

$\displaystyle \sum_{i \mathop = a}^b \map h i = \sum_{i \mathop = a}^b \map f i + \sum_{i \mathop = a}^b \map g i$


Proof

The proof proceeds by induction on $b$.

For all $b \in \Z_{\ge 0}$, let $\map P b$ be the proposition:

$\displaystyle \sum_{i \mathop = a}^b \map h i = \sum_{i \mathop = a}^b \map f i + \sum_{i \mathop = a}^b \map g i$


Basis for the Induction

Let $b < a$.

Then all indexed summations are zero.

Because $0 = 0 + 0$, the result follows.


Basis for the Induction

Let $b = a$.

\(\displaystyle \sum_{i \mathop = a}^b \map h i\) \(=\) \(\displaystyle \sum_{i \mathop = a}^a \map h i\)
\(\displaystyle \) \(=\) \(\displaystyle \map h a\)
\(\displaystyle \) \(=\) \(\displaystyle \map f a + \map g a\) Definition of Pointwise Addition
\(\displaystyle \) \(=\) \(\displaystyle \sum_{i \mathop = a}^a \map f i + \sum_{i \mathop = a}^a \map g i\)
\(\displaystyle \) \(=\) \(\displaystyle \sum_{i \mathop = a}^b \map f i + \sum_{i \mathop = a}^b \map g i\) as $a = b$

Thus $\map P a$ is seen to hold.

This is our basis for the induction.


Induction Hypothesis

Now it needs to be shown that, if $\map P k$ is true, where $k \ge a$, then it logically follows that $\map P {k + 1}$ is true.


So this is the induction hypothesis:

$\displaystyle \sum_{i \mathop = a}^k \map h i = \sum_{i \mathop = a}^k \map f i + \sum_{i \mathop = a}^k \map g i$


from which it is to be shown that:

$\displaystyle \sum_{i \mathop = a}^{k + 1} \map h i = \sum_{i \mathop = a}^{k + 1} \map f i + \sum_{i \mathop = a}^{k + 1} \map g i$


Induction Step

We have:

\(\displaystyle \sum_{i \mathop = a}^{k + 1} \map h i\) \(=\) \(\displaystyle \sum_{i \mathop = a}^k \map h i + \map h {k + 1}\) Definition of Indexed Summation
\(\displaystyle \) \(=\) \(\displaystyle \sum_{i \mathop = a}^k \map h i + \map f {k + 1} + \map g {k + 1}\) Definition of Pointwise Addition
\(\displaystyle \) \(=\) \(\displaystyle \sum_{i \mathop = a}^k \map f i + \sum_{i \mathop = a}^k \map g i + \map f {k + 1} + \map g {k + 1}\) Induction Hypothesis
\(\displaystyle \) \(=\) \(\displaystyle \sum_{i \mathop = a}^k \map f i + \map f {k + 1} + \sum_{i \mathop = a}^k \map g i + \map g {k + 1}\) Arithmetic Addition is Commutative
\(\displaystyle \) \(=\) \(\displaystyle \sum_{i \mathop = a}^{k + 1} \map f i + \sum_{i \mathop = a}^{k + 1} \map g i\) Definition of Indexed Summation

So $\map P k \implies \map P {k + 1}$ and the result follows by the Principle of Mathematical Induction.

$\blacksquare$


Also see