# Index Laws/Sum of Indices/Semigroup

## Theorem

Let $\struct {S, \circ}$ be a semigroup.

For $a \in S$, let $\circ^n a = a^n$ be defined as the $n$th power of $a$:

$a^n = \begin{cases} a & : n = 1 \\ a^x \circ a & : n = x + 1 \end{cases}$

That is:

$a^n = \underbrace {a \circ a \circ \cdots \circ a}_{n \text{ copies of } a} = \circ^n \paren a$

Then:

$\forall m, n \in \N_{>0}: a^{n + m} = a^n \circ a^m$

## Proof

Let $a \in S$.

Because $\struct {S, \circ}$ is a semigroup, $\circ$ is associative on $S$.

The proof proceeds by the Principle of Mathematical Induction.

Let $P \paren m$ be the proposition:

$\forall n \in \N_{>0}: a^{n + m} = a^n \circ a^m$

that is:

$\forall n \in \N_{>0}: \circ^{n + m} a = \paren {\circ^n a} \circ \paren {\circ^m a}$

### Basis for the Induction

 $\, \displaystyle \forall n \in \N_{>0}: \,$ $\displaystyle \circ^{n + 1} a$ $=$ $\displaystyle \paren {\circ^n a} \circ a$ Definition of $\circ^n a: \N_{>0} \to S$ $\displaystyle$ $=$ $\displaystyle \paren {\circ^n a} \circ \paren {\circ^1 a}$ Definition of $\circ^n a$ for $n = 1$

So $P \paren 1$ holds.

This is our basis for the induction.

### Induction Hypothesis

Now we need to show that, if $P \paren k$ is true, where $k \ge 1$, then it logically follows that $P \paren {k + 1}$ is true.

So this is our induction hypothesis:

$\circ^{n + k} a = \paren {\circ^n a} \circ \paren {\circ^k a}$

It is then to be shown that:

$\circ^{n + \paren {k + 1} } a = \paren {\circ^n a} \circ \paren {\circ^{k + 1} a}$

### Induction Step

This is our induction step:

 $\displaystyle \circ^{n + \paren {k + 1} } a$ $=$ $\displaystyle \circ^{\paren {n + k} + 1} a$ Natural Number Addition is Associative $\displaystyle$ $=$ $\displaystyle \paren {\circ^{n + k} a} \circ \paren {\circ^1 a}$ Basis for the Induction $\displaystyle$ $=$ $\displaystyle \paren {\paren {\circ^n a} \circ \paren {\circ^k a} } \circ \paren {\circ^1 a}$ Induction Hypothesis $\displaystyle$ $=$ $\displaystyle \paren {\circ^n a} \circ \paren {\paren {\circ^k a} \circ \paren {\circ^1 a} }$ $\circ$ is associative $\displaystyle$ $=$ $\displaystyle \paren {\circ^n a} \circ \paren {\circ^{k + 1} a}$ Basis for the Induction

So $P \paren {k + 1}$ is true.

So by the Principle of Mathematical Induction, this result is true for all $m, n \in \N_{>0}$:

$\forall m, n \in \N_{>0}: \circ^{n + m} a = \paren {\circ^n a} \circ \paren {\circ^m a}$

or:

$\forall m, n \in \N_{>0}: a^{n + m} = a^n \circ a^m$

$\blacksquare$

## Notation

Let $a^n$ be defined as the power of an element of a magma:

$a^n = \begin{cases} a : & n = 1 \\ a^x \circ a : & n = x + 1 \end{cases}$

that is:

$a^n = \underbrace {a \circ a \circ \cdots \circ a}_{n \text{ copies of } a} = \map {\circ^n} a$

Recall the index law for sum of indices:

$\circ^{n + m} a = \paren {\circ^n a} \circ \paren {\circ^m a}$

This result can be expressed:

$a^{n + m} = a^n \circ a^m$

When additive notation $\struct {S, +}$ is used, the following is a common convention:

$\left({n + m}\right) a = n a + m a$

or:

$\forall m, n \in \N_{>0}: \paren {n + m} \cdot a = n \cdot a + m \cdot a$