3.4 Summation.

3.65   Notation ( $\mbox{{\bf Z}}_{\geq k}$.) Let $k\in\mbox{{\bf Z}}$. We define

$$\mbox{{\bf Z}}_{\geq k}=\{n\in\mbox{{\bf Z}}\colon n\geq k\}.$$

In particular $\mbox{{\bf Z}}_{\geq 0}=\mbox{{\bf N}}$.

3.66   Definition ( $${\sum_{j=k}^pf(j)}$$) Let $k\in\mbox{{\bf Z}}$ and let $f\colon\mbox{{\bf Z}}_{\geq k}\to F$ be a function from $\mbox{{\bf Z}}_{\geq k}$ to a field $F$. Define a function $S\colon\mbox{{\bf Z}}_{\geq k}\to F$ by the rules

$$\begin{eqnarray*} S(k)&=&f(k) \\ S(n+1)&=&S(n)+f(n+1)\mbox{ for all } n\in\mbox{{\bf Z}}_{\geq k}. \end{eqnarray*}$$

Hence, for $k=2$,

$$\begin{eqnarray*} S(5)&=&S(4)+f(5) \\ &=&S(3)+f(4)+f(5) \\ &=&S(2)+f(3)+f(4)+f(5) \\ &=&f(2)+f(3)+f(4)+f(5). \end{eqnarray*}$$

We denote $S(p)$ by $${\sum_{j=k}^pf(j)}$$ for all $p\in\mbox{{\bf Z}}_{\geq k}$. Thus,

$$\sum_{j=k}^k f(j)=f(k)$$ (3.67)

and

$$\sum_{j=k}^{n+1}f(j)=\left(\sum_{j=k}^n f(j)\right)+f(n+1).$$

The letter $j$ in (3.67) has no meaning, and can be replaced by any symbol that has no meaning in the present context. Thus $${\sum_{j=3}^5 f(j)=\sum_{w=3}^5 f(w)}$$.

3.68   Example.

$$\begin{eqnarray*}\sum_{j=0}^4j^2&=&0^2+1^2+2^2+3^2+4^2=30 \\ \sum_{j=-3}^3j&=&(-3)+(-2)+(-1)+0+1+2+3=0. \end{eqnarray*}$$

i

3.69   Remark. I will sometimes write things like

$$\sum_{j=1}^2{1\over {3-j}}={1\over {3-1}}+{1\over {3-2}}={1\over 2}+1={3\over 2}$$

even though my definition of summation is not strictly applicable here (since $${{1\over {3-j}}}$$ is not defined for all $j\in\mbox{{\bf Z}}_{\geq 1}$).

There are many formulas associated with summation notation that are easily proved by induction; e.g., let $f,g$ be functions from $\mbox{{\bf Z}}_{\geq k}$ to an ordered field $F$, and let $c\in F$. Then

$${\sum_{j=k}^p f(j)+\sum_{j=k}^p g(j)=\sum_{j=k}^p [f(j)+g(j)]\mbox{ for all } p\in\mbox{{\bf Z}}_{\geq k}.}$$

$${c\sum_{j=k}^p f(j)=\sum_{j=k}^p\left(c\cdot f(j)\right) \mbox{ for all } p\in\mbox{{\bf Z}}_{\geq k}.}$$

If $f(j)\geq g(j)$ for all $j\in\mbox{{\bf Z}}_{\geq k}$, then $${\sum_{j=k}^p f(j)\geq\sum_{j=k}^p g(j) \mbox{ for all } p\in\mbox{{\bf Z}}_{\geq k}.}$$

$${\sum_{j=k}^p f(j)=\sum_{j=k}^q f(j)+\sum_{j=q+1}^p f(j) \mbox{ for all } q\in\mbox{{\bf Z}}_{\geq k},p\in\mbox{{\bf Z}}_{\geq q+1}.}$$

We will assume these results.

3.70   Remark. Usually induction arguments are presented less formally than I have been presenting them. In the proof of the next theorem I will give a more typical looking induction argument. (I personally find the more formal version - where a proposition is actually named - easier to understand.)

3.71   Theorem (Finite geometric series.) Let $F$ be a field, and let $r\in F\backslash\{1\}$. Then for all $n\in\mbox{{\bf N}}$,

$$\sum_{j=0}^n r^j={{1-r^{n+1}}\over {1-r}}.$$ (3.72)

Proof: (By induction.) When $n=0$, (3.72) says $${\sum_{j=0}^0r^j={{1-r}\over {1-r}}}$$ which is true since both sides are equal to $1$. Now suppose that (3.72) is true for some $n\in\mbox{{\bf N}}$. Then

$$\begin{eqnarray*} \sum_{j=0}^{n+1}r^j&=&\sum_{j=0}^n r^j+r^{n+1}={{1-r^{n+1}}\ov... ...-r^{n+1}+r^{n+1}(1-r)}\over {1-r}}={{1-r^{(n+1)+1}}\over {1-r}} \end{eqnarray*}$$

so

$$\sum_{j=0}^{n+1}r^j={{1-r^{(n+1)+1}}\over {1-r}}.$$

Hence, if (3.72) holds for some $n\in\mbox{{\bf N}}$, it also holds when $n$ is replaced by $n+1$. By induction (3.72) holds for all $n\in\mbox{{\bf N}}$. $\mid\!\mid\!\mid$

3.73   Remark. I will sometimes denote $${\sum_{j=1}^n f(j)}$$ by $f(1)+f(2)+ \cdots + f(n)$. I am not going to give a formal definition for $\cdots$, and when you see $\cdots$ written in these notes it is usually an indication that a straightforward induction argument or a recursive definition is being omitted.

3.74   Remark. The previous proof was easy, but in order to use the induction proof, I needed to know the formula. Here I will indicate how one might discover such a formula. For each $n\in\mbox{{\bf N}}$, let $S_n=1+r+\cdots +r^n$. Then

$$(1+r+\cdots +r^{n+1}) = (1+r + \cdots +r^n) + r^{n+1} = S_n+r^{n+1}$$ (3.75)

and

$$(1+r+\cdots +r^{n+1}) = 1 + r(1+r + \cdots +r^n) = 1+rS_n.$$

Hence

$$S_n+r^{n+1} = 1 + rS_n,$$ (3.76)

and it follows that

$$S_n(1-r) = 1-r^{n+1}$$

i.e.

$$S_n={{1-r^{n+1}}\over {1-r}}.$$

Here I have derived the formula (3.72). If you write out the argument from line (3.75) to line (3.76), without using $\cdots$s, and using only properties of sums that we have explicitly proved or assumed, you will probably be surprised at how many implicit assumptions were made above. However all of the assumptions can be justified in a straightforward way.

3.77   Theorem (Factorization of $a^{n+1}-r^{n+1}$.) Let $F$ be a field, and let $a$, $r$ be elements of $F$. Then for all $n\in\mbox{{\bf N}}$,

$$(a^{n+1} - r^{n+1}) = (a-r)(\sum_{j=0}^n a^{n-j} r^j)$$ (3.78)

$$= (a-r)(a^n + a^{n-1}r^1 + a^{n-2}r^2 + \cdots + a^1r^{n-1} + r^n).\mbox{{}}$$

Proof: Let $n\in\mbox{{\bf N}}$. The formula (3.72) for a finite geometric series shows that

$$(1-r^{n+1}) = (1-r)\sum_{j=0}^nr^j \mbox{ for all }r \in F \setminus \{1\}.$$ (3.79)

This formula also holds when $r=1$, since then both sides of the equation are equal to zero, so

$$(1-r^{n+1}) = (1-r)\sum_{j=0}^nr^j \mbox{ for all }r \in F.$$ (3.80)

This proves our formula in the case $a=1$. When $a=0$, equation (3.78) says

$$-(r^{n+1}) = (-r)\cdot r^n$$

which is true, so we will suppose that $a\neq 0$. Then by (3.80) we have

$$\begin{eqnarray*} a^{n+1} - r^{n+1} &=&a^{n+1} \left( 1 - \left({r\over a}\right... ...^j}r^j = (a-r) \sum_{j=0}^n a^{n-j}r^j\mbox{ $\mid\!\mid\!\mid$} \end{eqnarray*}$$

3.81   Remark. The solution to the problem of ``factoring'' an expression depends on the field over which we are working. For example, if we work over $\mbox{{\bf Z}}_7$, then

$$x^2+5 = (x+3)(x+4),$$

whereas if $F$ is an ordered field, then $x^2+5$ does not factor in the form $(x+a)(x+b)$, where $a$ and $b$ are in $F$. (If $x^2+5 = (x+a)(x+b)$ for all $x\in F$, then by taking $x = -a$ we would get $a^2 + 5 = 0$, which is false since $a^2 + 5 > 0$ in any ordered field.)

3.82   Exercise. A Factor five of the following expressions into at least two factors. Assume that all numbers appearing in your factorization are rational.

a)

$a^3 - b^3$.

b)

$r^p - 1$. (Here $p\in \mbox{{\bf Z}}_{\geq2}$.)

c)

$a^3 + b^3$.

d)

$a^4 + b^4$.

e)

$x^6 - b^6$.

f)

$x^6 + a^6$.

3.83   Entertainment. Let $F$ be a field and let $r\in F\backslash\{1\}$. For all $n\in\mbox{{\bf Z}}_{\geq 1}$, let

$$T_n=r+2r^2+3r^3+\cdots +n\cdot r^n=\sum_{j=1}^n jr^j.$$

By looking at $T_{n+1}-r\cdot T_n$ and using the known formula (3.72), derive the formula

$$T_n={r\over {(1-r)^2}}\left(1+nr^{n+1}-(n+1)r^n\right).$$

3.84   Exercise. A Let

$$S_n=\sum_{j=1}^n {1\over {j(j+1)}}\mbox{ for all } n\in\mbox{{\bf Z}}_{\geq 1}.$$ (3.85)

Calculate the values for $S_1,S_2,S_3,S_4$. Write your answers as fractions in the simplest form you can. Then guess a formula for $S_n$, and prove that it is valid for all $n\in\mbox{{\bf Z}}_{\geq 1}$.

3.86   Exercise. A Let

$$T_n=\sum_{j=1}^n(2j-1)\mbox{ for all } n\in\mbox{{\bf Z}}_{\geq 1}.$$ (3.87)

Calculate the values for $T_1,T_2,T_3$, and $T_4$. Then guess a formula for $T_n$, and prove that your guess is correct.