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 ${\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 \varphi (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{\Big (}\varphi (n)+[n=1]{\Big )}}$$

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>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].}$$