The Recursive Curse: Sigma-notation

Background

This is the Curse that keeps on Cursing!

In this series we'll study some notation for expressing sums and in subsequent articles explore how to express them using a high-level programming language as well as investigating how those calculations are done by the computer in terms of recursion-depth and orders of growth.

Remark Sections and exercises marked with a "*" covers interesting but not essential material. Skip at your leisure.

Exercises marked with a ▸ are recommended and exercises marked with a M are for the mathematically inclined reader.

If you are reading this article because the code aspect of the series interests you I welcome you to skim this article and return to it on an as needed basis.

Notation

Le signe $\sum_{i=1}^{i=\infty}$ indique que l'on doit donne au nombre entier i toutes ses vaeurs $1, 2, 3, \ldots,$ et prenda la somme des termes.

— J. Fourier 1

In this part of the series we'll study some convenient notation
for expressing (finite) sums of the general form

\begin{equation} a_1 + a_2 + \cdots + a_n,
\end{equation}

where each term $a_k$ (where $k \in \left\{1, 2, \ldots, n \right\}$) is a number that has been defined in some manner. Instead of writing all the (consecutive) terms

\begin{equation} a_1 + \cdots + a_n,
\end{equation}

we will use the Greek letter $\Sigma$ (capital sigma, for "sum") and write

\begin{equation} \sum\limits_{k=1}^n a_k \tag{1} \label{eq:sigma-delimited} \end{equation}

instead. Viz. that $\sum_{k=1}^n a_k = a_1 + a_2 + \cdots + a_n$.

Large summation signs like eq. \eqref{eq:sigma-delimited} may be written more compactly as$\sum_{k=1}^n a_k$.


Remark * We call the quantity after $\sum$ (here $a_k$) the summand. The index variable $k$ is said to be bound to the $\sum$ sign, because the $k$ in $a_k$ is unrelated to appearances of $k$ outside
of the summation symbol (Sigma-notation). Any other letter could be readily substituted for $k$ here without changing the meaning. 2

For the index variable, or dummy index, (here $k$) it is not uncommon to use
any of the letters $i,\ j,\ k,\ m,\ n,\ r,\ s,$ and $t$ however it may be wise to discard usage of $i$ in certain contexts and reserve it to denote $\sqrt{-1}$.


Equivalently we may write the same sum in eq. \eqref{eq:sigma-delimited} using the following notation

\begin{equation} \sum\limits_{1 \le\ k\ \le\ n} a_k \tag{2} \label{eq:sigma-general} \end{equation}

We refer to the notation in eq. \eqref{eq:sigma-delimited} as the delimited form of the Sigma-notation and we refer to the notation in eq. \eqref{eq:sigma-general} as the generalized Sigma-notation which is arguably more useful.

Consider the following example to evaluate the merits of the two: say we want to sum all the odd numbers under a $100$. First, behold the sum expressed using the delimited form:

\begin{equation} \sum_{k=0}^{49} (2k + 1)^2 \tag{3} \label{eq:sigma-odds-delimited} \end{equation}

Secondly, the generalized equivalent of eq. \eqref{eq:sigma-odds-delimited},

\begin{equation} \sum\limits_{\substack{ 1 \le\ k\ \le 100 \\ k\ \textrm{odd} } } k^2 \tag{4} \label{eq:sigma-odds-general} \end{equation}

Arguably eq. \eqref{eq:sigma-odds-delimited} is more work on behalf of both the reader and the author. Meanwhile eq. \eqref{eq:sigma-odds-general} affords us greater understanding at solely the loss of the author whom has to do slightly more work in $\LaTeX$ (but he didn't require a single moments pause to express the sum).

Generally, we write

\begin{equation} \sum_{R(j)} a_j \tag{5} \label{eq:sigma-formally} \end{equation}

to denote the sum of all terms $a_j$ such that $j$ is an integer satisfying a given property $R(j)$. If no such integers exist eq. \eqref{eq:sigma-formally} denotes zero. By extension both

\begin{align} \sum\limits_{k=1}^n a_k & \textrm{and} \sum\limits_{1 \le\ k\ \le\ n} a_k \end{align}

equal zero if $n$ is zero by definition.



Important!

Despite having already made many modifications to the summation symbol we'll allow ourselves to return to the delimited form which we started with.

It is important to note that to adequately define $\sum_{i=1}^n a_i$ we' require a recursive definition. Formally defining the symbol isn't strictly important for the sake of the symbol itself, seeing as we've already utilised it successfully and readily adapted to our needs (and we'll continue adapting it later in this article).

However, we will digress here to provide said recursive definition solely for the sake of later articles in which we'll revisit the idea of expressing our sums recursively and when we do so we will do it without discarding the modifications we've applied to the notation.

Definition 1:

\begin{align} \sum\limits_{i=1}^1 a_i &= a_1, \\ \sum\limits_{i=1}^n a_i &= \sum\limits_{i=1}^{n-1} a_i + a_n. \end{align}



References

[1] J. Fourier, "Refroidissement séculaire du globe terrestre," Bulletin des Sciences par la Société philomathique de Paris, series 3, 7 (1820), 58-70.

[2] Ronald. L. Graham, Donald E. Knuth and Oren Patashnik, Concrete Mathematics: A Foundation for Computer Science. Addison-Wesley, 1989; second edition, 1994.

[3] Donald E. Knuth, The Art of Computer programming, volume $1$: Fundamental Algorithms. Addison-Wesley, 1968; third edition, 1997.