Summation Notation and Series
What you'll learn: How to write and compute sums compactly using sigma notation, a critical skill for analyzing algorithms and data structures.
What is Summation Notation?
Instead of writing 1 + 2 + 3 + 4 + 5, mathematicians and computer scientists use sigma notation (Σ, Greek letter sigma) to express sums concisely:
5
Σ i = 1 + 2 + 3 + 4 + 5 = 15
i=1
This reads as "the sum of i, where i goes from 1 to 5." The variable i is the index, 1 is the lower bound, and 5 is the upper bound.
Common Series Formulas
You've already learned about arithmetic and geometric sequences. Now we compute their total sums:
Arithmetic Series
For an arithmetic sequence (constant difference between terms):
n
Σ (a + d·k) = n·(first term + last term) / 2
k=0
Example: Sum of first n natural numbers: 1 + 2 + ... + n = n(n+1)/2
Geometric Series
For a geometric sequence (constant ratio between terms):
n
Σ a·r^k = a·(1 - r^(n+1)) / (1 - r) [when r ≠ 1]
k=0
Example: 1 + 2 + 4 + 8 + 16 = 2^5 - 1 = 31
Why This Matters in CS
When analyzing how long an algorithm takes, you'll often sum up operations: "This loop runs n times, doing i operations on iteration i." That's summation notation in action!
Key Takeaway: Summation notation (Σ) compactly expresses sums; arithmetic series sum linearly with average×count, while geometric series grow exponentially and have closed-form formulas—essential for algorithm analysis.