2.5.3: More examples

The sum of an arbitrary number of terms is written using the symbol ∑. (This symbol is the Greek letter sigma, which is equivalent to the Latin letter S and stands for ‘sum’.) Thus, we have

\(\sum_{i=1}^{5} i^{2}=1^{2}+2^{2}+3^{2}+4^{2}+5^{2}\)

\(\sum_{k=3}^{7} a_{k}=a_{3}+a_{4}+a_{5}+a_{6}+a_{7}\)

\(\sum_{n=0}^{N} \frac{1}{n+1}=\frac{1}{0+1}+\frac{1}{1+1}+\frac{1}{2+1}+\cdots+\frac{1}{N+1}\)

This notation for a sum, using the ∑ operator, is called summation notation. A similar notation for products uses the symbol ∏. (This is the Greek letter pi, which is equivalent to the Latin letter P and stands for ‘product’.) For example,

\(\prod_{k=2}^{5}(3 k+2)=(3 \cdot 2+2)(3 \cdot 3+2)(3 \cdot 4+2)(3 \cdot 5+2)\)

\(\prod_{i=1}^{n} \frac{1}{i}=\frac{1}{1} \cdot \frac{1}{2} \cdots \frac{1}{n}\)

Induction can be used to prove many formulas that use these notations. Here are two examples:

theorem 3.7

\(\sum_{i=1}^{n} i=\frac{n(n+1)}{2}\) for any integer n greater than zero.

We’ll prove this theorem in class. Can you do it yourself?

The summation of Theorem 3.7 is often attributed to mathematician and physicist Carl Friedrich Gauss (1777–1855). Gauss has been exceptionally influential in a variety of fields; he is called “the greatest mathematician since antiquity”. For example, you might have heard of the Gaussian probability distribution, or perhaps of the Gauss unit for magnetic flux (although we now commonly use the Tesla for that, with 1 Tesla equalling 105 Gauss). His brilliance was already apparent in primary school when he allegedly used the ‘Gauss sum’ from Theorem 3.7 to solve the maths homework the teacher had set the class—to great astonishment of the teacher. You will see this summation again in the course Algorithms & Data Structures when analysing the runtime of algorithms containing loops.

Source: en.Wikipedia.org/wiki/Carl_Friedrich_Gauss.

Theorem3.8.

\(\sum_{i=1}^{n} i 2^{i-1}=(n-1) \cdot 2^{n}+1\) for any natural number \(n>0\)

Proof. Let \(P(n)\) be the statement \(\sum_{i=1}^{n} i 2^{i-1}=(n-1) \cdot 2^{n}+1 .\) We use induction to show that P(n) is true for all n > 0

Base case: Consider the case \(n=1 . P(1)\) is the statement that \(\sum_{i=1}^{1} i 2^{i-1}=(1-1)\) *\(2^{1}+1 .\) Since each side of this equation is equal to one, this is true.

Inductive case: Let k > 1 be arbitrary, and assume that P(k) is true. We want to show that \(P(k+1)\) is true. \(P(k+1)\) is the statement \(\sum_{i=1}^{k+1} i 2^{i-1}=((k+1)-1) \cdot 2^{k+1}+1 .\) But, we can compute that

\(\sum_{i=1}^{k+1} i 2^{i-1}=\left(\sum_{i=1}^{k} i 2^{i-1}\right)+(k+1) 2^{(k+1)-1}\)

\(=\left((k-1) \cdot 2^{k}+1\right)+(k+1) 2^{k}\) (inductive hypothesis)

\(=((k-1)+(k+1)) 2^{k}+1\)

\(=(k \cdot 2) \cdot 2^{k}+1\)

\(=k 2^{k+1}+1\)

which is what we wanted to show. This completes the induction.

For example, these theorems show that \(\sum_{i=1}^{100} i=1+2+3+4+\cdots+100=\frac{100(100+1)}{2}=\)5050 and that \(1 \cdot 2^{0}+2 \cdot 2^{1}+3 \cdot 2^{2}+4 \cdot 2^{3}+5 \cdot 2^{4}=(5-1) 2^{5}+1=129,\) as well as infinitely many other such sums.