Iverson bracket

We mechanically derive a well-known sum manipulation rule using Iverson brackets:

${\displaystyle {\begin{aligned}\sum _{k\in A}f(k)+\sum _{k\in B}f(k)&=\sum _{k}f(k)\,[k\in A]+\sum _{k}f(k)\,[k\in B]\\&=\sum _{k}f(k)\,([k\in A]+[k\in B])\\&=\sum _{k}f(k)\,([k\in A\cup B]+[k\in A\cap B])\\&=\sum _{k\in A\cup B}f(k)\ +\sum _{k\in A\cap B}f(k).\end{aligned}}}$

The well-known rule ${\displaystyle \textstyle \sum _{j=1}^{n}\,\sum _{k=1}^{j}f(j,k)=\sum _{k=1}^{n}\,\sum _{j=k}^{n}f(j,k)}$ is likewise easily derived:

${\displaystyle {\begin{aligned}\sum _{j=1}^{n}\,\sum _{k=1}^{j}f(j,k)&=\sum _{j,k}f(j,k)\,[1\leq j\leq n]\,[1\leq k\leq j]\\&=\sum _{j,k}f(j,k)\,[1\leq k\leq j\leq n]\\&=\sum _{j,k}f(j,k)\,[1\leq k\leq n]\,[k\leq j\leq n]\\&=\sum _{k=1}^{n}\,\sum _{j=k}^{n}f(j,k).\end{aligned}}}$

For instance, the Euler phi function that counts the number of positive integers up to n which are coprime to n can be expressed by

${\displaystyle \phi (n)=\sum _{i=1}^{n}[\gcd(i,n)=1],\qquad {\text{for }}n\in \mathbb {N} ^{+}.}$

Another use of the Iverson bracket is to simplify equations with special cases. For example, the formula

${\displaystyle \sum _{1\leq k\leq n \atop \gcd(k,n)=1}\!\!k={\frac {1}{2}}n\varphi (n)}$

is valid for n > 1 but is off by 1/2 for n = 1. To get an identity valid for all positive integers n (i.e., all values for which ${\displaystyle \phi (n)}$ is defined), a correction term involving the Iverson bracket may be added:

${\displaystyle \sum _{1\leq k\leq n \atop \gcd(k,n)=1}\!\!k={\frac {1}{2}}n(\varphi (n)+[n=1])}$

Many common functions, especially those with a natural piecewise definition, may be expressed in terms of the Iverson bracket. The Kronecker delta notation is a specific case of Iverson notation when the condition is equality. That is,

${\displaystyle \delta _{ij}=[i=j].}$

The indicator function, often denoted ${\displaystyle \mathbf {1} _{A}(x)}$, ${\displaystyle \mathbf {I} _{A}(x)}$ or ${\displaystyle \chi _{A}(x)}$, is an Iverson bracket with set membership as its condition:

${\displaystyle \mathbf {I} _{A}(x)=[x\in A]}$.

The Heaviside step function, sign function,[1] and absolute value function are also easily expressed in this notation:

${\displaystyle {\begin{aligned}H(x)&=[x\geq 0],\\\operatorname {sgn}(x)&=[x>0]-[x<0],\end{aligned}}}$

and

${\displaystyle {\begin{aligned}|x|&=x[x>0]-x[x<0]\\&=x([x>0]-[x<0])\\&=x\cdot \operatorname {sgn}(x).\end{aligned}}}$

The comparison functions max and min (returning the larger or smaller of two arguments) may be written as

${\displaystyle \max(x,y)=x[x>y]+y[x\leq y]}$ and

${\displaystyle \min(x,y)=x[x\leq y]+y[x>y]}$.

The floor and ceiling functions can be expressed as

${\displaystyle \lfloor x\rfloor =\sum _{n}n\cdot [n\leq x<n+1]}$

and

${\displaystyle \lceil x\rceil =\sum _{n}n\cdot [n-1<x\leq n],}$

where the index ${\displaystyle n}$ of summation is understood to range over all the integers.

The ramp function can be expressed

${\displaystyle R(x)=x\cdot [x\geq 0].}$

The trichotomy of the reals is equivalent to the following identity:

${\displaystyle [a<b]+[a=b]+[a>b]=1.}$

The Möbius function has the property (and can be defined by recurrence as[4])

${\displaystyle \sum _{d|n}\mu (d)\ =\ [n=1].}$