SEM 6 › Discrete Mathematics › Week 04
Discrete Mathematics · Week 04

Sequences & Summations

Sequence notation, geometric and arithmetic progressions, strings, finding formulas for sequences, Σ notation and its laws, the geometric series theorem, infinite series, double sums, and the standard closed forms.

ITE38222 videos · 61 min📄 Lesson 4.pdf

1Sequences

Sequences are ordered lists of elements. They're a discrete structure used to solve counting problems, and an important data structure in computer science.

  • 1, 3, 5, 7, 9 is a finite sequence with five terms.
  • 1, 3, 9, 27, 81, …, 3ⁿ, … is an infinite sequence.
Notation: {a₁, a₂, a₃, …}, {aₙ}, or {aₙ}n=1∞
Example 4.1.1

aₙ = n / (n + 1) gives the terms 1/2, 2/3, 3/4, …, n/(n+1), …

2Geometric & arithmetic progressions

Geometric progression

a, ar, ar², …, arⁿ, …

  • a = initial term
  • r = common ratio (multiply by r each time)

Examples: - {(−1)ⁿ}: a = 1, r = −1 → 1, −1, 1, −1, … - {6·(1/3)ⁿ}: a = 6, r = 1/3 → 6, 2, 2/3, …

Arithmetic progression

a, a + d, a + 2d, …, a + nd, …

  • a = initial term
  • d = common difference (add d each time)

Example: - {sₙ = −1 + 4n}: a = −1, d = 4 → −1, 3, 7, 11, …

Remark 4.1 — strings

A finite sequence a₁, a₂, …, aₙ is also called a string. The length of the string is its number of terms. Example: "abcd" is a string of length 4.

Finding a formula for a sequence (Example 4.1.2)

Terms Pattern Formula Type
1, 1/2, 1/4, 1/8, 1/16 Each term is half the previous one aₙ = (1/2)ⁿ, n = 0, 1, 2, … Geometric, a = 1, r = 1/2
1, 3, 5, 7, 9 Add 2 each time aₙ = 2n + 1, n = 0, 1, 2, … Arithmetic, a = 1, d = 2
1, −1, 1, −1, 1 Alternating aₙ = (−1)ⁿ, n = 0, 1, 2, … Geometric, a = 1, r = −1
How to spot the pattern
  • Check the differences between terms. Constant → arithmetic.
  • Check the ratios. Constant → geometric.
  • Otherwise compare with the useful sequences below (squares, cubes, 2ⁿ, n!), or try "previous term(s) + something".

Table 1 — useful sequences (first 10 terms)

nth term Terms
n² 1, 4, 9, 16, 25, 36, 49, 64, 81, 100, …
n³ 1, 8, 27, 64, 125, 216, 343, 512, 729, 1000, …
n⁴ 1, 16, 81, 256, 625, 1296, 2401, 4096, 6561, 10000, …
2ⁿ 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, …
3ⁿ 3, 9, 27, 81, 243, 729, 2187, 6561, 19683, 59049, …
n! 1, 2, 6, 24, 120, 720, 5040, 40320, 362880, 3628800, …
🧪 Try it — Sequence & series explorer

3Summation notation (Σ)

Σj=mn aj = am + am+1 + … + an
  • j is the index of summation. It runs through every integer from the lower limit m to the upper limit n.
  • Σ is the upper-case Greek letter sigma.
Remark 4.2 — the usual laws of arithmetic apply

Σj=1n (a·xj + b·yj) = a·Σj=1n xj + b·Σj=1n yj

So you can split sums and pull constants out.

Example 4.1.2 — first 100 terms of {1/n}

Lower limit 1, upper limit 100, so the sum is Σj=1100 1/j.

4Geometric series (Theorem 1)

If a and r are real and r ≠ 0:
Σj=0n a·rj = (a·rn+1 − a) / (r − 1) if r ≠ 1, and (n + 1)·a if r = 1

Proof sketch:

  1. Let S = Σj=0n a·rj.
  2. Multiply by r: rS = Σj=0n a·rj+1 = Σk=1n+1 a·rk.
  3. Remove the k = n+1 term and add the k = 0 term: rS = (Σk=0n a·rk) + (a·rn+1 − a) = S + (a·rn+1 − a).
  4. If r ≠ 1, solve for S: S = (a·rn+1 − a)/(r − 1).
  5. If r = 1, every term equals a, so S = (n + 1)a.
Example 4.2.1 — Σj=08 (3·2j + 2·3j)

Split using Remark 4.2: S₁ + S₂.

  • S₁ = Σ 3·2j with a = 3, r = 2: (3·2⁹ − 3)/(2 − 1) = 1536 − 3 = 1,533
  • S₂ = Σ 2·3j with a = 2, r = 3: (2·3⁹ − 2)/(3 − 1) = (39,366 − 2)/2 = 19,682

Total = 1,533 + 19,682 = 21,215

5Infinite series (Theorem 2)

If |x| < 1: Σn=0∞ xⁿ = 1 / (1 − x)

Proof: by Theorem 1 with a = 1, r = x, the partial sum is Σn=0k xⁿ = (xk+1 − 1)/(x − 1). Because |x| < 1, xk+1 → 0 as k → ∞. So the sum → (−1)/(x − 1) = 1/(1 − x). ∎

More generally, Σ a·rⁿ = a/(1 − r) when |r| < 1.

Example 4.2.2 — Σn=0∞ 2−2n·31+n

Rewrite each term: 2−2n·31+n = (1/4ⁿ)·3·3ⁿ = 3·(3/4)ⁿ.

This is geometric with a = 3 and r = 3/4 < 1, so S = 3/(1 − 3/4) = 3/(1/4) = 12.

6Double sums

Evaluate the inner sum first, then the outer sum.

Example 4.2.3 — Σi=02 Σj=03 i·j
  • Inner sum over j = 0, 1, 2, 3: i·0 + i·1 + i·2 + i·3 = 6i
  • Outer sum: Σi=02 6i = 0 + 6 + 12 = 18
🧪 Try it — Σ calculator (any expression in k)

7Useful closed forms (Table 2)

Sum Closed form
Σk=0n a·rk (r ≠ 0) (a·rn+1 − a)/(r − 1), r ≠ 1
Σk=1n k n(n + 1)/2
Σk=1n k² n(n + 1)(2n + 1)/6
Σk=1n k³ n²(n + 1)²/4
Σk=0∞ xk, |x| < 1 1/(1 − x)
Σk=1∞ k·xk−1, |x| < 1 1/(1 − x)²
Example 4.2.4 — Σk=100200 k

Use "sum up to 200 minus sum up to 99":

Σk=100200 k = Σk=1200 k − Σk=199 k = (200)(201)/2 − (99)(100)/2 = 20,100 − 4,950 = 15,150

Note on the PDF

The PDF writes (200)(201)/2 as "201,000" and gets 196,050. That's an arithmetic slip: 200 × 201 / 2 = 20,100, so the correct answer is 15,150. Check it with the Σ calculator's first button.

Exam focus

Expect:

  • Finding terms aₙ
  • Identifying arithmetic or geometric progressions and their a, d, r
  • Writing a formula for a list of terms
  • Writing sums in Σ notation
  • Evaluating sums using splitting + geometric formula, the closed forms, and the "sum to n minus sum to m − 1" trick
  • Infinite geometric series (rewrite as a·rⁿ first)

8Quick revision sheet

Concept Remember it as
Sequence Ordered list:
Geometric a, ar, ar², …: multiply by r
Arithmetic a, a+d, a+2d, …: add d
String Finite sequence; length = number of terms
Σ Index j from lower m to upper n; linear, so split and factor
Geometric sum (a·rn+1 − a)/(r − 1); if r = 1, (n+1)a
Infinite geometric a/(1 − r), |r| < 1
Σk, Σk², Σk³ n(n+1)/2, n(n+1)(2n+1)/6, n²(n+1)²/4
Partial range Σmn = Σ1n − Σ1m−1
Double sum Inner first

?Self-check quiz

11 questions on this week. Answer them all, then press Check my answers. Your best and latest scores are saved and shown on the subject page.

← PreviousFunctionsNext →Matrices