In mathematics, an iterated binary operation is an extension of a binary operation on a set S to a function on finite sequences of elements of S through repeated application.^[1] Common examples include the extension of the addition operation to the summation operation, and the extension of the multiplication operation to the product operation. Other operations, e.g., the set-theoretic operations union and intersection, are also often iterated, but the iterations are not given separate names. In print, summation and product are represented by special symbols; but other iterated operators often are denoted by larger variants of the symbol for the ordinary binary operator. Thus, the iterations of the four operations mentioned above are denoted

${\displaystyle \sum ,\ \prod ,\ \bigcup ,}$ and ${\displaystyle \bigcap }$, respectively.

More generally, iteration of a binary function is generally denoted by a slash: iteration of ${\displaystyle f}$ over the sequence ${\displaystyle (a_{1},a_{2}\ldots ,a_{n})}$ is denoted by ${\displaystyle f/(a_{1},a_{2}\ldots ,a_{n})}$, following the notation for reduce in Bird–Meertens formalism.

In general, there is more than one way to extend a binary operation to operate on finite sequences, depending on whether the operator is associative, and whether the operator has identity elements.

Denote by a_j,k, with j ≥ 0 and k ≥ j, the finite sequence of length k − j of elements of S, with members (a_i), for j ≤ i < k. Note that if k = j, the sequence is empty.

For f : S × S → S, define a new function F_l on finite nonempty sequences of elements of S, where $${\displaystyle F_{l}(\mathbf {a} _{0,k})={\begin{cases}a_{0},&k=1\\f(F_{l}(\mathbf {a} _{0,k-1}),a_{k-1}),&k>1.\end{cases}}}$$

Similarly, define $${\displaystyle F_{r}(\mathbf {a} _{0,k})={\begin{cases}a_{0},&k=1\\f(a_{0},F_{r}(\mathbf {a} _{1,k})),&k>1.\end{cases}}}$$

If f has a unique left identity e, the definition of F_l can be modified to operate on empty sequences by defining the value of F_l on an empty sequence to be e (the previous base case on sequences of length 1 becomes redundant). Similarly, F_r can be modified to operate on empty sequences if f has a unique right identity.

If f is associative, then F_l equals F_r, and we can simply write F. Moreover, if an identity element e exists, then it is unique (see Monoid).

If f is commutative and associative, then F can operate on any non-empty finite multiset by applying it to an arbitrary enumeration of the multiset. If f moreover has an identity element e, then this is defined to be the value of F on an empty multiset. If f is idempotent, then the above definitions can be extended to finite sets.

If S also is equipped with a metric or more generally with topology that is Hausdorff, so that the concept of a limit of a sequence is defined in S, then an infinite iteration on a countable sequence in S is defined exactly when the corresponding sequence of finite iterations converges. Thus, e.g., if a₀, a₁, a₂, a₃, … is an infinite sequence of real numbers, then the infinite product ${\textstyle \prod _{i=0}^{\infty }a_{i}}$ is defined, and equal to ${\textstyle \lim \limits _{n\to \infty }\prod _{i=0}^{n}a_{i},}$ if and only if that limit exists.

The general, non-associative binary operation is given by a magma. The act of iterating on a non-associative binary operation may be represented as a binary tree.

Iterated operations

Area of mathematics	Sum				Product
	Name	Operation	Definition	Symbol	Name	Operation	Definition	Symbol
Arithmetic	Summation	Addition	Sum of numbers	${\displaystyle \sum }$	Iterated product	Multiplication	Product of numbers	${\displaystyle \prod }$
Set theory	Union of a sequence of sets	Set union	All elements of sets	${\displaystyle \bigcup }$	Intersection of a sequence of sets	Set intersection	Common elements	${\displaystyle \bigcap }$
Logic	Existential quantifier	Disjunction	Disjunction of statements	${\displaystyle \bigvee }$	Universal quantifier	Conjunction	Conjunction of statements	${\displaystyle \bigwedge }$
Divisibility theory	Least common multiple	Least common multiple	The smallest number that is a multiple of all the terms	${\displaystyle \operatorname {lcm} }$	Greatest common divisor	Greatest common divisor	The greatest number that is a divisor of all the terms	${\displaystyle \gcd }$
Category theory	Coproduct	Disjoint union	Coproduct of objects	${\displaystyle \coprod }$	Product	Cartesian product	Product of objects	${\displaystyle \prod }$

The iterated binary operation is written as:

${\displaystyle \mathop {\bigstar } _{k=1}^{n}a_{k}}$

Meaning of symbols:

Symbol	Meaning
${\displaystyle \bigstar }$	Iterated binary operation symbol
${\displaystyle k}$	Index variable
${\displaystyle k=1}$	Lower bound
${\displaystyle k=n}$ or ${\displaystyle n}$	Upper bound
${\displaystyle a_{k}}$	k-th element

Example:

${\displaystyle \mathop {\bigstar } _{k=1}^{4}a_{k}=\mathop {\bigstar } _{k=1}^{k=4}a_{k}=a_{1}\star a_{2}\star a_{3}\star a_{4}}$

General form:

${\displaystyle \mathop {\bigstar } _{k\in K}a_{k}}$

Restricted form:

${\displaystyle \mathop {\bigstar } _{1\leq k\leq n \atop k\equiv 0{\pmod {2}}}a_{k}}$

Infinite version:

${\displaystyle \mathop {\bigstar } _{k=1}^{\infty }a_{k}=\mathop {\bigstar } _{k=1}^{k\to \infty }a_{k}}$

Let ${\displaystyle (S,\star )}$ be a structure with associative operation ${\displaystyle \star }$:

• Single element:

${\displaystyle \mathop {\bigstar } _{k=n}^{n}a_{k}=a_{n}}$

• Expansion:

${\displaystyle \mathop {\bigstar } _{k=1}^{n}a_{k}=a_{1}\star a_{2}\star \dots \star a_{n}}$

• Recursion:

${\displaystyle \mathop {\bigstar } _{k=1}^{n}a_{k}=\left(\mathop {\bigstar } _{k=1}^{n-1}a_{k}\right)\star a_{n}}$

• Right recursion:

${\displaystyle \mathop {\bigstar } _{k=1}^{n}a_{k}=a_{1}\star \left(\mathop {\bigstar } _{k=2}^{n}a_{k}\right)}$

• Splitting:

${\displaystyle \left(\mathop {\bigstar } _{k=1}^{m}a_{k}\right)\star \left(\mathop {\bigstar } _{k=m+1}^{n}a_{k}\right)=\mathop {\bigstar } _{k=1}^{n}a_{k}}$

• Permutation invariance:

${\displaystyle \mathop {\bigstar } _{k=1}^{n}a_{k}=\mathop {\bigstar } _{k=1}^{n}a_{\sigma (k)}}$

• Empty product (monoid):

${\displaystyle \mathop {\bigstar } _{k=1}^{0}a_{k}=e}$

• Idempotence:

if ${\displaystyle a\star a=a}$, then ${\displaystyle \mathop {\bigstar } _{k=1}^{n}a=a}$

• Constant sequence:

${\displaystyle \mathop {\bigstar } _{k=1}^{n}a=a\star \cdots \star a}$

If ${\displaystyle (S,\star ,e)}$ is a Monoid, then:

• Empty product = identity element
• Empty sum = 0 (in arithmetic monoids)

In functional programming, iterated binary operations correspond to higher-order functions such as fold or reduce.

• Unary operation
• Unary function
• Binary operation
• Binary function
• Ternary operation

• Bulk action
• Parallel prefix operation Archived 2013-06-03 at the Wayback Machine
• Nuprl iterated binary operationsArchived 2016-03-03 at the Wayback Machine