Skip to main content

Section 4.1 Preliminaries on summation notation

Before getting into induction, it will be useful to review \(\Sigma\) notation.

Definition 4.1.1.

Let \(n\) be a natural number, and let \(a \colon n \to A\) be a map to a ring \(A\text{.}\) Then we define the notation \(\sum_{k=1}^n a(k)\) inductively as follows: if \(n=0\text{,}\) then \(\sum_{k= 1}^0a(k)=0\text{;}\) for any \(n\geq 1\text{,}\) we let \(\sum_{k = 1}^n a(k) = a(n)+\sum_{k=1}^{n-1} a(k)\text{.}\)

More generally, if \(S\) is a finite set and \(a \colon S \to A\) is a map, then we choose a bijection \(\sigma \colon n \to S\) for a natural number \(n\text{,}\) and we set \(\sum_{s\in S} a(s) = \sum_{k=1}^n a(\sigma(k))\text{.}\)

For example,

\begin{equation*} \sum_{k=1}^{n} k^2 = 1^2+2^2+3^2+\cdots + n^2\text{.} \end{equation*}

We can split sums and use the distribution

\begin{equation*} \sum_{k=m}^{n} (a_{k} +b_{k})=\sum_{k=m}^{n} a_{k} +\sum_{k=m}^{n} b_{k}\;\; \;\;\; \mbox{ and } \;\;\;\;\; \sum_{k=m}^{n} c\cdot a_{k} =c\cdot \sum_{k=m}^{n} a_{k}\text{.} \end{equation*}

The following are useful manipulations of \(\Sigma\) notation

  1. Detaching the last element:

    \begin{equation*} \sum_{k=1}^{n+1} a_k = \left(\sum_{k=1}^{n} a_k\right) + a_{n+1}\text{.} \end{equation*}

  2. Differences

    \begin{equation*} \mbox{If } S_n=\sum_{k=1}^{n} a_k, \mbox{ then } S_{n+1}-S_n = a_{n+1}\text{.} \end{equation*}

  3. Change of variables:

    \begin{equation*} \sum_{k=m}^{n} a_{k+\ell} =\sum_{k=m+\ell}^{n+\ell} a_{k}\text{.} \end{equation*}

    For example,

    \begin{equation*} \sum_{k=3}^{5} \frac{1}{(k+1)^2} =\frac{1}{(3+1)^2}+\frac{1}{(4+1)^2}+\frac{1}{(5+1)^2} =\frac{1}{4^2}+\frac{1}{5^2}+\frac{1}{6^2} = \sum_{k=4}^{6} \frac{1}{k^2}\text{.} \end{equation*}

  4. Change of variables:

    \begin{equation*} \sum_{k=m}^{n} a_{k} =\sum_{j=m}^{n} a_{j}\text{.} \end{equation*}