A sum is a loop.

acc = 0
for i in range(1, 5 + 1):
    acc += i

Try it before reading on. Press Play and watch the running total grow one term at a time; press n < m: empty and see that a sum with no terms is not an error; press 1/i through 0 and see what happens when one term does not exist. Under the picture, the verdict compares the loop with a closed-form formula whenever one applies. By the end of the chapter you will read a sum as a loop, count its terms correctly, and know which rewrites keep its value.

Intuition: a sum is a loop

Every sum in a machine-learning paper is a loop in disguise. The average loss over a batch is a loop over examples. The score of a linear model is a loop over features. A dot product is a loop over coordinates. Writing the loop in mathematical notation is shorter, and the notation also tells you three things you must not get wrong: where the loop starts, where it stops, and what is added each time.

The picture is an accumulator. Start with a total of $0$. For each index in turn, compute a term and add it to the total. When the indices run out, the total is the answer. Nothing else is going on: the sum symbol is the word for, the bounds are the range, and the body is what the loop adds.

Two features of that picture need care, because they are the source of nearly every error with sums:

• Both ends are included. In mathematics the sum from $i=m$ to $i=n$ includes the term at $n$. Python’s range does not: range(m, n) stops before $n$. Counting the terms is a fencepost problem: from $3$ to $11$ there are nine terms, not eight.
• A sum can have no terms. If the stop is below the start, the loop does nothing and the total stays at its starting value $0$. That is a number, not a failure, and it is the right answer to a question such as “the average of nothing is a sum over no examples”.

The index itself is a dummy: renaming $i$ as $k$ changes nothing, exactly as renaming a loop variable changes nothing in code. What matters is the range and the body.

Definition

Sigma notation. For integers $m$ and $n$ and a rule that gives a number $a_i$ for each integer $i$ in the range,

The integer $m$ is the lower bound, $n$ the upper bound, $i$ the index and $a_i$ the term (or body). Both bounds are included.

The number of terms. If $n\ge m$, the sum has $n-m+1$ terms. The “plus one” is the fencepost: a fence from post $3$ to post $11$ has nine posts and eight gaps.

The empty sum. If $n<m$ there are no indices, and by convention the sum equals $0$, the starting value of the accumulator. This is the only value that keeps the rules below true for every range, and it is what the loop returns.

A term that does not exist. If the rule is not defined at some index in the range, the sum is undefined; it is not $0$ and the offending term is not skipped. For example $\sum_{i=-2}^{3} \frac1i$ is undefined, because $\frac10$ does not exist.

Closed forms. Some sums have a formula that gives the result without adding the terms. For $n\ge 1$:

A constant added $n-m+1$ times gives $\sum_{i=m}^{n} c=(n-m+1)\,c$. A geometric sum has a term that is a constant ratio $r$ to the power of the index. If $r\ne1$,

and if $r=1$ every term is $1$, so the sum is $n-m+1$. The geometric formula comes from a telescoping trick: multiplying the sum by $(1-r)$ makes every term but the first and the last cancel in pairs.

A convention to notice. In a geometric sum the term at $i=0$ is $r^{0}$, and we read it as $1$ for every $r$, including $r=0$ (it is the empty product, and it is what Python’s Fraction(0) ** 0 gives). Chapter I.1 leaves $0^{0}$ undefined for ordinary powers of numbers; the two do not conflict, because here the convention belongs to the notation of a geometric sequence and is stated, not smuggled in. A negative power of $0$ stays undefined everywhere: if $r=0$ and a term needs $r^{i}$ with $i<0$, the sum is undefined. An empty sum is different again: it has no terms, so it is $0$ even when the bounds are ones where $r^{m}$ would not exist.

Rules for rewriting a sum. For the same bounds on both sums and constants $c$:

In the shift, $j=i+k$, so $i=j-k$: the bounds go up by $k$, and the term must be rewritten with $j-k$ wherever it had $i$.

Double sums. A sum can have a sum as its body. In $\sum_{i=1}^{n}\sum_{j=1}^{k}a_{ij}$ the inner sum is added completely for each $i$, so the cells $a_{ij}$ of a grid are added row by row. For a finite grid the total does not depend on the order, so adding column by column gives the same number. If the inner bound depends on the outer index, as in $\sum_{i=1}^{n}\sum_{j=1}^{i}a_{ij}$, the cells form a triangle, and swapping the order means rewriting the bounds so that the same cells are visited.

Python is zero-based. A list a stores its first entry at position $0$. If the mathematics indexes from $1$, then $a_i$ is a[i - 1]. Mixing the two conventions is the most common way to get a sum quietly wrong.

Mechanics: how to work with a sum

Off by one: five loops, one sum

The four numbers $m$, $n$, the start of the range and the stop of the range are easy to mix up. The stage below runs five loops for the same sum, shows the Python of each, and reports which ones return the true value. For the sum to be informative the terms are chosen so that a mistake changes the result.

a = [1, 3, 5, 7, 9]  # a[0] is a_1

Read the cards in turn for the odd numbers from $1$ to $5$. The loop that stops one early misses the last term. The loop whose window slides down by one adds a term before the start and drops the last one. The unshifted list loop reads one position too far and Python raises an error, and a version with a negative index would not raise at all but would silently read the end of the list. Then change the terms to the whole numbers: the extra term at $i=0$ is $0$, so the slid window and the loop that stops early return the same total, and the total alone cannot tell you which slip you made. A single test case is never proof that the bounds are right.

Double sums: rows, columns and triangles

acc = 0
for i in range(1, 3 + 1):
    for j in range(1, 4 + 1):
        acc += i * j

On a rectangle the order cannot matter: both orders add the same cells, and the stage shows the two totals agreeing. When the entry factors as a function of $i$ times a function of $j$, the double sum is a product of two single sums, which is why the first preset needs only a few additions. On a triangle the swap needs care: the inner bounds must be rewritten, and the verdict reports what the loop would return if its bounds were not rewritten: it visits the other triangle. When the entries are symmetric, such as $i\cdot j$, the other triangle happens to have the same total, so the slip goes unnoticed; a data table with unequal entries shows it.

Rewriting a sum: three rules

Three observations, each visible in the panels. Linearity lets you move a constant out of a sum and split a sum of two terms into two sums; both sides always agree, including for negative constants and for ranges that contain negative indices. Shifting the index is correct only when the term changes with it: moving the bounds and leaving the body alone computes a different sum. Look for the preset where the wrong shift happens to give the right number by coincidence, and notice that this is not a reason to trust it. Finally, Gauss’s pairing explains the closed form for consecutive whole numbers: the first and last add to the same total as the second and second-last, and so on. When the number of terms is odd, one middle term has no partner.

Worked examples

Five computations, each shown step by step with every number taken from the same model as the stages. Step forward and back with the buttons, or press Play; going back selects an earlier step, and nothing is undone.

Executable reference code

Run the Python examples below to follow the calculations step by step. The comments record what each line returns.

First the loop itself, with exact fractions so that no rounding enters. It shows the accumulator, the empty sum, the closed forms checked against the loop, the geometric sum including the case $r=1$, and the off-by-one variants on a zero-based list.

from fractions import Fraction

# The sum of a_i for i = m, ..., n (both ends INCLUDED) is a loop with an accumulator.
# Python's range(start, stop) stops BEFORE stop, so the loop that visits i = m, ..., n is range(m, n + 1).


def summation(term, m, n):
    acc = Fraction(0)  # the empty sum: the value before any term has been added
    for i in range(m, n + 1):
        acc += term(i)
    return acc


total = summation(lambda i: Fraction(i), 1, 5)  # 1 + 2 + 3 + 4 + 5 = 15
squares = summation(lambda i: Fraction(i) ** 2, 1, 5)  # 1 + 4 + 9 + 16 + 25 = 55
empty = summation(lambda i: Fraction(i), 3, 2)  # n < m: range(3, 3) has no values, so the sum is 0
single = summation(lambda i: Fraction(i), 4, 4)  # one term

# Closed forms are claims about EVERY n; compare them with the loop for a few bounds.
n = 10
gauss_ok = summation(lambda i: Fraction(i), 1, n) == Fraction(n * (n + 1), 2)  # n(n+1)/2
squares_ok = summation(lambda i: Fraction(i) ** 2, 1, n) == Fraction(n * (n + 1) * (2 * n + 1), 6)
odd_ok = summation(lambda i: Fraction(2 * i - 1), 1, n) == n**2  # the first n odd numbers add up to n squared

# Geometric: (1 - r) * (r**m + ... + r**n) telescopes to r**m - r**(n + 1), so for r != 1 the sum is (r**m - r**(n+1)) / (1 - r).
# Convention (stated in I.8; I.1 leaves 0**0 undefined for ordinary powers): the term r**0 of a geometric sum is 1 for every r, even r = 0,
# which is what Fraction(0) ** 0 gives. A negative power of 0 (r = 0, i < 0) is an error; an empty range(...) never evaluates it.
r = Fraction(1, 2)
geometric = summation(lambda i: r**i, 0, 4)  # 1 + 1/2 + 1/4 + 1/8 + 1/16 = 31/16
geometric_closed = (r**0 - r**5) / (1 - r)
geometric_ok = geometric == geometric_closed
all_ones = summation(lambda i: Fraction(1) ** i, 0, 4)  # r = 1 needs its own formula: n - m + 1 = 5, not 0/0

# Off-by-one: the same sum written four ways. Only the first one is the mathematical sum from 1 to 5.
a = [Fraction(2 * i - 1) for i in range(1, 6)]  # the list holds a_1, ..., a_5, so a[i - 1] is a_i (zero-based list!)
correct = sum(a[i - 1] for i in range(1, 5 + 1))  # 1 + 3 + 5 + 7 + 9 = 25
stops_early = sum(a[i - 1] for i in range(1, 5))  # range(1, 5) misses i = 5: 16, not 25
try:
    sum(a[i] for i in range(1, 5 + 1))  # a[5] does not exist: the list has indices 0 .. 4
    index_error = False
except IndexError:
    index_error = True
slid_window = sum(Fraction(2 * i - 1) for i in range(0, 5))  # reads a_0 ... a_4 = -1 + 1 + 3 + 5 + 7 = 15, not 25

# A negative index does not fail: a[-1] is the LAST entry. a_0 "exists" in code even though the list starts at a_1.
silent_wrap = a[0 - 1] == a[-1]  # True

print(total, squares, empty, single, gauss_ok, squares_ok, odd_ok, geometric, geometric_ok, all_ones, correct, stops_early, index_error, slid_window, silent_wrap)

Then double sums: rows first and columns first, the triangle with the bounds rewritten, and the same triangle with the bounds kept by mistake.

from itertools import product

# A double sum is a loop inside a loop. Rows i = 1..n, columns j = 1..k, entries a[i][j] (here written with 1-based indices).
n, k = 3, 4


def entry(i, j):
    return i * j


# Rectangular: the inner bound does not depend on i. Every cell of the grid is visited exactly once.
rows_first = 0
for i in range(1, n + 1):
    for j in range(1, k + 1):
        rows_first += entry(i, j)

columns_first = 0
for j in range(1, k + 1):
    for i in range(1, n + 1):
        columns_first += entry(i, j)

same_total = rows_first == columns_first == 60  # (1+2+3)(1+2+3+4): the sum factors because entry(i, j) = i * j
cells = len(list(product(range(1, n + 1), range(1, k + 1))))  # n * k = 12 cells

# Triangular: the inner bound is the OUTER index, so the cells with j <= i form a triangle with n(n+1)/2 cells.
m = 4
by_rows = 0
for i in range(1, m + 1):
    for j in range(1, i + 1):
        by_rows += entry(i, j)

# Swapping the order must swap the bounds too: j runs 1..m and then i must run from j up to m (the cells with i >= j).
by_columns = 0
for j in range(1, m + 1):
    for i in range(j, m + 1):
        by_columns += entry(i, j)

triangle_cells = sum(1 for i in range(1, m + 1) for j in range(1, i + 1))  # 1 + 2 + 3 + 4 = 10
triangle_ok = by_rows == by_columns == 65 and triangle_cells == m * (m + 1) // 2

# The classic slip: keeping the bounds 1..i for j and 1..m for i after swapping the loops visits a DIFFERENT set of cells.
wrong = 0
for j in range(1, m + 1):
    for i in range(1, j + 1):  # now i <= j: the other triangle (the upper one)
        wrong += entry(i, j)
wrong_same_here = wrong == by_rows  # True ONLY because entry(i, j) = i * j is symmetric; not for a general table

table = [[2, -1, 0], [1, 4, -2], [0, 5, 1]]
lower = sum(table[i][j] for i in range(3) for j in range(i + 1))  # cells with j <= i: 2 + 1 + 4 + 0 + 5 + 1 = 13
upper_wrong = sum(table[i][j] for j in range(3) for i in range(j + 1))  # cells with i <= j instead: 2 + (-1) + 4 + 0 + (-2) + 1 = 4
wrong_differs = lower != upper_wrong

print(rows_first, columns_first, same_total, cells, by_rows, by_columns, triangle_ok, wrong_same_here, lower, upper_wrong, wrong_differs)

Finally the form sums take on data. NumPy is zero-based too; a dot product and a mean are sums; and the file shows that adding floating-point numbers is not exact, that the order of additions matters, and what a compensated sum does about it.

import math

import numpy as np

# Sigma notation as arrays. Index convention: NumPy is zero-based, the mathematics here starts at i = 1.
n = 10
i = np.arange(1, n + 1)  # the indices 1, 2, ..., n  (np.arange stops BEFORE its second argument, like range)
total_int = int(i.sum())  # 55 = n(n+1)/2, exact in integer arithmetic
squares = int((i**2).sum())  # 385

# The weighted sum, the dot product and the mean are all sums.
w = np.array([0.5, 0.25, 0.25])
x = np.array([4.0, 8.0, 12.0])
dot = float(w @ x)  # sum_i w_i x_i = 2 + 2 + 3 = 7
mean = float(x.sum() / x.size)  # (4 + 8 + 12) / 3 = 8

# Sums of doubles are NOT exact, and the order of addition matters: adding a tiny term to a huge accumulator can lose it completely.
big, tiny = 1e16, 1.0
lost = (big + tiny) - big  # 0.0: 1e16 + 1 rounds back to 1e16 (the spacing of doubles near 1e16 is 2)
kept = (big - big) + tiny  # 1.0: add the small term to a small accumulator instead

# Adding 0.1 ten times does not give 1.0 with a plain loop; math.fsum tracks the lost low-order bits and does.
acc = 0.0
for _ in range(10):
    acc += 0.1
naive_sum = acc  # 0.9999999999999999
careful_sum = math.fsum([0.1] * 10)  # 1.0
naive_is_one = naive_sum == 1.0  # False
careful_is_one = careful_sum == 1.0  # True

# For many terms the plain left-to-right loop drifts; NumPy's pairwise summation drifts much less. Compare both with the correctly rounded fsum.
values = np.full(10**5, 0.1)
exact = math.fsum(values.tolist())
pairwise_error = abs(float(values.sum()) - exact)
left_to_right = 0.0
for v in values.tolist():
    left_to_right += v
loop_error = abs(left_to_right - exact)
pairwise_wins = pairwise_error < loop_error  # True: same numbers, same exact answer, different order of additions

print(total_int, squares, dot, mean, lost, kept, naive_sum, careful_sum, naive_is_one, careful_is_one, pairwise_error, loop_error, pairwise_wins)

Explore: change the sum

These questions have definite answers; check each against the stages above.

• In the first stage, choose the whole numbers and set the bounds to $1$ and $20$. How many terms are there? What does the closed form $\frac{n(n+1)}{2}$ give, and does the loop agree?
• Choose the squares from $-3$ to $3$. The terms are symmetric around $0$; is the total zero? Now choose the whole numbers from $-3$ to $3$. Why is the total zero this time?
• Make the bounds equal. How many terms are there? Now set the upper bound one below the lower bound, and then three below. What do you read, and does the number of terms become negative?
• With the powers of a ratio, set the ratio to $2$ and then to $-1$, from $0$ to $4$. Compare each total with the closed form. Then set the ratio to $1$: why does the formula have to be replaced by a count?
• Type your own list into the first stage, for example five numbers of your choice, and read the sum from $1$ to $5$. Then read it from $1$ to $6$: the stage shows the loop that would raise an error. Why would the same slip with a negative index raise nothing?
• In the identities stage, set the shift to $0$. Why does forgetting to change the term do no harm there? Find the preset where it does no harm by coincidence, and then change the bounds slightly to break it.

Common mistakes

Numerical considerations

Sums of whole numbers and fractions are exact. Sums of floating-point numbers are not: each addition rounds to the nearest double, the rounding errors accumulate, and the result depends on the order of the additions.

Two other numerical habits follow from the rest of the chapter. A closed form such as $\frac{n(n+1)}{2}$ is exact in integer arithmetic but can overflow a fixed-width integer for large $n$; Python’s integers do not overflow, NumPy’s integer arrays do. And a geometric sum with $\lvert r\rvert<1$ and many terms is dominated by its first few terms: the later ones are so small that adding them to a large accumulator loses them, which is harmless there but is why the order of addition matters when the terms vary in size.

Finally, a sum of many terms with the terms of both signs can lose most of its significant digits to cancellation: two nearly equal numbers subtract to something small, and the rounding errors that were tiny compared with the numbers are no longer tiny compared with the result. Sorting by magnitude, or using a compensated sum, helps.

Connections to engineering and machine learning

• A loss is a mean over examples. The batch loss $L=\frac1N\sum_{i}\ell_i$ is a sum divided by the number of terms. If the indices run from $0$ to $N-1$ as in code, the count is $N$, not $N-1$; the mean of a batch of nothing is undefined (a division by zero), which is a different thing from the empty sum, which is $0$.
• A dot product is a sum of products. $\mathbf{w}\cdot\mathbf{x}=\sum_{i}w_ix_i$. A linear model, a neuron before its activation and the attention score are all sums of this kind. Rewriting them is sum algebra: linearity moves a constant weight out front, and splitting a sum splits a model across devices.
• Softmax has a sum in its denominator. The normalizing constant $\sum_j e^{z_j}$ is a sum over all classes. The numerical care of the previous section applies directly: summing very different magnitudes is exactly where order and compensation matter.
• Sums over axes. A matrix is a double sum waiting to happen. X.sum(axis=0) adds down the rows and X.sum(axis=1) along the columns; summing everything is the double sum, and the order cannot matter for a finite grid, apart from floating-point rounding.
• Triangular sums count pairs. The number of pairs $(i,j)$ with $j\le i$ is a triangular number, and an algorithm with a loop inside a loop whose inner bound is the outer index has a running time proportional to $n^2$ with the constant $\tfrac12$ that the closed form gives. Comparing every example with every other example in a batch is this pattern.
• Geometric sums are discounting and learning-rate schedules. A discounted return $\sum_t\gamma^{t}r_t$ and a moving average with decay both weight terms by powers of a ratio; the closed form with $\lvert r\rvert<1$ tells you how much total weight a long horizon can carry.

Exercises

Answer each question and press Check. A wrong answer tells you which mistake it looks like. After one attempt you may open a worked solution.

Summary and checkpoints

• A sum is a loop with an accumulator that starts at $0$: for each index from the lower bound to the upper bound, both included, add the term. The index is a dummy name.
• The number of terms is $n-m+1$. When $n<m$ the sum is empty and equals $0$. If a term is undefined, the whole sum is undefined; terms are never skipped.
• Closed forms: $\frac{n(n+1)}{2}$ for $1,\dots,n$, $\frac{n(n+1)(2n+1)}{6}$ for the squares, $n^2$ for the first $n$ odd numbers, $(n-m+1)c$ for a constant, and $\frac{r^m-r^{n+1}}{1-r}$ for a geometric sum when $r\ne1$ (and $n-m+1$ when $r=1$).
• Valid rewrites: pull a constant out, split a sum into two sums over the same bounds, split the range, shift the index and change the term to match. Pairing the first term with the last explains the formula for consecutive whole numbers.
• A double sum adds a grid of cells; on a rectangle the order does not matter; on a triangle the inner bound must be rewritten when the order is swapped.
• In Python, range(m, n + 1) visits $m,\dots,n$ and a list is zero-based, so a one-based $a_i$ is a[i - 1]; a negative index wraps silently.
• Floating-point sums round at each step and depend on the order of the additions; keep exact values, or use a compensated or pairwise sum.

Checkpoints. You can move on when you can, without the stage:

1. Write the sum of $a_i$ from $i=m$ to $i=n$ as a Python loop, and say how many times the body runs.
2. State what a sum with the upper bound below the lower bound equals, and what a sum with a term that does not exist equals.
3. Use a closed form for a sum of consecutive whole numbers, and say when the geometric formula cannot be used.
4. Shift the index of a sum by $k$ and change both the bounds and the term.
5. Swap the order of a double sum over a triangle and write the new bounds.