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),g(\sigma (n))=f(g(n))(n\in \mathbb{N})\mathrm{.}$

Write $g(n)=({\pi }_1(g(n)),S_n)$ 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({\pi }_1(g(n)),S_n)=(\sigma ({\pi }_1(g(n))),S_n+a_{{\pi }_1(g(n))})=(\sigma (n),S_n+a_n)$, 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,S_{\sigma (n)}=S_n+a_n\mathrm{.}$

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

${\sum }_{k<n}{a}_k:=S_n\mathrm{.}$

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,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 \left({\sum }_{k<n}^{\mathbb{N}}{a}_k\right)={\sum }_{k<n}^{\mathbb{R}}\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$.