Summation, Products, and Finite Structure

Motivation

You need arithmetic with fractions and the distributive law. By the end of this chapter, you should be able to read and construct indexed sums and products, change an index without changing the terms, derive simple finite accumulation formulas, and check what a formula means at its endpoints. These skills are used in data summaries, repeated changes and the infinite series of Chapter 6.

A large symbol is not a new kind of arithmetic. It is a compact instruction telling us which ordinary additions or multiplications to perform. Much of the difficulty lies in reading the instruction rather than carrying out the operations.

5.1 The index is an instruction, not an extra variable

Definition

For integers $m\le n$ and numbers $a_m,\ldots,a_n$, define

$$\sum_{k=m}^{n}a_k=a_m+a_{m+1}+\cdots+a_n.$$

The symbol $k$ is the index, $m$ is the lower limit, and $n$ the upper limit. Both endpoints are included, so there are $n-m+1$ terms. The expression being summed is the summand. To evaluate it, replace every occurrence of the index in the summand by each permitted integer.

For example,

$$\sum_{k=2}^{5}(2k-1)=3+5+7+9=24.$$

There are four terms, not three and not five. A factor independent of the index is repeated unchanged:

$$\sum_{k=1}^{n}c=nc\qquad(n\ge1).$$

In a finite sum the index is a bound or dummy variable: $\sum_{k=1}^{n}k^2=\sum_{j=1}^{n}j^2$. Renaming it does not change the number. A variable not bound by the summation sign remains a parameter. For example,

$$F(x)=\sum_{k=1}^{3}(x+k)=3x+6.$$

Here $x$ is free to vary; $k$ is not an argument of $F$.

Worked example

Worked example 1: translating data notation. Four readings are $x_1=3$, $x_2=5$, $x_3=4$, $x_4=8$. Then

$$\sum_{i=1}^{4}x_i=20,\qquad \sum_{i=1}^{4}x_i^2=9+25+16+64=114.$$

But $(\sum_{i=1}^{4}x_i)^2=400$. Squaring a sum creates cross terms; it does not simply square each summand. The sample arithmetic mean is $\bar x=(1/4)\sum_i x_i=5$, with the same unit as each reading.

The notation $\sum_i$ without endpoints is acceptable only when the index set has already been specified. It must not silently change from one calculation to another.

5.2 Algebra of finite sums

Proposition

If $a_k,b_k$ are defined for the same integer range and $\alpha,\beta$ are constants independent of $k$, the distributive law gives

$$\sum_{k=m}^{n}(\alpha a_k+\beta b_k) =\alpha\sum_{k=m}^{n}a_k+\beta\sum_{k=m}^{n}b_k.$$

Proof

This is linearity. It is proved by expanding both sides into their finite lists of terms and regrouping. It does not require the terms to be positive.

Splitting a range at an integer $p$ with $m\le p<n$ gives

$$\sum_{k=m}^{n}a_k=\sum_{k=m}^{p}a_k+\sum_{k=p+1}^{n}a_k.$$

The second sum starts at $p+1$: starting it at $p$ would count one term twice.

Common mistake

A constant may be taken outside, but an index-dependent expression may not. The expression $\sum_{k=1}^{n}ka_k$ cannot be rewritten as $k\sum_{k=1}^{n}a_k$: there is no single value of $k$ left after summation.

Worked example

Worked example 2: an algebraic total. Since $1+\cdots+5=15$,

$$\sum_{k=1}^{5}(3k-2)=3(15)-2(5)=35.$$

The second contribution is $2$ repeated five times, not a single subtraction of $2$.

5.3 Reindexing preserves the list

A change of index must change both the summand and the limits. If $j=k-m$, then $k=m$ corresponds to $j=0$ and $k=n$ to $j=n-m$. Thus

$$\sum_{k=m}^{n}a_k=\sum_{j=0}^{n-m}a_{j+m}.$$

One can check a reindexing by comparing the first term, the last term, and the number of terms. Those three checks catch many errors.

Worked example

Worked example 3: a shifted model. Rewrite $\sum_{k=3}^{7}(k-2)^2$ with lower index zero. Let $j=k-3$. The result is

$$\sum_{j=0}^{4}(j+1)^2=1^2+2^2+3^2+4^2+5^2=55.$$

Replacing $k$ by $j$ in the original formula without changing the limits would not perform this shift.

Reversing an order is also possible. In $\sum_{k=0}^{n}a_k$, set $j=n-k$. Then the same terms appear as $a_n,a_{n-1},\ldots,a_0$, so

$$\sum_{k=0}^{n}a_k=\sum_{j=0}^{n}a_{n-j}.$$

For finite real or complex sums, reordering is valid because addition is associative and commutative. Chapter 6 will not assume this permission automatically for arbitrary infinite series.

5.4 Arithmetic totals and telescoping

For an integer $n\ge1$, let $S=1+2+\cdots+n$. Reverse the order and add corresponding terms:

$$2S=(1+n)+(2+n-1)+\cdots+(n+1)=n(n+1).$$

There are $n$ pairs, each equal to $n+1$. Therefore

$$\sum_{k=1}^{n}k=\frac{n(n+1)}2.$$

This proof works whether $n$ is odd or even: we added two full lists rather than trying to partition one list into pairs. An arithmetic progression with first term $a$ and common difference $d$ has $k$th term $a+(k-1)d$ and total

$$\sum_{k=1}^{n}[a+(k-1)d] =na+\frac{dn(n-1)}2=\frac n2[2a+(n-1)d].$$

Worked example

Worked example 4: a planned sequence of measurements. A study schedules $12$ measurements, starting $5$ minutes after the reference time and increasing each measurement time by $3$ minutes. The times are $5,8,\ldots,38$ minutes. Their mean is $(5+38)/2=21.5$ minutes, and their sum is $12(21.5)=258$ minutes. The sum is a sum of timestamps relative to the reference, not the elapsed duration of the study; the last measurement occurs at $38$ minutes.

Proposition

A sum telescopes when most terms cancel after expansion. For any defined $b_1,\ldots,b_{n+1}$,

$$\sum_{k=1}^{n}(b_k-b_{k+1})=b_1-b_{n+1}.$$

The intermediate $b_2,\ldots,b_n$ appear once with each sign. Cancellation is valid because this is a finite expression.

Worked example

Worked example 5: a rational telescope. For positive integers $k$,

$$\frac1{k(k+1)}=\frac1k-\frac1{k+1}.$$

Hence

$$\sum_{k=1}^{n}\frac1{k(k+1)}=1-\frac1{n+1}=\frac n{n+1}.$$

The identity is proved by a common denominator before it is summed. At $n=1$ the formula gives $1/2$, which checks the lower endpoint. A telescope removes middle terms, not the final boundary term.

The finite geometric formula already derived in Chapter 3 is another accumulation identity. In current notation, for $n\ge1$,

$$\sum_{k=0}^{n-1}ar^k=\begin{cases} a(1-r^n)/(1-r),&r\ne1,\\ na,&r=1. \end{cases}$$

Here the first term is $a$, and the last is $ar^{n-1}$. This formula is finite and valid even when $|r|>1$; convergence is not a question until an infinite limit is proposed.

5.5 Product notation, factorials and cancellation

Definition

Define the corresponding product by

$$\prod_{k=m}^{n}a_k=a_ma_{m+1}\cdots a_n\qquad(m\le n).$$

The expression $a_k$ is now the factor. For an integer $n\ge1$, the factorial is $n!=\prod_{k=1}^{n}k$. We set $0!=1$; there are no positive integers from one through zero to multiply. More generally, the empty sum is $0$ and the empty product is $1$. These are the additive and multiplicative identity elements. Whenever an empty range is used here it contains no indices; it is not an instruction to sum backwards.

A product containing a zero factor is zero. A quotient of products requires a nonzero denominator. If all relevant factors are defined,

$$\prod_{k=m}^{n}(a_kb_k)=\left(\prod_{k=m}^{n}a_k\right)\left(\prod_{k=m}^{n}b_k\right),$$

and, when every $b_k\ne0$,

$$\prod_{k=m}^{n}\frac{a_k}{b_k}= \frac{\prod_{k=m}^{n}a_k}{\prod_{k=m}^{n}b_k}.$$

For $N=n-m+1$ factors, $\prod_{k=m}^{n}(ca_k)=c^N\prod_{k=m}^{n}a_k$. This is not $c\prod a_k$ unless special values make them coincide. Products do not have sum-like linearity: generally $\prod(a_k+b_k)\ne\prod a_k+\prod b_k$.

Worked example

Worked example 6: a telescoping product. For $n\ge1$,

$$\prod_{k=1}^{n}\frac{k+1}{k} =\frac21\frac32\cdots\frac{n+1}{n}=n+1.$$

All cancelled factors are nonzero. At $n=0$, interpreting the left side as empty gives $1$, consistent with $n+1$. By contrast, an expression with a denominator that vanishes at some index is undefined; an attractive cancellation pattern does not make division by zero legitimate.

Worked example

Worked example 7: varying percentage changes. A dimensionless fraction $p_k$ changes an amount by the multiplier $1+p_k$ during stage $k$. Starting from $Q_0$, the amount after $n$ stages is

$$Q_n=Q_0\prod_{k=1}^{n}(1+p_k).$$

For a $10\%$ rise followed by a $10\%$ fall, the multiplier is $1.1(0.9)=0.99$, so the final amount is $99\%$ of the starting amount. Adding the percentages would miss the changing base. For nonnegative amounts, a stage multiplier should be nonnegative; a negative algebraic multiplier would need a different model interpretation.

5.6 Two indices and a statistical identity

A finite rectangular double sum is

$$\sum_{i=1}^{m}\sum_{j=1}^{n}a_{ij} =\sum_{i=1}^{m}(a_{i1}+\cdots+a_{in}).$$

Every table entry appears once. Therefore one can sum by columns instead of by rows. In particular, ordinary finite distributivity gives

$$\left(\sum_{i=1}^{m}u_i\right)\left(\sum_{j=1}^{n}v_j\right) =\sum_{i=1}^{m}\sum_{j=1}^{n}u_iv_j.$$

The indices must be independent. For example, $(u_1+u_2)(v_1+v_2)$ has four terms, not only the two matching-index terms $u_1v_1+u_2v_2$. This is an algebraic fact and does not assume any statistical independence.

For real observations $x_1,\ldots,x_n$ with $n\ge1$, let $\bar x=(1/n)\sum_i x_i$. Expanding each square and using linearity gives

$$\begin{aligned} \sum_{i=1}^{n}(x_i-\bar x)^2 &=\sum_i x_i^2-2\bar x\sum_i x_i+\sum_i\bar x^2\\ &=\sum_i x_i^2-2n\bar x^2+n\bar x^2\\ &=\sum_i x_i^2-n\bar x^2. \end{aligned}$$

This identity concerns the total squared deviation; dividing by $n$ or by $n-1$ belongs to different statistical conventions. The $n-1$ convention is not defined at $n=1$. For the readings in Example 1, the squared-deviation total is $114-4(25)=14$, also $4+0+1+9$ by direct computation. Its unit is the square of the reading unit.

5.7 Graded exercises

Foundation

Checkpoint

Exercise 1

1. Expand and evaluate $\sum_{k=0}^{3}(2k+1)$ and $\prod_{k=1}^{4}(k+1)$.

Checkpoint

Exercise 2

2. How many terms are in $\sum_{j=4}^{n}a_j$ for $n\ge4$? Evaluate $\sum_{j=4}^{8}7$.

Checkpoint

Exercise 3

3. For $a_1=1,a_2=-2,a_3=4$, evaluate $\sum a_i$, $\sum a_i^2$, and $(\sum a_i)^2$ over $i=1,2,3$.

Checkpoint

Exercise 4

4. Explain why $\prod_{k=1}^{3}(2a_k)$ equals $8a_1a_2a_3$, not $2a_1a_2a_3$.

Core

Checkpoint

Exercise 5

5. Rewrite $\sum_{k=5}^{9}(k-4)^3$ with lower index zero. State the first and last terms.

Checkpoint

Exercise 6

6. Derive a closed formula for $\sum_{k=1}^{n}(4k-1)$, $n\ge1$. Check $n=1$ and $n=3$.

Checkpoint

Exercise 7

7. Evaluate $\sum_{k=2}^{n}1/[k(k+1)]$ for $n\ge2$.

Checkpoint

Exercise 8

8. Evaluate $\prod_{k=2}^{n}(k-1)/k$ for $n\ge2$. Give the empty-product value at $n=1$ and test whether the same closed formula fits.

Checkpoint

Exercise 9

9. A population model has consecutive multipliers $1.2$, $0.75$ and $1.1$. What fraction of its original amount remains? Is the overall percentage change the sum $20-25+10$?

Checkpoint

Exercise 10

10. Evaluate $\sum_{i=1}^{2}\sum_{j=1}^{3}(i+2j)$ by rows and by columns.

Synthesis

Checkpoint

Exercise 11

11. Prove $\sum_{k=1}^{n}(2k-1)=n^2$ using the arithmetic-sum formula. Interpret why the first $n$ odd positive integers are being counted, including the last term.

Checkpoint

Exercise 12

12. For $x_1=2,x_2=4,x_3=9$, find the mean and total squared deviation exactly, both by expansion and by the identity in §5.6.

Checkpoint

Exercise 13

13. For $n\ge1$, simplify $\prod_{k=1}^{n}(1-1/(k+1)^2)$. Show the cancellation carefully; do not cancel across addition.

Checkpoint

Exercise 14

14. A student writes $\sum_{k=1}^{n}x^k=x\sum_{k=1}^{n}x^{k-1}=x(1-x^n)/(1-x)$. State the values of $x$ for which the quotient formula is valid. Give the separate answer at the excluded value and check $x=0$.

Checkpoint

Exercise 15

15. With $a_1=1,a_2=2$ and $b_1=3,b_2=5$, give a numerical counterexample to $\prod_{k=1}^{2}(a_k+b_k)=\prod_{k=1}^{2}a_k+\prod_{k=1}^{2}b_k$.

Checkpoint

Exercise 16

16. Suppose $q_1,\ldots,q_n>0$, $n\ge1$. Prove $\ln(\prod_{k=1}^{n}q_k)=\sum_{k=1}^{n}\ln q_k$ by repeated use of the two-factor logarithm law. Explain why one nonpositive factor invalidates this real-logarithm statement even when the final product happens to be positive.

5.8 Full solutions

Solution · Exercise 1

1. The sum is $1+3+5+7=16$. The product is $2\cdot3\cdot4\cdot5=120$.

Solution · Exercise 2

2. There are $n-4+1=n-3$ terms. For upper limit eight there are five terms, giving $35$.

Solution · Exercise 3

3. The sum is $1-2+4=3$. The sum of squares is $1+4+16=21$, whereas the square of the sum is $9$. Their difference reflects cross terms.

Solution · Exercise 4

4. There are three separate factors of two: $(2a_1)(2a_2)(2a_3)=2^3a_1a_2a_3$. This remains true when any $a_k=0$.

Solution · Exercise 5

5. Set $j=k-5$, so $k-4=j+1$. The result is $\sum_{j=0}^{4}(j+1)^3$, starting at $1^3$ and ending at $5^3$.

Solution · Exercise 6

6. Linearity gives $4n(n+1)/2-n=2n^2+n=n(2n+1)$. At one this is $3$; at three it is $21$, agreeing with $3+7+11$.

Solution · Exercise 7

7. Write each term as $1/k-1/(k+1)$. The remaining boundary terms are $1/2-1/(n+1)=(n-1)/[2(n+1)]$. At $n=2$, this is $1/6$, the one term in the sum.

Solution · Exercise 8

8. The product is $(1/2)(2/3)\cdots((n-1)/n)=1/n$. At $n=1$ the empty product is $1$, which agrees with $1/n=1$.

Solution · Exercise 9

9. The exact multiplier is $(6/5)(3/4)(11/10)=99/100$. Thus $99\%$ remains and the overall change is a $1\%$ decrease. The sum of the stage percentages is $5\%$, which does not account for their different bases.

Solution · Exercise 10

10. Rows give $(3+5+7)+(4+6+8)=15+18=33$. Columns give $(3+4)+(5+6)+(7+8)=7+11+15=33$. Each of six entries is included once.

Solution · Exercise 11

11. Linearity gives $2[n(n+1)/2]-n=n^2$. The indexed expression starts at one, increases by two, and ends at $2n-1$, so it lists exactly the first $n$ positive odd integers. At $n=1$ both sides equal one.

Solution · Exercise 12

12. The mean is $15/3=5$. Directly, the total is $(2-5)^2+(4-5)^2+(9-5)^2=9+1+16=26$. The identity gives $4+16+81-3(25)=101-75=26$.

Solution · Exercise 13

13. Since $1-1/(k+1)^2=k(k+2)/(k+1)^2$, separate the product into $\prod_{k=1}^{n}k/(k+1)$ and $\prod_{k=1}^{n}(k+2)/(k+1)$. They are $1/(n+1)$ and $(n+2)/2$, giving $(n+2)/[2(n+1)]$. At $n=1$, this is $3/4$, agreeing with the original first factor. The decomposition used multiplication after factoring a difference of squares, not cancellation of a term inside a sum.

Solution · Exercise 14

14. For every real $x\ne1$, the finite quotient formula is valid. At $x=1$ the sum is $n$. At $x=0$ the original sum, whose powers start at one, is zero and the quotient gives zero. The finite geometric expression $\sum_{k=0}^{n-1}x^k$ treats its constant term as one, including when $x=0$; it does not require defining a general indeterminate expression $0^0$.

Solution · Exercise 15

15. The left side is $(1+3)(2+5)=28$. The proposed right side is $1\cdot2+3\cdot5=17$, so the proposed law is false.

The two-factor logarithm law used in the following solution is proved in Chapter 9, using the real-power foundation.

Solution · Exercise 16

16. For $n=1$ the statement is immediate. Combining the first two positive factors gives $\ln(q_1q_2)=\ln q_1+\ln q_2$; combining their positive product with $q_3$ adds $\ln q_3$. Continue through the finite list, producing all $n$ terms. Positivity makes every logarithm defined. Two negative factors can have a positive product, but their individual real logarithms are undefined; a zero factor makes the logarithm of the product undefined as well.

Summary

• A finite sum lists additions; a finite product lists multiplications. Endpoints and the number of terms are part of the meaning.
• Sums are linear; a product of termwise products splits into two products, but products do not similarly split over addition.
• Reindex by changing the index expression and both limits. Compare the first and last terms.
• Arithmetic totals, telescoping and geometric totals are exact finite identities. Check exceptional denominators separately.
• Empty sums and products are zero and one. Nonempty denominators still must not vanish.
• Data means and squared deviations illustrate why the distinction between a sum of squares and a squared sum matters.

Connections. Finite partial sums lead to Chapter 6's definition of an infinite series. The identities here supply statements to prove by induction in Chapter 7. Product multipliers connect with exponent and logarithm laws in Chapter 9. The matrix-entry notation in Chapter 4 is an indexed sum.