Week 19: TAOCP 1.2.3 Sums and Products

Sigma and Pi notation, and the rules for manipulating sums: distributive, change of variable, interchanging order of summation, and handling sums over relations instead of just ranges. Knuth also introduces the bracket notation for conditions (later called Iverson brackets).

Time About 8 hours this week

Why it matters

Analyzing loops means analyzing sums. Being able to swap the order of a double sum or reindex cleanly is the core skill behind every running-time derivation you will meet in Vol 3.

Before you start

1.2.1 Mathematical Induction
Arithmetic and geometric series

How to approach it

Do not read this like prose. For every manipulation rule, write a tiny concrete example with numbers (say n = 4) and check both sides agree. Pay special attention to interchanging the order of summation with dependent bounds; draw the grid of (i, j) pairs to see it.

Exercises

This section has a lot of exercises and many are short manipulations. Do as many of the 00 to 20 ones as you can; speed with sums is a muscle. Do every exercise rated 00 to 20 in your head or on paper; they are quick and they check you actually absorbed the definitions. Then pick two or three rated 20 to 25 (M or not) and grind them out fully. Attempt one M25 to M30 and give yourself a hard 90-minute cap before reading the answer. Always read the answer to every exercise you attempted, even the ones you got, because Knuth's answers often teach a second technique.

Traps

Changing a variable but forgetting to change the bounds.
Swapping a double sum with dependent limits incorrectly. Draw the region.
If you find this section rough, Concrete Mathematics (Graham, Knuth, Patashnik) chapter 2 covers the same ground more gently.