Learning objectives
By the end of this week you can:
- 1 Define sequences explicitly and by recurrence, including Fibonacci.
- 2 Evaluate arithmetic and geometric sums and use summation notation.
- 3 Decide whether two sets have the same cardinality using bijections.
- 4 Show that ℤ and ℚ are countable and that ℝ is not (Cantor's diagonal argument).
- 5 Connect uncountability to the existence of problems no program can solve.
★ the wow moment
There are more problems than programs.
Programs are finite strings, so there are countably many of them. Yes/no problems are subsets of ℕ, and there are uncountably many. Cantor's 1891 diagonal trick therefore proves that most problems cannot be solved by any computer, ever.
Topics
- Sequences, recurrence relations, Fibonacci
- Arithmetic and geometric progressions
- Summations and closed forms
- Cardinality, countable sets
- Cantor’s diagonal argument
- Uncountability and computability
Before class
- Skim Rosen 2.4–2.5 (20 minutes is enough; we go through it together).
- Bring paper and a pen: part of every lecture is solving by hand.
In industry
-
Algorithm analysis
Running times are sums: a nested loop costs 1 + 2 + … + n = n(n+1)/2 steps.
-
Finance and growth
Compound interest and population models are geometric sequences and recurrences.
-
Computability
The halting problem uses the same diagonal argument as Cantor.
Lab 9: Recurrences and Cantor's Diagonal
Compute recurrences three ways, check summation formulas, and run Cantor's diagonal argument on a list of binary strings.
due Fri, Dec 4 · 23:59 · 100 points · opens in week 11
Go deeper
- Mathematics for Computer Science (Lehman, Leighton, Meyer) · Chapter 8, infinite sets
- Stanford CS103 Mathematical Foundations of Computing · cardinality and unsolvable problems lectures
- Cantor's diagonal argument (Wikipedia)
Tags:sequencerecurrencesummationFibonaccicardinalitycountableCantorhalting problem