Skip to section
Foundationsfor rotation-free search
Section 3 of 526% of course
Contents
Chapter 1 Section 1.3 55 min

Part I · Mathematical foundations

From repeated addition to sigma notation

Construct summation notation from a running-total loop.

Repeated addition is just an algorithm

Think about how you'd add up [4, −2, 7, 1] in code. You'd probably start with a total = 0. Then you'd visit one position at a time, replacing your total with total + current_value.

Running-total machinetotal = 0
4-271
total = 0total = total + a[0] // add 4total = total + a[1] // add -2total = total + a[2] // add 7total = total + a[3] // add 1

The final total here is 10. For a simple sum, the order you visit the numbers doesn't change the answer, but the index is still there, telling our loop which value to grab next.

Compress the loop only after you understand it

Math uses the Greek capital letter sigma, ∑, as a shorthand for this exact kind of repeated addition. Let's break it down piece by piece:

∑3 stop at index 3i=0 start i at 0ai add the value at i
∑i=03 ai = a0 + a1 + a2 + a3

Separate the loop controller from the accumulator

Notice that a repeated sum tracks two changing pieces of state, just like our code would. The index (our loop counter) tells us which term is up next. The accumulator stores the running total of the terms we've already seen. Mixing them up is like using your for loop counter as your database result: sure, they're both numbers, but they mean very different things.

Worked example

Name the invariant

Right before we process position i, let's say our total equals the sum of positions 0 through i−1. Adding ai to it ensures that same statement is true for the next iteration. Once i reaches D, our accumulator holds the sum of positions 0 through D−1—the entire list.

In software, we call this a loop invariant: a fact that we guarantee stays true as the loop advances. It's the logical bridge that proves “the code ran” means “the code computed the right answer.”

Worked example

Evaluate a finite sum

Let's take a = [4, −2, 7, 1]. The best way to handle a sigma is to expand it first:

∑i=13 ai = −2 + 7 + 1 = 6

Notice that the lower bound is 1, so we skipped a0 entirely.

Use D when the length might change

∑i=0D−1 ai

This is a perfectly reusable recipe. If D is 4, our upper bound is 3. If D grows to 128, the upper bound naturally becomes 127.

Check your understanding

How many terms are inside a sum from i=2 through i=6?

The index is just local bookkeeping

If we swap i out for k, absolutely nothing changes as long as we're consistent. It's exactly like renaming a local variable in a function:

∑i=0D−1 ai = ∑k=0D−1 ak

Check your understanding

Which expansion correctly matches a sum from i=0 through 2 of (i+1)?

Split a sum without changing it

A long sum can be sliced at any valid boundary. For instance, if 0 < m < D:

∑i=0D−1 ai = ∑i=0m−1 ai + ∑i=mD−1 ai

This is just the math way of saying: "sum up the first chunk, sum up the second chunk, and then add those two subtotals together." This trick becomes incredibly handy later when we start reasoning about chunking data for parallel hardware!

Retrieval check: expand the first three terms of our general sum

Assuming D is at least 3, the sum kicks off with a0 + a1 + a2, and marches all the way up through aD−1.

Section summary

  • A finite sum is literally just a running-total loop.
  • The bounds tell us exactly which indices get to participate.
  • ∑ is there to hide the repetition, not to make things artificially complex.
  • When in doubt, expand the unfamiliar notation back into plain addition.

Repository layer · second pass

What does sigma notation compress—and what does it not change?

Sigma notation is a loop header plus a loop body. The lower and upper marks specify the inclusive values taken by the index. The expression to the right is evaluated once for each index and the results are added. Nothing mysterious occurs between the expanded addition and the compact symbol.

The notation becomes safe when you adopt a mechanical reading routine: identify the index, list its legal values, substitute each value into the body, and only then add. This routine also exposes off-by-one mistakes immediately because the number of written terms must be upper − lower + 1.

Reasoning chain

  1. 1

    Circle the index variable.

  2. 2

    Expand its inclusive range.

  3. 3

    Substitute one index value at a time.

  4. 4

    Count the terms before evaluating them.

  5. 5

    Accumulate from a stated initial total of zero.

Worked trace

Expand before calculating

  1. Consider Σ from i=2 through 5 of (2i−1).
  2. The index values are 2, 3, 4, 5: four terms.
  3. Substitution gives 3 + 5 + 7 + 9.
  4. A running total gives 3, 8, 15, 24.

Result. The sum is 24, and the four-term count checks the bounds.

Executable lens · Python

Make the hidden state visible

total = 0
for i in range(2, 6):  # Python stops before 6
    total += 2 * i - 1
assert total == 24

Retype this example, predict each intermediate value, and then change one input that touches a boundary.

Misconception clinic

Tempting mistakes

  • Reading the upper bound as exclusive because Python range is exclusive.
  • Adding the index values instead of evaluating the body at each index.

Retrieval and transfer

Close the book first

  1. Expand Σᵢ₌₀³ (i²+1) without skipping a term.
  2. Write 5+8+11+14 using sigma notation.
  3. Explain why a sum with lower bound 4 and upper bound 3 is empty.