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$, writing $d=n+1-m$ for the number of terms,

${\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".

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 ${\mathrm{\Sigma }}_0$, the empty sum, is then the base case of every induction, and no index outside $\mathbb{N}$ is ever needed.