Finite sums and finite products of natural numbers, $\sum_{k<n} a_k$ and $\prod_{k<n} a_k$ in $\mathbb{N}$

Let $a : \mathbb{N} \to \mathbb{N}$, written $a_k$ for $a(k)$, with addition and multiplication of natural numbers as in Addition of natural numbers and Multiplication of natural numbers. Finite sums and finite products of $a$ inside $\mathbb{N}$ are defined by recursion on the upper index, which is legitimate by the recursion theorem (The recursion theorem).

That theorem produces a function of one variable, so the running index has to be carried inside the value. Apply it to the set $A = \mathbb{N} \times \mathbb{N}$, the starting element $(0,0)$ and the function $f(k, s) = (\sigma(k),\, s + a_k)$: there is a unique $g : \mathbb{N} \to \mathbb{N} \times \mathbb{N}$ 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)),\, S_n\big)$ for its two coordinates.

The first coordinate is the index itself, and that is an 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)), S_n\big) = \big(\sigma(\pi_1(g(n))),\, S_n + a_{\pi_1(g(n))}\big) = \big(\sigma(n),\, S_n + a_n\big)$, so $\pi_1(g(\sigma(n))) = \sigma(n)$. Only now may the second coordinates of the two displayed clauses be read off, and doing so gives

$S_0 = 0, \qquad S_{\sigma(n)} = S_n + a_n .$

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

$\sum_{k<n} a_k := S_n .$

The same construction with starting element $(0,1)$ and $f(k,p) = (\sigma(k),\, p \cdot a_k)$, with the same induction on the first coordinate and the same uniqueness argument, gives the unique $P : \mathbb{N} \to \mathbb{N}$ with

$P_0 = 1, \qquad P_{\sigma(n)} = P_n \cdot a_n ,$

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

The empty sum is $0$ and the empty product is $1$, by the base clause of the recursion and by nothing else: no convention is imported from anywhere.

Notation. We abbreviate $\sum_{k=0}^{n} a_k := \sum_{k<n+1} a_k$ and likewise for products, using $\sigma(n) = n+1$. Only finitely many values of $a$ enter $\sum_{k<n} a_k$, so the notation is also used for a list $a_0, \dots, a_{n-1}$ of naturals given without reference to any extension to all of $\mathbb{N}$: extend the list by $a_k = 0$ (respectively $a_k = 1$) for $k \ge n$ and apply the definition. Where the two kinds of finite sum have to be told apart, we write $\sum^{\mathbb{N}}$ and $\prod^{\mathbb{N}}$ for the ones defined here and $\sum^{\mathbb{R}}$, $\prod^{\mathbb{R}}$ for those of Finite sums and finite products, by recursion; elsewhere the ambient set is fixed by the terms being summed.

Truncated difference, fixed here for the whole page. For $m, n \in \mathbb{N}$ we write $n - m$ for the unique $j \in \mathbb{N}$ with $m + j = n$ when $m \le n$, and for $0$ when $n < m$. Existence in the first case is the definition of $\le$ (Order on the natural numbers) and uniqueness is commutativity with cancellation (Addition is commutative, Addition is cancellative). The two cases are exhaustive and mutually exclusive, since exactly one of $m < n$, $m = n$, $n < m$ holds (Trichotomy of the order on $\mathbb{N}$), so the notation names a single natural number for every $m$ and $n$. Every use of $n-m$ on this page is this operation; no negative number is ever formed, and where a statement is true only under $m \le n$ that hypothesis is written out.

• Why a second finite sum is needed at all. Finite sums and finite products, by recursion defines $\sum_{k<n} a_k$ for a sequence of reals, and its value is a real number. Every count on this page is a natural number, so the sum rule, the row sums of Pascal's triangle, the condition $\sum_i k_i = n$ on a multinomial coefficient and the stars-and-bars count all need a sum that stays in $\mathbb{N}$. The two notions are related, not rival: the bridge $\iota\big(\sum^{\mathbb{N}}_{k<n} a_k\big) = \sum^{\mathbb{R}}_{k<n}\iota(a_k)$ is proved in the next item, and it is what lets an identity between counts be read inside $\mathbb{R}$ and back.

• The monoid version, later. The same recursion is carried out in an arbitrary monoid in The product $g_0 g_1 \cdots g_{n-1}$ of a finite list in a monoid, by recursion, with the empty product ($n = 0$) equal to the identity ↗, which comes later in the reading order; $(\mathbb{N},+,0)$ and $(\mathbb{N},\cdot,1)$ are instances of it, and the agreement is immediate because the recursion clauses are identical. That pointer is orientation only: nothing here depends on it, and the notion defined above is complete as it stands.

• $0$ is an index. $\sum_{k<n}$ runs over $k = 0, 1, \dots, n-1$, so $\sum_{k<1} a_k = a_0$ and $\sum_{k<0} a_k = 0$. A claim about $\sum_{k<n} a_k$ must be checked at $n = 0$, where it is a claim about $0$, and a claim about $\prod_{k<n} a_k$ at $n = 0$, where it is a claim about $1$.