Skip to content
Tutorials Center
My learning

Topics

Lesson 27 of 68 ยท Sequences, Sums and Recurrences

Sequences and Summations

Work with arithmetic and geometric sequences, sigma notation, closed-form sums and telescoping series, then compute and plot partial sums in Python.

A sequence is an ordered list of numbers, one for each position 0, 1, 2, ... or 1, 2, 3, ... Daily savings, the running time of a loop on inputs of size 1, 2, 3, ..., and the numbers of nodes on each level of a binary tree are all sequences. Adding up the terms gives a summation, and a great deal of algorithm analysis is the art of replacing a long sum by a short formula.

In this lesson you will meet arithmetic and geometric sequences, read and write sigma notation, learn the closed forms every programmer should know, use telescoping to collapse sums, and check each formula by computing it. If sigma notation looks unfamiliar, Mathematical Notation and Python shows how it maps onto loops.

Sequences and their formulas

We write a sequence as aโ‚€, aโ‚, aโ‚‚, ... or as (aโ‚™). There are two ways to describe one. An explicit formula gives aโ‚™ directly from n, for example aโ‚™ = 3 + 4n. A recursive definition gives aโ‚™ in terms of earlier terms; that is the topic of Recurrence Relations.

Two families appear constantly.

  • An arithmetic sequence adds the same difference d each time: aโ‚™ = aโ‚€ + nยทd. Example: 3, 7, 11, 15, ... with aโ‚€ = 3 and d = 4.
  • A geometric sequence multiplies by the same ratio r each time: aโ‚™ = aโ‚€ ยท rโฟ. Example: 5, 10, 20, 40, ... with aโ‚€ = 5 and r = 2.

Two sequences to know

Arithmetic Add the same step every time.
Geometric Multiply by the same ratio.
Growth Linear for the first, exponential for the second.

Many loops cost an arithmetic series; doubling processes give geometric ones.

1 / 2

Sigma notation

The symbol ฮฃ (capital sigma) abbreviates a sum. The expression

ฮฃ_{k=m}^{n} f(k)

means f(m) + f(m+1) + ... + f(n). The letter k is the index (a dummy variable that exists only inside the sum), m is the lower limit and n the upper limit. It translates directly to Python: sum(f(k) for k in range(m, n + 1)). Note the n + 1, because range excludes its end. A sum with limits that cross (m > n) is empty and equals 0, just as sum([]) does.

Useful rules: constants factor out (ฮฃ cยทf(k) = cยทฮฃ f(k)), sums split (ฮฃ (f(k) + g(k)) = ฮฃ f(k) + ฮฃ g(k)), and you may shift the index as long as you shift the limits to match.

Closed forms for arithmetic and geometric sums

The sum of the first n terms of an arithmetic sequence has a famous story: the young Gauss added 1 to 100 by pairing the first and last terms, 1 + 100, 2 + 99, 3 + 98, and so on, giving 50 pairs of 101. The general rule is

aโ‚€ + (aโ‚€ + d) + ... + (aโ‚€ + (nโˆ’1)d) = n ยท (first + last) / 2

so ฮฃ_{k=1}^{n} k = n(n+1)/2.

For a geometric sum, multiply the sum S by r and subtract: S โˆ’ rS = aโ‚€ โˆ’ aโ‚€ยทrโฟ, hence

aโ‚€ + aโ‚€r + ... + aโ‚€r^(nโˆ’1) = aโ‚€ ยท (rโฟ โˆ’ 1) / (r โˆ’ 1) (r โ‰  1)

If |r| < 1 the infinite sum exists and equals aโ‚€ / (1 โˆ’ r). Two more closed forms are worth memorising: ฮฃ kยฒ = n(n+1)(2n+1)/6 and ฮฃ kยณ = (n(n+1)/2)ยฒ. The second says the sum of the first n cubes is the square of the sum of the first n integers.

Python Check the closed forms

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Both sides agree for every formula: the arithmetic total is 136, the geometric total is 1275, and the sums of squares and cubes to 100 are 338350 and 25502500. The partial sum of halves is 1023/1024, one short step from 1. Numerical agreement is not a proof, but it is an excellent way to catch a wrong formula before you try to prove it by induction in Mathematical Induction.

Telescoping sums

Some sums collapse because consecutive terms cancel. Consider

ฮฃ_{k=1}^{n} 1 / (k(k+1))

Split each term with partial fractions: 1/(k(k+1)) = 1/k โˆ’ 1/(k+1). Written out, the sum is (1 โˆ’ 1/2) + (1/2 โˆ’ 1/3) + (1/3 โˆ’ 1/4) + ... + (1/n โˆ’ 1/(n+1)). Each middle term cancels with its neighbour, like the sections of a collapsing telescope, leaving 1 โˆ’ 1/(n+1) = n/(n+1).

In general, if a term can be written as g(k) โˆ’ g(k+1), the sum from 1 to n telescopes to g(1) โˆ’ g(n+1). Spotting the right g is the skill.

Computing and plotting partial sums

A partial sum Sโ‚™ adds the first n terms. Plotting partial sums shows whether a series settles down (converges) or keeps growing. The sum ฮฃ 1/kยฒ, for example, creeps up to ฯ€ยฒ/6 โ‰ˆ 1.6449, while the harmonic series ฮฃ 1/k grows without bound, though extremely slowly.

Python Partial sums on a plot

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The exact fraction for the telescoping sum with n = 100 is 100/101, as derived. After 100 terms the harmonic sum has reached about 5.1874, the squares sum 1.6350, and the telescoping sum 0.9901. The first two bend toward a ceiling on the plot; the harmonic curve keeps climbing, because doubling the number of terms always adds roughly 0.69 more (to reach a sum of 10 you would need over 12,000 terms).

To avoid off-by-one slips, count the terms. A sum from k = m to n has n โˆ’ m + 1 terms, which is why range(m, n + 1) is the right translation.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. What is 3 + 7 + 11 + 15 + 19 + 23 + 27 + 31?

    There are 8 terms, first 3 and last 31, so the sum is 8 * (3 + 31) / 2 = 136.
  2. 2. Which Python expression equals the sum of k^2 for k from 1 to n?

    range excludes its end, so range(1, n + 1) is needed to include k = n.
  3. 3. What is the geometric sum 1 + 2 + 4 + ... + 2^9 (ten terms)?

    Using a0 * (r^n - 1) / (r - 1) with a0 = 1, r = 2 and n = 10 terms gives 1023.
  4. 4. Why does the sum of 1/(k(k+1)) from 1 to n equal n/(n+1)?

    1/(k(k+1)) = 1/k - 1/(k+1), so all the middle terms cancel and only 1 - 1/(n+1) remains.
  5. 5. Which statement about the harmonic series 1 + 1/2 + 1/3 + ... is correct?

    The partial sums keep increasing, roughly like the natural logarithm of n, so they have no finite limit.

Summary

  • A sequence has an explicit formula or a recursive definition; arithmetic sequences add a constant, geometric ones multiply by one.
  • ฮฃ_{k=m}^{n} f(k) corresponds to sum(f(k) for k in range(m, n + 1)) and has n โˆ’ m + 1 terms.
  • Key closed forms: n(n+1)/2, n(n+1)(2n+1)/6, (n(n+1)/2)ยฒ, and aโ‚€(rโฟ โˆ’ 1)/(r โˆ’ 1).
  • Telescoping sums collapse when each term is g(k) โˆ’ g(k+1).
  • Compute partial sums and compare them with a closed form before trusting (or proving) the formula.

Next: Recurrence Relations, where each term is defined from the ones before it.