Sequences, summations, cardinality and an introduction to algorithms

This week combines three separate topics: sequences and sums, the size of sets (cardinality), and an introduction to algorithms. A summation computation is a sure source of marks on the midterm: there is no calculator, so the numbers are small enough to compute by hand and knowing the formulas is enough. From cardinality there is usually a short part like “is this set countable, give a bijection”. The algorithms part is the groundwork for next week’s Big-O topic: you will learn to read and trace pseudocode.

Golden rules:

1. Split the sum: $\sum (ak + b) = a\sum k + \sum b$.
2. If the lower bound is not 1: sum from 1 to the upper bound, and subtract the sum from 1 to (lower bound − 1).
3. In a geometric sum, count the terms. If $j = 0..n$ there are $n + 1$ terms.
4. Countable = I can list the elements as 1st, 2nd, 3rd, one by one.
5. When tracing an algorithm, write every variable in a table. Don’t do it in your head.

Sequences

Sequence: a function from the integers (usually $\{0, 1, 2, \dots\}$ or $\{1, 2, 3, \dots\}$) to a set. Its $n$th term is $a_n$.

Solving a recurrence relation means finding a closed formula that writes $a_n$ only in terms of $n$. The simple method is iteration: write a few terms, see the pattern, verify with induction. For $a_n = a_{n-1} + 3$, $a_0 = 5$, we get $a_n = 5 + 3n$.

Order for finding a formula from terms: are the differences constant (arithmetic)? Are the ratios constant (geometric)? Compare with squares, cubes, $2^n$, $n!$. Is each term twice the previous one plus one?

Summations

$\sum_{k=m}^{n} a_k = a_m + a_{m+1} + \dots + a_n$

$k$ is the index of summation, $m$ the lower bound, $n$ the upper bound. The name of the index does not matter: $\sum_{k=1}^5 k^2 = \sum_{j=1}^5 j^2$.

Formulas to memorize

See once why the geometric formula is correct: $S = a + ar + \dots + ar^n$. $rS = ar + \dots + ar^{n+1}$. Subtract: $rS - S = ar^{n+1} - a$, that is $S = \tfrac{a(r^{n+1} - 1)}{r - 1}$. All the middle terms cancelled each other.

Shifting the index

Write $\sum_{k=4}^{8} k^2$ with $j = k - 3$: $k = 4 \Rightarrow j = 1$, $k = 8 \Rightarrow j = 5$, the term is $(j + 3)^2$.

$\sum_{k=4}^{8} k^2 = \sum_{j=1}^{5} (j+3)^2 = 16 + 25 + 36 + 49 + 64 = 190.$

A faster way: $\sum_{1}^{8} k^2 - \sum_{1}^{3} k^2 = 204 - 14 = 190$.

Double sums and products

In a double sum, compute the inner sum first (treat the outer index as a constant), then the outer sum. This is the same as two nested for loops:

total := 0
for i := 1 to 3
    for j := 1 to 4
        total := total + (2i − j)

Product notation: $\prod_{i=1}^{4} 2i = 2 \cdot 4 \cdot 6 \cdot 8 = 384$. $n! = \prod_{i=1}^{n} i$.

PITFALL · The number of terms in $\sum_{k=m}^{n}$. From $k = 10$ to $30$ there are $30 - 10 + 1 = 21$ terms, not 20. This difference costs marks in the sum of a constant term: $\sum_{k=10}^{30} 2 = 42$.

Cardinality

For finite sets, size is the number of elements. To compare infinite sets you cannot count; instead you match them up. $\lvert A \rvert = \lvert B \rvert$ if and only if there is a bijection from $A$ to $B$.

• Countable: finite, or of the same cardinality as $\mathbb{Z}^+$ (countably infinite). You can list its elements as $a_1, a_2, a_3, \dots$ without skipping any.
• Uncountable: not countable.

Stadium intuition: a stadium has infinitely many seats numbered $1, 2, 3, \dots$. If you can give every element of the set a seat (nobody left standing, no two people in the same seat), the set is countable.

Countable sets

• Positive even numbers: $f(n) = 2n$. An infinite set can have the same size as its own proper subset; this is impossible for finite sets.
• $\mathbb{Z}$: list in the order $0, 1, -1, 2, -2, 3, -3, \dots$ (the function in question 8).
• Positive rationals $\mathbb{Q}^+$: group the $p/q$ by the sum $p + q$. Each group is finite. Write the fractions that do not reduce in order, skipping repeats:

p+q = 2:  1/1
p+q = 3:  1/2, 2/1
p+q = 4:  1/3, 3/1           (2/2 = 1/1 skipped)
p+q = 5:  1/4, 2/3, 3/2, 4/1
p+q = 6:  1/5, ...
List: 1/1, 1/2, 2/1, 1/3, 3/1, 1/4, 2/3, 3/2, 4/1, 1/5, ...

The union of two countable sets, and the union of finitely or countably many countable sets, is countable.

$\mathbb{R}$ is uncountable: Cantor’s diagonal argument

Theorem: the interval $(0, 1)$ is uncountable (so $\mathbb{R}$ is too).

Idea of the proof (by contradiction): assume there is a list of all the numbers in $(0, 1)$. Look at the $i$th decimal digit of the $i$th number in the list. Build a new number: its $i$th digit is 5 if the $i$th digit of the $i$th number is not 5, and 4 if it is 5. This number differs from every number in the list in at least one digit, so it is not in the list. Contradiction.

r1 = 0.[3]1415          diagonal digits: 3, 7, 1, 2, 4
r2 = 0.2[7]182          none is 5 → make them all 5
r3 = 0.14[1]42          new number: 0.55555...
r4 = 0.577[2]1          differs from r_i in the i-th digit
r5 = 0.6931[4]

(In the real proof the list is infinite and each number has infinitely many digits; choosing 5 and 4 avoids the double-representation problem such as 0.4999… = 0.5.)

Consequences: the irrational numbers are uncountable, and $\mathcal{P}(\mathbb{Z}^+)$ is uncountable. A set with an uncountable subset is also uncountable.

Introduction to algorithms

Algorithm: a finite, precise sequence of steps for solving a problem. Its properties: input, output, definiteness (every step is clear), correctness (right result), finiteness (ends in a finite number of steps), effectiveness (every step is doable), generality (applies to a whole class of problems).

Finding the maximum

procedure max(a1, a2, ..., an: integers)
max := a1
for i := 2 to n
    if max < ai then max := ai
return max

Trace: for 4, 9, 2, 11, 7, max takes the values 4, 9, 9, 11, 11. Each element is compared once: $n - 1$ comparisons.

Linear search and binary search

Linear search: look one by one from start to end. The list may be unsorted. In the worst case, comparison with $n$ elements.

Binary search: the list must be sorted. At each step it halves the interval:

procedure binary search(x: integer, a1 < a2 < ... < an)
i := 1; j := n
while i < j
    m := ⌊(i + j)/2⌋
    if x > am then i := m + 1
    else j := m
if x = ai then location := i else location := 0
return location

Trace: $x = 72$ in the list 2, 5, 8, 12, 16, 23, 38, 56, 72, 91:

Because the interval halves in each round, about $\log_2 n$ rounds are enough. Even with 1,000,000 elements, about 20.

Sorting: bubble sort and insertion sort

Bubble sort: compare neighbouring elements and swap them if they are out of order. At the end of each pass the largest remaining element settles at the end.

3, 2, 4, 1, 5
pass 1:  2, 3, 1, 4, 5      (5 is already in place, 4 settled into place)
pass 2:  2, 1, 3, 4, 5
pass 3:  1, 2, 3, 4, 5

The number of comparisons is always $(n-1) + (n-2) + \dots + 1 = \tfrac{n(n-1)}{2}$.

Insertion sort: keep the left part sorted and insert the next element in the right place. Like arranging the cards in your hand in a card game.

Greedy algorithm

At each step make the choice that looks best at that moment. Making change: give the largest coin that fits. With coins of 25, 10, 5, 1 cents the greedy algorithm always gives the fewest coins (this can be proved). But it can fail when the coin set changes: with 25, 10, 1 and 30 cents, greedy gives 6 coins, although 3 dimes are enough. The answer to “is the greedy algorithm optimal?” is either a proof or a counterexample.

Common mistakes