Mathematics.

sequences and recursion

Summation Notation

Discrete Mathematics20 minDifficulty2 out of 10

You should know: sequences and series

Overview

Summation notation (sigma notation) is a compact way to write the sum of a sequence of terms without writing out every addend. The capital Greek letter Σ (sigma) stands for 'sum,' and an expression like Σᵢ₌₁ⁿ aᵢ means 'add up the terms aᵢ as the index i runs from 1 to n.' The index variable is a placeholder — it takes each integer value in the given range exactly once, and the notation says nothing about how the sum is computed, only what is being added. Sigma notation is indispensable for writing series, statistical formulas (means, variances), polynomial expansions, and algorithm running-time analyses concisely, and it comes with a small set of algebraic rules (linearity, splitting, reindexing) that let sums be manipulated symbolically before any arithmetic is done.

Intuition

Think of Σ as a for-loop written in math: the bottom of the sigma sets the starting value of a counter, the top sets the stopping value, and the expression to the right is what gets accumulated on each pass. Just as a for-loop's accumulator doesn't care what the loop variable is named, Σᵢ₌₁ⁿ i² and Σⱼ₌₁ⁿ j² are exactly the same sum — the index is a dummy variable, invisible outside the sum. This loop picture also explains the algebra rules: splitting a range is just breaking one loop into two consecutive loops, and linearity is running two accumulators side by side versus one accumulator that does both additions per step.

Formal Definition

Definition

For a sequence of terms indexed by integers, the sum from index m to index n (m ≤ n) is written and defined as:

∑i=mnai=am+am+1+⋯+an\sum_{i=m}^{n} a_i = a_m + a_{m+1} + \cdots + a_n
Definition of sigma notation
∑i=mn(ai+bi)=∑i=mnai+∑i=mnbi\sum_{i=m}^{n} (a_i + b_i) = \sum_{i=m}^{n} a_i + \sum_{i=m}^{n} b_i
Linearity (additivity)
∑i=mnc ai=c∑i=mnai\sum_{i=m}^{n} c\,a_i = c \sum_{i=m}^{n} a_i
Linearity (scalar multiple)
∑i=mnai=∑i=mkai+∑i=k+1nai(m≤k<n)\sum_{i=m}^{n} a_i = \sum_{i=m}^{k} a_i + \sum_{i=k+1}^{n} a_i \quad (m \le k < n)
Splitting a range
∑i=1ni=n(n+1)2\sum_{i=1}^{n} i = \frac{n(n+1)}{2}
Sum of the first n positive integers (Gauss's formula)

Derivation

Gauss's trick for the sum of the first n positive integers: write the sum forwards and backwards, then add term by term.

S=1+2+⋯+(n−1)+nS = 1 + 2 + \cdots + (n-1) + n

Sum written forwards

S=n+(n−1)+⋯+2+1S = n + (n-1) + \cdots + 2 + 1

Same sum written backwards

2S=(n+1)+(n+1)+⋯+(n+1)⏟n terms=n(n+1)2S = \underbrace{(n+1) + (n+1) + \cdots + (n+1)}_{n \text{ terms}} = n(n+1)

Add the two equations term by term; each column sums to n+1

S=n(n+1)2S = \frac{n(n+1)}{2}

Divide by 2

Worked Examples

  1. Write out each term for i = 1 through 5.

    (2⋅1+1)+(2⋅2+1)+(2⋅3+1)+(2⋅4+1)+(2⋅5+1)(2\cdot1+1) + (2\cdot2+1) + (2\cdot3+1) + (2\cdot4+1) + (2\cdot5+1)

  2. Simplify each term.

    3+5+7+9+113 + 5 + 7 + 9 + 11

  3. Add them up.

    3+5+7+9+11=353+5+7+9+11 = 35

Answer: 35

Practice Problems

Difficulty 2/10

Evaluate Σᵢ₌₁⁴ i².

Difficulty 3/10

Use Gauss's formula to evaluate Σᵢ₌₁²⁰ i.

Difficulty 4/10

A class of students records daily step counts for a week as aᵢ for i = 1 to 7, and Σᵢ₌₁⁷ aᵢ = 63,000. If the average daily step count is defined as (1/7)Σᵢ₌₁⁷ aᵢ, what is the average?

Quiz

In Σᵢ₌₁ⁿ aᵢ, the letter i is:
Which identity expresses the linearity of summation?
Gauss's formula Σᵢ₌₁ⁿ i = n(n+1)/2 is derived by:

Summary

  • Σᵢ₌ₘⁿ aᵢ means 'add the terms aᵢ for each integer i from m to n'; i is a dummy variable.
  • Summation is linear: it distributes over addition and pulls out constant multiples.
  • A sum can be split at any interior point into two consecutive sums covering the same range.
  • Gauss's formula Σᵢ₌₁ⁿ i = n(n+1)/2 comes from pairing the sum with its reverse.

References

  1. WebsiteWikipedia — Summation