Elementary combinatorics: Summation and product symbol
Summation symbol
Dots notation A small number of mathematical terms can be added easily with the sum symbol \(+\). But in many problems there are summations in which many terms have to be added together. For example, the sum of the natural numbers 1 up to and including 64, or the sum of the first 8 squares. You can of course write this suggestively as \[1+2+3+\ldots+63+64=2080\] and \[1+4+16+\ldots+47+64=204\] But we have included many terms in the expression here for a reason. With \[1+2+\ldots+64\] it is already unclear whether you mean the sum of the numbers 1 up to and including 64, or actually the sum \[1+2+4+8+16+32+64=126\] is meant, where each term is twice the previous term. Of course, the notation \[1+4+\ldots 64\] does not have to indicate the sum of the first 8 squares, but it could also stand for \[1+4+16+64=85\] where each term is four times the previous term. If you find these examples a bit contrived, then what do you think \[3+5+7+\ldots 17\] means? The sum of odd numbers \[3+5+7+9+11+13+15+17\] or the sum of prime numbers \[3+5+7+11+13+17\text?\]
Sigma notation (informal) In mathematics you need a more precise sum notation than `dotting' and that is sigma notation. The symbol \(\sum\), which is pronounced ``sigma'', derived from the Greek capital letter \(\Sigma\), is used to indicate addition of terms; it is summation symbol. A so-called summation index runs over the various terms: the sum of the natural numbers 1 to 64 then becomes \(\displaystyle\sum_{i=1}^{64} i\). We read this as ``the sum of \(i\) where \(i\) runs from \(1\) through \(64\) '' or as ``the sum of \(i\) for \(i=1\) through \(i=64\) ''. The pattern is now clearly written down and \(\displaystyle\sum_{i=1}^{66} i=2080\). The sum of the first 8 squares is denoted \(\displaystyle\sum_{i=1}^{8} i^2\) in sigma notation and is equal to \(204\) because ``the sum of \(i^2\) for \(i=1\) through \(i=8\) '' does indeed equal this number.
Example 1 The sum \[2+3+4+5+6+7+8+9+10\] can be shortened as \[ \sum_{i=2}^{10} i,\] but also as \[\sum_{j=1}^{9} (j+1)\] or as \[\sum_{j=4}^{12} (j-2)\text.\] The sigma notation for a certain sum is therefore not unique.
Example 2 If we have 10 numbers that we denote with \(a_0,a_1,a_2,\ldots, a_9\), then we write the sum of these numbers as \[\sum_{i=0}^{9} a_i=a_0+a_1+a_2+\cdots + a_8+a_9\] We read this as ``the sum of the terms \(a_i\) where (the summation index) \(i\) goes from \(0\) up to and including \(9\)''.
Sigma notation (formal) For each natural number \(n\) and \(a_0, a_1,\ldots,, a_n\) mathematical objects for which addition is defined (e.g., real numbers) we define: \[\sum_{i=0}^n a_i=a_0+a_1+a_2+\ldots a_n\] More generally for natural numbers \(m\le n\): \[\sum_{i=m}^n a_i=a_m+a_{m+1}+a_{m+2}+\ldots a_n\] We read this as ``the sum of the terms \(a_i\) where (the summation index) \(i\) goes from \(m\) up to and including \(n\)''. Here \(a_i\) is the general term, \(i\) is the summation index, \(m\) is the lower bound, and \(n\) is the upper bound of the summation.
