Course contentsShow
← Computer Science
Lesson 85 of 2,8722. Discrete Mathematics for CSFree lesson

Summation Notation and Series

Understanding sigma notation for sums and computing common series like arithmetic and geometric sums.

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.