Double Summation (Nested Sigma Notation)

A double sum like Σ_{i=1}^{3} Σ_{j=1}^{2} (i + j) means you evaluate the inner sigma completely for each value of the outer index, then add those results. The inner sum uses j as its dummy variable; the outer sum uses i. Misreading which variable belongs to which sigma is the most common failure in nested summation. You must treat the inner index as the one that runs fastest, completing all its terms before the outer index advances.

The honest version is that most errors come from misreading the index bounds or treating the sum of powers (Σk², Σk³) as if they were the same concept as an infinite power series (Σaₙxⁿ), which is a different subject entirely. A double summation is a finite sum of sums; it has nothing to do with convergence or infinite behaviour.

In the notation Σ_{i=1}^{m} Σ_{j=1}^{n} a_{i,j}, the outer index i runs from 1 to m. For each fixed i, the inner index j runs from 1 to n, adding the terms a_{i,1} + a_{i,2} + ... + a_{i,n}. The result of that inner sum becomes one term in the outer sum. The dummy variable j is bound to the inner sigma; you could rename it k or p without changing the value.

The upper bound of the inner sum (here n) is almost always a constant or depends on the outer index. If the inner bound is a constant, the region of (i,j) pairs is a rectangle. If it depends on i, like j = 1 to i, the region is triangular.

When both summations have constant bounds, evaluate the double sum by first computing the inner sum for each outer index, then summing those results. For Σ_{i=1}^{3} Σ_{j=1}^{2} (i + j), the inner sum for i=1 is (1+1)+(1+2)=5. For i=2 it is 7, and for i=3 it is 9. The outer sum is 5+7+9=21.

This works for any expression. The order of evaluation is fixed: the inner sigma runs to completion before the outer index increments. A common failure is adding the outer sum first and then multiplying, that is only valid when the expression factors into a product of independent sums.

If the expression inside a double sum factors into a product of a function of the outer index and a function of the inner index, like Σ_{i=1}^{m} Σ_{j=1}^{n} f(i)g(j), then you can separate the sum: (Σ_{i=1}^{m} f(i)) * (Σ_{j=1}^{n} g(j)). This is a direct consequence of the distributive property of multiplication over addition.

For example, Σ_{i=1}^{3} Σ_{j=1}^{2} i·j^2 equals (Σ_{i=1}^{3} i) * (Σ_{j=1}^{2} j^2) = 6 * 5 = 30. Verify by evaluating the inner sum: for i=1, inner sum = 1+4=5; i=2, 2+8=10; i=3, 3+12=15; total = 30. The separable rule works only when the expression is a product of a function of one index and a function of the other. It fails when the expression mixes indices in a sum or difference inside the product.

When the inner sum's upper bound depends on the outer index, like Σ_{i=1}^{n} Σ_{j=1}^{i} a_{i,j}, the (i,j) pairs form a triangle. These triangular double sums appear in combinatorial identities and are the main reason to learn swapping order. Graham, Knuth and Patashnik, in Concrete Mathematics (2nd ed., 1994, ch. 2.4), give the interchange rule: Σ_{i=1}^{n} Σ_{j=1}^{i} a_{i,j} = Σ_{j=1}^{n} Σ_{i=j}^{n} a_{i,j}. Swapping changes the order of summation without changing the value.

Grid Diagram of i-j Pairs for Swapped Bounds

For n=4, the original sum Σ_{i=1}^{4} Σ_{j=1}^{i} 1 counts pairs where j ≤ i. Those pairs are: (1,1), (2,1), (2,2), (3,1), (3,2), (3,3), (4,1), (4,2), (4,3), (4,4). The outer index runs down the rows; the inner index runs across columns up to the row number. Swapped, Σ_{j=1}^{4} Σ_{i=j}^{4} 1 counts the same set: for j=1, i runs 1 to 4; for j=2, i runs 2 to 4; for j=3, i runs 3 to 4; for j=4, i runs 4 to 4. The count is 10 in both cases, verifying the rule.

The swap is useful when the inner sum becomes easier after reindexing, especially when the expression has a factor that is constant in the new outer index.

Example 1: Rectangular Double Sum with Constant Expression

Evaluate Σ_{i=1}^{2} Σ_{j=1}^{3} (2i + 3j). Inner sum for i=1: (2+3)+(2+6)+(2+9)=5+8+11=24. For i=2: (4+3)+(4+6)+(4+9)=7+10+13=30. Outer sum: 24+30=54. This matches Σ_{i=1}^{2} 2i * 3 + Σ_{j=1}^{3} 3j * 2? No, the expression does not factor, so you cannot separate. The manual evaluation is the only safe path.

Example 2: Triangular Double Sum with Constant 1

Evaluate Σ_{i=1}^{4} Σ_{j=1}^{i} 1. Inner sum for i=1: 1. i=2: 2. i=3: 3. i=4: 4. Outer sum: 1+2+3+4=10. The closed form for Σ_{i=1}^{n} Σ_{j=1}^{i} 1 is n(n+1)/2. For n=4, that is 4*5/2=10.

Example 3: Triangular Double Sum with Interchange

Evaluate Σ_{i=1}^{3} Σ_{j=1}^{i} (i - j). Using the swap: Σ_{j=1}^{3} Σ_{i=j}^{3} (i - j). For j=1: i runs 1 to 3, terms (0+1+2)=3. For j=2: i runs 2 to 3, terms (0+1)=1. For j=3: i runs 3 to 3, term 0. Outer sum: 3+1+0=4. Verify directly: for i=1, inner sum = 0; i=2, inner sum = (2-1)=1; i=3, inner sum = (3-1)+(3-2)=2+1=3; total = 0+1+3=4. The swap simplified the evaluation because the inner sum became a small arithmetic series.

Double summation appears in matrix multiplication, where each entry of the product is a sum over the inner index. In probability tables, the sum over all cells of a joint distribution is a double sum. In statistics, the sum of squared deviations from a mean involves a double sum over data points. Riemann sums for double integrals use nested sigma notation over a grid of partitions. Graham, Knuth and Patashnik treat multiple sums extensively in Concrete Mathematics ch. 2.4, showing how to manipulate them for combinatorial identities.

Related topics like summation properties (constant multiple, sum/difference) are handled elsewhere. The formulas for arithmetic, geometric, and power sums (like Σk, Σk², Σk³) are assumed knowledge when working with double sums. If you need to calculate summation manually, you use those closed forms inside the nested sum.

Region	Sum of 1 (count of pairs)	Closed Form
Rectangular m×n	m n	m n
Triangular (j ≤ i)	n(n+1)/2	n(n+1)/2
Triangular (i ≤ j)	n(n+1)/2	n(n+1)/2

The single thing that most often goes wrong is assuming you can swap the order of summation without changing the bounds. You cannot. Swapping requires adjusting the bounds so that the set of (i,j) pairs remains identical. A rectangular double sum with constant bounds swaps directly, the inner and outer bounds just trade places. A triangular double sum requires the rule from Concrete Mathematics: the new inner bound becomes the old outer index. If you swap without adjusting, you get a different sum, and you will not know until you check a small case.