Finite Sums and Summation Techniques

A finite sum adds one contribution for each index in a finite set. Most summation errors come from changing that index set, losing a boundary term, or counting some contributions twice. This chapter develops techniques around those three checks. Sequences and Series supplies the arithmetic and geometric examples.

Read the index set before manipulating the formula

For a finite set $I$ and real or complex numbers $a_i$, the notation

$$\sum_{i\in I}a_i$$

means to add the indexed contributions. Equal values at different indices still contribute separately. For an integer range $m\le n$, there are $n-m+1$ terms from $m$ through $n$. We interpret a range with no admissible indices as an empty sum, whose value is $0$.

The index is a bound variable: renaming it changes nothing if every occurrence bound by that sum is renamed consistently. An index outside the sum may remain a free parameter. In a nested sum, use distinct names for independent indices.

For example,

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

Here $k$ varies, while $x$ is fixed. A sum indexed by a finite set can be reordered because addition is associative and commutative. These statements do not automatically extend to infinite series.

Linearity and reindexing

For constants $\alpha,\beta$ and the same finite index set $I$,

$$\sum_{i\in I}(\alpha a_i+\beta b_i) =\alpha\sum_{i\in I}a_i+\beta\sum_{i\in I}b_i.$$

This follows by distributing and regrouping finitely many terms. The factors must be independent of the index being summed. A quantity may be constant for an inner sum but vary in an outer one.

Reindexing requires a bijection between the old and new index sets. If $\phi:J\to I$ is bijective, then

$$\sum_{i\in I}a_i=\sum_{j\in J}a_{\phi(j)}.$$

Every original contribution appears exactly once. For $n\ge0$, setting $j=k-1$ gives

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

Both the bounds and the summand change. Reversing a range instead uses $j=n+1-k$, sending $1,\ldots,n$ to $n,\ldots,1$. This is the mechanism behind pairing the first and last terms of an arithmetic sum.

Telescoping: preserve the endpoints

Adjacent differences cancel:

$$\sum_{k=0}^{n-1}(u_{k+1}-u_k)=u_n-u_0.$$

Write out the first and last few terms to see which survive. At $n=0$, both sides are zero. A useful example, for $n\ge1$, is

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

so

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

The cancellation works because the decomposition creates matching interior terms. It does not permit deleting unrelated terms merely because they look similar.

Summation by parts

The discrete product difference can be written as

$$\begin{aligned} a_{k+1}b_{k+1}-a_kb_k &=(a_{k+1}-a_k)b_k\\ &\quad+a_{k+1}(b_{k+1}-b_k). \end{aligned}$$

Sum this equality for $0\le k<n$. The left side telescopes. With $\Delta a_k=a_{k+1}-a_k$ and $\Delta b_k=b_{k+1}-b_k$, rearrangement yields

$$\begin{aligned} \sum_{k=0}^{n-1}\Delta a_k\,b_k &=a_nb_n-a_0b_0\\ &\quad-\sum_{k=0}^{n-1}a_{k+1}\Delta b_k. \end{aligned}$$

This identity holds for $n\ge0$. The shifted factor $a_{k+1}$ is essential; replacing it by $a_k$ changes the identity. Like integration by parts, the technique transfers a difference from one factor to the other, sometimes leaving an easier sum.

For example, put $a_k=k$ and $b_k=r^k$. Let

$$G_n=\sum_{k=0}^{n-1}r^k, \qquad W_n=\sum_{k=0}^{n-1}(k+1)r^k.$$

For $r\ne1$, summation by parts gives $G_n=nr^n-(r-1)W_n$. Substituting the geometric formula gives

$$W_n=\frac{1-(n+1)r^n+nr^{n+1}}{(1-r)^2}.$$

At $r=1$, use $W_n=n(n+1)/2$ instead. At $n=0$ the sum is empty. Zeroth powers here denote the constant term, including when $r=0$.

Multiple sums are sums over tuples

A rectangular double sum visits each pair in $I\times J$ once:

$$\sum_{i\in I}\sum_{j\in J}c_{ij} =\sum_{j\in J}\sum_{i\in I}c_{ij}.$$

Both index sets must be finite here. If $c_{ij}=a_i b_j$, distributivity gives

$$\sum_{i\in I}\sum_{j\in J}a_i b_j =\left(\sum_{i\in I}a_i\right) \left(\sum_{j\in J}b_j\right).$$

This factorization relies on the rectangular domain and the separated factors. It is generally wrong over a triangular region such as $i<j$.

For a triangle, describe the same pairs using the other outer index:

$$\sum_{i=1}^{n}\sum_{j=i}^{n}c_{ij} =\sum_{j=1}^{n}\sum_{i=1}^{j}c_{ij}.$$

On the left, fix $i$ and range from $j=i$ to $n$. On the right, fix $j$ and range from $i=1$ to $j$. Both describe $1\le i\le j\le n$. With $c_{ij}=1$, each side counts $n(n+1)/2$ pairs, not $n^2$.

An extra index creates extra multiplicity even if the summand does not mention it. For $m,n\ge1$,

$$\sum_{h=1}^{m}\sum_{i=1}^{n}\sum_{j=1}^{n}a_i b_j =m\left(\sum_{i=1}^{n}a_i\right) \left(\sum_{j=1}^{n}b_j\right).$$

There are $m$ identical copies of the double sum. An unused index cannot simply be erased.

Exercises

ExerciseReindex without changing the terms

Rewrite the following sum with an index starting at zero, then evaluate it:

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

Show solution

Solution

Set $j=k-3$. The bounds become $0\le j\le4$, and the summand becomes $2j+5$. The five terms are $5,7,9,11,13$, giving $45$. Keeping $2j-1$ after changing the bounds would change the sum.

ExerciseReverse a three-index region

Write the sum over $1\le i<j<k\le4$ in two nested orders, with the innermost sum first ranging over $k$, then over $i$.

Show solution

Solution

The two expressions are

$$\sum_{i=1}^{2}\sum_{j=i+1}^{3}\sum_{k=j+1}^{4}a_{ijk},$$$$\sum_{k=3}^{4}\sum_{j=2}^{k-1}\sum_{i=1}^{j-1}a_{ijk}.$$

Both contain exactly $a_{123},a_{124},a_{134},a_{234}$. Listing the tuples verifies the bounds directly.

ExerciseDo not identify independent indices

Assume $a_1,\ldots,a_n$ are nonzero. Is the product below always $n$?

$$\left(\sum_{i=1}^{n}a_i\right) \left(\sum_{j=1}^{n}\frac1{a_j}\right)$$

Show solution

Solution

No. Its expansion includes all $n^2$ pairs, not just the diagonal $i=j$:

$$\sum_{i=1}^{n}\sum_{j=1}^{n}\frac{a_i}{a_j} =n+\sum_{\substack{1\le i,j\le n\\i\ne j}}\frac{a_i}{a_j}.$$

For $n=2$ and $a_1=a_2=1$, the product is $4$, whereas $n=2$. Renaming a bound index is valid only when it does not merge previously independent indices.

ExerciseUse a telescoping product difference

Derive the summation-by-parts identity above directly from the product difference. Check it for $n=1$.

Show solution

Solution

Summing the product difference cancels all intermediate products, leaving $a_nb_n-a_0b_0$. Subtract the sum containing $\Delta b_k$ to isolate the other sum. At $n=1$, the right side reduces to

$$a_1b_1-a_0b_0-a_1(b_1-b_0)=(a_1-a_0)b_0,$$

which is precisely the single term on the left. This also checks the placement of the shift.

ExerciseAntisymmetry and the square-sum identity

For real numbers $a_i,b_i$, put $c_{ij}=a_i b_j-a_j b_i$. Evaluate the sum of all $c_{ij}$ for $1\le i,j\le n$, and simplify the sum of their squares.

Show solution

Solution

Since $c_{ji}=-c_{ij}$ and $c_{ii}=0$, the unsquared terms cancel in pairs. For the squares, paired terms are equal, so

$$\sum_{i=1}^{n}\sum_{j=1}^{n}c_{ij}=0.$$$$\sum_{i=1}^{n}\sum_{j=1}^{n}c_{ij}^2 =2\sum_{1\le i<j\le n}c_{ij}^2.$$

There are $n(n-1)/2$ off-diagonal pairs. Define

$$\begin{aligned} A&=\sum_{i=1}^{n}a_i^2,\\ B&=\sum_{i=1}^{n}b_i^2,\\ C&=\sum_{i=1}^{n}a_i b_i. \end{aligned}$$

Expanding each square and factoring the rectangular sums gives $AB$ from each of the two square terms and $-2C^2$ from the cross term. Hence

$$\sum_{i=1}^{n}\sum_{j=1}^{n}c_{ij}^2=2(AB-C^2),$$

and therefore

$$AB-C^2=\sum_{1\le i<j\le n}(a_i b_j-a_j b_i)^2.$$

This is Lagrange’s identity. Its nonnegative right side implies the real Cauchy–Schwarz inequality; see Inequalities. Restricting a sum to $i<j$ requires grouping entire symmetric pairs, not simply deleting a diagonal and changing two independent bounds.

ExerciseWhich infinite extension is being claimed?

Does finite cancellation alone justify changing the order of an infinite double series? What remains true about the square partial sums of the antisymmetric array above?

Discussion guide

Solution

Every square partial sum over $1\le i,j\le n$ is zero, so that particular sequence of partial sums has limit zero. This does not establish existence or equality of iterated infinite sums: those use a different limiting procedure. Absolute convergence of a double series is a sufficient condition for freely reordering its terms. Conditional convergence requires more care. Continue with Infinite Series before extending finite reindexing rules to infinite sums.