Sequences, sums, and relations to functions
Sequences are functions on the natural numbers. Recognising their patterns and summing them efficiently is a core skill in analysing algorithms.
Sequences as functions
A sequence is a function from the natural numbers to a set, written \(a_0, a_1, a_2, \ldots\). An arithmetic sequence adds a constant difference: \(a_n = a_0 + nd\). A geometric sequence multiplies by a constant ratio: \(a_n = a_0 r^n\). Recognising which type you have unlocks formulas.
Summation notation
\(\sum_{i=1}^{n} a_i\) means \(a_1 + a_2 + \cdots + a_n\). Sums split over addition and pull out constants: \(\sum (3a_i + b_i) = 3\sum a_i + \sum b_i\). Changing the index variable does not change the value; it is just a placeholder.
Key sum formulas
\(\sum_{i=1}^n i = \frac{n(n+1)}{2}\), \(\sum_{i=1}^n i^2 = \frac{n(n+1)(2n+1)}{6}\), and the geometric sum \(\sum_{i=0}^{n} r^i = \frac{r^{n+1} - 1}{r - 1}\) for \(r \ne 1\). The first formula is said to have been found by the young Gauss, pairing 1 with 100, 2 with 99, and so on.
\sum_{i=1}^n i = \frac{n(n+1)}{2}Worked example: an algorithm's cost
A nested loop runs the inner loop \(i\) times for \(i = 1\) to \(n\). Total steps: \(\sum_{i=1}^n i = \frac{n(n+1)}{2}\), roughly \(\frac{n^2}{2}\). Doubling \(n\) roughly quadruples the work. Sums like this are how computer scientists predict running times.
Recurrence relations
A recurrence defines a sequence by earlier terms: Fibonacci numbers satisfy \(F_n = F_{n-1} + F_{n-2}\) with \(F_0 = 0\), \(F_1 = 1\). Compound interest follows \(A_n = 1.05A_{n-1}\). Solving a recurrence means finding a closed formula, such as \(A_n = 1.05^n A_0\).
Growth of functions
To compare algorithms, we use big-O notation: \(f(n) = O(g(n))\) means \(f\) grows no faster than a constant multiple of \(g\) for large \(n\). Common classes, from fastest to slowest: \(O(1)\), \(O(\log n)\), \(O(n)\), \(O(n\log n)\), \(O(n^2)\), \(O(2^n)\). Constant factors are ignored; growth rate is what matters for large inputs.
Cardinality of finite unions and products
Counting connects to functions: the number of functions from a set of size \(m\) to a set of size \(n\) is \(n^m\), since each of the \(m\) inputs chooses one of \(n\) outputs. The number of injections is \(n(n-1)\cdots(n-m+1)\) when \(m \le n\).
Common mistakes
Off-by-one errors in summation limits. Applying the geometric formula when the ratio is 1. Confusing \(O(n^2)\) with exactly \(n^2\) steps. Forgetting initial conditions when solving recurrences.
Key takeaways
Sequences are functions on the naturals; arithmetic and geometric sequences have closed forms. Know the sums of integers, squares, and geometric terms. Recurrences define terms from earlier ones. Big-O describes growth rates and is the language of algorithm analysis.
Flashcard
a_n = a_0 + nd
Check your understanding
What is 1 + 2 + 3 + ... + 100?