Skip to main content

Midterm 2 note sheet

Induction, loop invariants, recursion, recurrences and growth

Published

Last modified: 2026-11-19 12:07:39 (PST)

This sheet comes printed with Midterm 2. You may not bring your own notes, so study with this sheet. It leaves out some results; the full definitions are in the notes. Download the PDF to print it.

Integers

Table 1: Integers.
Integers, rationals, reals \(\mathbb{Z}\), \(\mathbb{Q}\), \(\mathbb{R}\)
Even \((n \text{ even}) \Leftrightarrow (\exists k \in \mathbb{Z}, n = 2 k)\)
Odd \((n \text{ odd}) \Leftrightarrow (\exists k \in \mathbb{Z}, n = 2 k + 1)\)
Parity \(\forall n \in \mathbb{Z}, (((n \text{ even}) \lor (n \text{ odd})) \land (\neg ((n \text{ even}) \land (n \text{ odd}))))\)
Closure \((a, b \in \mathbb{Z}) \Rightarrow ((a + b \in \mathbb{Z}) \land (a - b \in \mathbb{Z}) \land (a b \in \mathbb{Z}))\)
Divides (\(a, b \in \mathbb{Z}\)) \((a \mid b) \Leftrightarrow (\exists k \in \mathbb{Z}, b = a k)\)
Congruence (\(a, b, n \in \mathbb{Z}\), \(n > 0\)) \((a \equiv b \pmod{n}) \Leftrightarrow (n \mid (a - b))\)
Remainder \(r\) of \(a\) by \(n\) (\(a, n \in \mathbb{Z}\), \(n > 0\)) the unique \(r\) with \(\exists q \in \mathbb{Z}, ((a = q n + r) \land (0 \le r < n))\)
Rational \((x \in \mathbb{Q}) \Leftrightarrow (\exists a, b \in \mathbb{Z}, ((b \ne 0) \land (x = a / b)))\)

Induction

Table 2: Induction.
Sum \(\sum_{i=1}^{n} a_i = a_1 + a_2 + \cdots + a_n\)
Induction (\(b, k, n \in \mathbb{Z}\)) \((P(b) \land (\forall k \ge b, (P(k) \Rightarrow P(k + 1)))) \Rightarrow (\forall n \ge b, P(n))\)
Base case \(P(b)\)
Inductive step assume \(P(k)\) (the induction hypothesis), show \(P(k + 1)\)

Strong induction

Table 3: Strong induction.
Strong induction (\(b, c, k, n \in \mathbb{Z}\)) \((P(b) \land \cdots \land P(c) \land (\forall k \ge c, ((P(b) \land \cdots \land P(k)) \Rightarrow P(k + 1)))) \Rightarrow (\forall n \ge b, P(n))\)

Loop invariants

Table 4: Loop invariants.
Loop invariant \(I\), guard \(G\) \(I\) is true each time \(G\) is tested
Initialization \(I\) holds when \(G\) is first tested
Maintenance \((I \land G)\) before a pass through the body \(\Rightarrow\) \(I\) after it
Termination the loop stops, and \((I \land (\neg G)) \Rightarrow\) the result

Racket

Table 5: Racket.
Define a function (define (f x y) body)
Conditionals (if test then-expr else-expr)
(cond [test1 expr1] [test2 expr2] [else expr3])
Lists '() empty, (list 1 2 3) gives '(1 2 3)
(cons x lst) puts x in front, (empty? lst) is #t if lst is '()
(first lst), (second lst), (third lst), (rest lst) all but the first
Arithmetic (+ a b) (- a b) (* a b) (quotient n d) (remainder n d)
Comparison (= a b) (< a b) (<= a b) (> a b) (>= a b)
(equal? a b) is #t if a and b are the same value, lists included
Logic (and a b) (or a b) (not a)

Recurrences

Table 6: Recurrences.
Recurrence relation each term from earlier terms, starting from initial terms
Iteration substitute repeatedly, write the result after \(j\) steps, choose \(j\) to reach an initial term
Geometric sum (\(r \ne 1\)) \(1 + r + \cdots + r^k = \dfrac{r^{k + 1} - 1}{r - 1}\)
Arithmetic sum \(1 + 2 + \cdots + n = \dfrac{n (n + 1)}{2}\)
Logarithms \(2^{\log_2 n} = n\)
\(\log_2 (x y) = \log_2 x + \log_2 y\)
\(\log_2 (x^k) = k \log_2 x\)

Growth of functions

Table 7: Growth of functions.
Big-O (\(c \in \mathbb{R}\); \(N, n \in \mathbb{Z}\)) \((f(n) = O(g(n))) \Leftrightarrow (\exists c > 0, \exists N, \forall n \ge N, \mathopen{}\left|f(n)\right|\mathclose{} \le c \mathopen{}\left|g(n)\right|\mathclose{})\)
Big-Omega \((f(n) = \Omega(g(n))) \Leftrightarrow (\exists c > 0, \exists N, \forall n \ge N, \mathopen{}\left|f(n)\right|\mathclose{} \ge c \mathopen{}\left|g(n)\right|\mathclose{})\)
Big-Theta \((f(n) = \Theta(g(n))) \Leftrightarrow ((f(n) = O(g(n))) \land (f(n) = \Omega(g(n))))\)
Witnesses the numbers \(c\) and \(N\)
Back to top