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

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

${\mathrm{\Sigma }}_0=0,{\mathrm{\Sigma }}_{\sigma (n)}={\mathrm{\Sigma }}_n+a_n\mathrm{.}$

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

We write ${\sum }_{k<n}{a}_k:={\mathrm{\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 $\mathrm{\Pi }:\mathbb{N}\to \mathbb{R}$ with

${\mathrm{\Pi }}_0=1,{\mathrm{\Pi }}_{\sigma (n)}={\mathrm{\Pi }}_n\cdot a_n,$

and we write ${\prod }_{k<n}{a}_k:={\mathrm{\Pi }}_n$.

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

${\sum }_{k=0}^n{a}_k:={\sum }_{k<n+1}{a}_k,{\prod }_{k=0}^n{a}_k:={\prod }_{k<n+1}{a}_k,$

and, for a general lower index $m$ with $m\le n+1$, let $d$ be the unique natural number satisfying $m+d=n+1$. Existence is the definition of natural order (Order on the natural numbers); if $m+d=m+e$, commutativity (Addition is commutative) gives $d+m=e+m$, so cancellation (Addition is cancellative) gives $d=e$. On these admissible bounds only, we may write this unique additive gap as $d=n+1-m$; no total natural subtraction operation is presupposed. With $d$ thus fixed, define

${\sum }_{k=m}^n{a}_k:={\sum }_{j<d}{a}_{m+j},{\prod }_{k=m}^n{a}_k:={\prod }_{j<d}{a}_{m+j}\mathrm{.}$

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 ${\mathrm{\Sigma }}_0=0$ and ${\prod }_{k=0}^{-1}{a}_k$ for the empty product ${\mathrm{\Pi }}_0=1$; the index $-1$ never occurs as an element of $\mathbb{N}$ and is only a way of writing "no terms".

Equivalently, for naturals $m\le r$, the half-open endpoint notation ${\sum }_{k=m}^{r-1}{a}_k$ and ${\prod }_{k=m}^{r-1}{a}_k$ means ${\sum }_{j<d}{a}_{m+j}$ and ${\prod }_{j<d}{a}_{m+j}$, respectively, where $d$ is the unique natural with $m+d=r$. Here $r-1$ is an endpoint label for the terms before $r$, so this notation needs no total subtraction operation. For $m=r$, the unique gap is $0$ because $m+0=m$, giving the empty sum and product; the case $m=r=0$ is the $-1$ endpoint convention just stipulated.

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.

Complete ordered field (least-upper-bound property)

Ordered field

Field

The natural numbers $\mathbb{N}$ (von Neumann)

Addition of natural numbers

The recursion theorem

The principle of mathematical induction

Order on the natural numbers

Addition is commutative

Addition is cancellative

• 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 the same symbols $n$ and $r$ for their canonical images in $\mathbb{R}$. Thus $\frac{1}{n}{\sum }_{k<n}{a}_k$ means the inverse of the field element $n\cdot 1_{\mathbb{R}}$, multiplied by that real sum; this is defined for $n\ge 1$ because $n\cdot 1_{\mathbb{R}}>0$. Index bounds remain natural numbers. Likewise the exponent in $a^n$ or $a^r$ remains a natural, integer or rational (Integer powers $a^m$, Rational powers $a^r$ of a positive base); it is not replaced by a real exponent.
• 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 ${\mathrm{\Sigma }}_0$, the empty sum, is then the base case of every induction, and no index outside $\mathbb{N}$ is ever needed.