Finite sums and finite products, by recursion

Throughout this page $\mathbb{R}$ is the complete ordered field (Complete ordered field (least-upper-bound property)), in particular an ordered field (Ordered field) and a field (Field), and $\mathbb{N}$ is the set of natural numbers (The natural numbers $\mathbb{N}$ (von Neumann)) with successor $\sigma(n) = n + 1$ (Addition of natural numbers).

Let $a : \mathbb{N} \to \mathbb{R}$ be a sequence of reals, written $a_k$ for $a(k)$. Finite sums and finite products of $a$ are defined by recursion on the upper index, which is legitimate because of the recursion theorem (The recursion theorem). That theorem produces a function of one variable, so the running index has to be carried along inside the value: applying it to the set $A = \mathbb{N} \times \mathbb{R}$, the starting element $(0, 0)$ and the function $f(n, s) = (\sigma(n),\, s + a_n)$ gives a unique $g : \mathbb{N} \to \mathbb{N} \times \mathbb{R}$ with

$g(0) = (0, 0), \qquad g(\sigma(n)) = f(g(n)) \quad (n \in \mathbb{N}).$

Write $g(n) = \big(\pi_1(g(n)),\, \Sigma_n\big)$ for its two coordinates.

The first coordinate is the index itself, and that is a small induction, not an observation (The principle of mathematical induction). Indeed $\pi_1(g(0)) = 0$; and if $\pi_1(g(n)) = n$, then $g(\sigma(n)) = f\big(\pi_1(g(n)), \Sigma_n\big) = \big(\sigma(\pi_1(g(n))),\, \Sigma_n + a_{\pi_1(g(n))}\big) = \big(\sigma(n),\, \Sigma_n + a_n\big)$, so $\pi_1(g(\sigma(n))) = \sigma(n)$. By induction $\pi_1(g(n)) = n$ for every $n \in \mathbb{N}$. Only now may the second coordinate of the two displayed clauses be read off, and doing so gives

$\Sigma_0 = 0, \qquad \Sigma_{\sigma(n)} = \Sigma_n + a_n .$

$\Sigma$ is moreover the unique function $\mathbb{N} \to \mathbb{R}$ with those two properties: if $\Sigma'$ also has them then $n \mapsto (n, \Sigma'_n)$ satisfies the two clauses defining $g$, hence equals $g$ by the uniqueness clause of The recursion theorem, so $\Sigma' = \Sigma$.

We write $\sum_{k < n} a_k := \Sigma_n$. The same construction with starting element $(0, 1)$ and $f(n, p) = (\sigma(n),\, p \cdot a_n)$, with the same induction on the first coordinate and the same uniqueness argument, gives the unique $\Pi : \mathbb{N} \to \mathbb{R}$ with

$\Pi_0 = 1, \qquad \Pi_{\sigma(n)} = \Pi_n \cdot a_n ,$

and we write $\prod_{k < n} a_k := \Pi_n$.

Notation. For $m, n \in \mathbb{N}$ we abbreviate

$\sum_{k=0}^{n} a_k := \sum_{k < n+1} a_k, \qquad \prod_{k=0}^{n} a_k := \prod_{k < n+1} a_k,$

and, for a general lower index $m$ with $m \le n + 1$, writing $d = n + 1 - m$ for the number of terms,

$\sum_{k=m}^{n} a_k := \sum_{j < d} a_{m+j}, \qquad \prod_{k=m}^{n} a_k := \prod_{j < d} a_{m+j} .$

When $m = n + 1$ we have $d = 0$ and the sum is empty, with value $0$, while the empty product has value $1$. In the same spirit $\sum_{k=0}^{-1} a_k$ is notation for the empty sum $\Sigma_0 = 0$ and $\prod_{k=0}^{-1} a_k$ for the empty product $\Pi_0 = 1$; the index $-1$ never occurs as an element of $\mathbb{N}$ and is only a way of writing "no terms".

Only finitely many values of $a$ enter $\sum_{k<n} a_k$, so the notation $\sum_{k<n} a_k$ and $\prod_{k<n} a_k$ is also used for a list $a_0, \dots, a_{n-1}$ of reals given without reference to any extension of the list to all of $\mathbb{N}$: extend the list by $a_k = 0$ (respectively $a_k = 1$) for $k \ge n$ and apply the definition above.

• Why recursion and not "$a_0 + a_1 + \cdots + a_{n-1}$". The dots are not a definition: they presuppose that the displayed pattern determines a value for every $n$, which is exactly what the recursion theorem (The recursion theorem) supplies, and its uniqueness clause is what makes $\sum_{k<n} a_k$ a single well-determined real rather than a family of choices. Associativity and commutativity of addition are not used in the definition; they are used in the laws proved from it (Laws of finite sums and finite products).
• Naturals and rationals inside $\mathbb{R}$ (a convention used on the whole page). A natural number $n$ and a rational number $r$ are not literally elements of $\mathbb{R}$: they enter $\mathbb{R}$ through the canonical embedding $\iota : \mathbb{Q} \to \mathbb{R}$, which is an injective, order-preserving field homomorphism (The unique embedding of ℚ into an ordered field), restricting on positive naturals to $n \mapsto n \cdot 1_{\mathbb{R}} = 1_\mathbb{R} + \cdots + 1_\mathbb{R}$ (Canonical naturals are positive and strictly increasing). Following ordinary practice, and only where no confusion is possible, we write $n$ for $\iota(n)$ and $r$ for $\iota(r)$; so, for instance, $\frac{1}{n}\sum_{k<n} a_k$ means $\iota(n)^{-1} \cdot \sum_{k<n} a_k$, which makes sense because $\iota(n) > 0$ for $n \ge 1$. Exponents are the one place where the identification is deliberately NOT made: in $a^n$ and $a^r$ the exponent stays a natural, an integer or a rational (Integer powers $a^m$, Rational powers $a^r$ of a positive base), never a real.
• The two indexings are related by $\sum_{k=0}^{n} a_k = \sum_{k < n+1} a_k$, so a statement proved for one is available for the other. Sums over $k < n$ are the primitive form here because $\Sigma_0$, the empty sum, is then the base case of every induction, and no index outside $\mathbb{N}$ is ever needed.