Key Points

All 38 must-memorize boxes from every section, in one place. Read this the night before and the morning of the exam.

5.2 Strong Induction & Well-Ordering

What changes vs. ordinary induction

	Ordinary induction	Strong induction
Inductive hypothesis	$P (k)$	$P (b) \land P (b + 1) \land \dots \land P (k)$
Base cases	usually one	often several
Use when	$P (k + 1)$ comes from $P (k)$	$P (k + 1)$ comes from $P (k - 1)$ , $P (k - 2)$ , a factor of $k + 1$ , …

Both are valid proof techniques and both are equivalent to the well-ordering property. Strong induction is never wrong to use, just sometimes unnecessary.

How many base cases do you need?

If your inductive step reaches back to $P (k + 1 - s)$ , you need $s$ consecutive base cases, and the inductive step starts once $k$ is at least the last base case.

Example: with 3-cent and 5-cent stamps you build $k + 1$ from $k - 2$ (add a 3-cent stamp), so $s = 3$ . You need 3 base cases, $P (8), P (9), P (10)$ , and the step is for $k \geq 10$ .

Which sets are well-ordered?

Yes: $N$ , $Z^{+}$ , ${n \in Z : n \geq - 5}$ (anything of the form "integers $\geq$ some fixed number").
No: $Z$ (no least element), $Q^{+}$ and $(0, 1)$ (keep halving), $R_{\geq 0}$ has least element 0 but its subset $(0, 1)$ has none.

Mathematical induction, strong induction, and well-ordering are equivalent: each one can be used to prove the others.

5.3 Recursive Definitions & Structural Induction

Explicit formula → recursive definition

Ask: how do I get $a_{n + 1}$ from $a_{n}$ ?

Explicit	Recursive step	Basis
$a_{n} = c + d n$ (arithmetic)	$a_{n + 1} = a_{n} + d$	$a_{0} = c$
$a_{n} = c \cdot r^{n}$ (geometric)	$a_{n + 1} = r \cdot a_{n}$	$a_{0} = c$
$S_{n} = \sum_{i = 0}^{n} b_{i}$	$S_{n + 1} = S_{n} + b_{n + 1}$	$S_{0} = b_{0}$
$n!$	$(n + 1)! = (n + 1) \cdot n!$	$0! = 1$
$P_{m} (n) = mn$	$P_{m} (n + 1) = P_{m} (n) + m$	$P_{m} (0) = 0$

Always state the basis. A recursive rule without a starting value defines nothing.

Writing a recursive definition for a set of integers

Find the period of the pattern. The basis lists one "block" of elements; the recursive step adds the period.

Set	Basis	Recursive step
Positive multiples of 5	$5 \in S$	$x \in S \Rightarrow x + 5 \in S$
Odd positive integers	$1 \in S$	$x \in S \Rightarrow x + 2 \in S$
${n \in Z^{+} : n \equiv 3 (mod 4)}$	$3 \in S$	$x \in S \Rightarrow x + 4 \in S$
Positive integers not divisible by 7	$1, 2, 3, 4, 5, 6 \in S$	$x \in S \Rightarrow x + 7 \in S$
All even integers (incl. negatives)	$0 \in S$	$x \in S \Rightarrow x + 2, x - 2 \in S$
Positive powers of 3	$3 \in S$	$x \in S \Rightarrow 3 x \in S$
$Z^{+}$	$1 \in S$	$x, y \in S \Rightarrow x + y \in S$

If the set includes negative numbers, you need a rule that goes down too.

Recursive functions on strings (the pattern: say what

λ

gives, then what adding one symbol does)

Function	Basis	Recursive step ( $w \in Σ^{*}$ , $a \in Σ$ )
length $l (w)$	$l (λ) = 0$	$l (w a) = l (w) + 1$
number of 1s, bit strings	$ones (λ) = 0$	$ones (w b) = ones (w) + b$ , for $b \in {0, 1}$
number of 0s, bit strings	$z (λ) = 0$	$z (w b) = z (w) + (1 - b)$
reversal $w^{R}$	$λ^{R} = λ$	$(w a)^{R} = a w^{R}$
power $w^{i}$	$w^{0} = λ$	$w^{i + 1} = w w^{i}$

Recursive sets of strings

Set	Basis	Recursive step
Palindromes (bit strings)	$λ, 0, 1 \in P$	$w \in P \Rightarrow 0 w 0, 1 w 1 \in P$
${0^{n} 1^{n} : n \geq 0}$	$λ \in A$	$x \in A \Rightarrow 0 x 1 \in A$

Tree functions to memorize

	Basis (single root)	Recursive ( $T = T_{1} \cdot T_{2}$ )
height $h (T)$	$0$	$1 + max (h (T_{1}), h (T_{2}))$
vertices $n (T)$	$1$	$1 + n (T_{1}) + n (T_{2})$
leaves $l (T)$	$1$	$l (T_{1}) + l (T_{2})$
internal vertices $i (T)$	$0$	$1 + i (T_{1}) + i (T_{2})$

Facts (all proved by structural induction): $n (T) \leq 2^{h (T) + 1} - 1$ , $n (T) \geq 2 h (T) + 1$ , $l (T) = i (T) + 1$ .

Structural induction templates

Integers / sets: Basis: check the listed elements. Step: "Assume $x$ (and $y$ ) have the property; show $x + y$ (or $3 x$ , $x^{2}$ , …) does too."

Strings: Basis: prove $P (λ)$ . Step: assume $P (w)$ , prove $P (w a)$ for every $a \in Σ$ .

Full binary trees: Basis: prove it for the single-vertex tree. Step: assume it for $T_{1}$ and $T_{2}$ , prove it for $T_{1} \cdot T_{2}$ using the recursive formulas for $h$ , $n$ , $l$ , $i$ .

Definition. Memorize the four cases exactly.

A (m, n) = ⎩ ⎨ ⎧ 2 n 02 A (m - 1, A (m, n - 1)) if m = 0 if m \geq 1, n = 0 if m \geq 1, n = 1 if m \geq 1, n \geq 2

Useful facts: $A (1, n) = 2^{n}$ for $n \geq 1$ , $A (m, 2) = 4$ for $m \geq 1$ , and $A (2, n) = 2^{2^{\cdot^{\cdot^{2}}}}$ (a tower of $n$ twos).

6.1 The Basics of Counting

Counting functions, subsets, and products

Let $∣ A ∣ = n$ and $∣ B ∣ = m$ .

All functions $f : A \to B$ : each of the $n$ inputs picks one of $m$ outputs, so $m^{n} = ∣ B ∣^{∣ A ∣}$ .
One-to-one functions: $m (m - 1) (m - 2) \dots (m - n + 1)$ if $n \leq m$ , and $0$ if $n > m$ .
Subsets of an $n$ -set: $∣ P (A) ∣ = 2^{n}$ . Each element is in or out, like a bit string.
Cartesian product: $∣ A_{1} \times \dots \times A_{k} ∣ = ∣ A_{1} ∣ \dots ∣ A_{k} ∣$ .
Relations from $A$ to $B$ (subsets of $A \times B$ ): $2^{nm}$ .

"At least one" means count the complement

$# (at least one X) = # (all) - # (none X) .$
Counting "at least one" directly usually double counts. The complement is almost always easier.

Use it whenever a problem says "or"

"Start with 0 or end with 11": count each, then subtract the strings that do both.

Length-8 bit strings that start with 0 or end with 11:
$2^{7} + 2^{6} - 2^{5} = 128 + 64 - 32 = 160.$

Counting multiples

Multiples of $d$ in ${1, \dots, N}$ : $⌊ N / d ⌋$ .
Multiples of $d$ in ${a, \dots, b}$ : $⌊ b / d ⌋ - ⌊(a - 1) / d ⌋$ .
"Divisible by both $d$ and $e$ " means divisible by $lcm (d, e)$ . For 4 and 6 that is 12, not 24.

Circular seating

$n$ people around a round table, rotations considered the same: $\frac{n !}{n} = (n - 1)!$ .
If reflections also count as the same ("same two neighbors, ignoring left/right"): $\frac{( n - 1 )!}{2}$ .

Class Problem 16: 5 people, same right and left neighbor means same seating, so $5! /5 = 4! = 24$ .

How to attack any counting problem

Decide what one outcome looks like (a string? a set? an arrangement?).
Sequence of choices? Multiply (product rule). Make sure each step's count doesn't depend on which earlier choice was made.
Separate cases? Add (sum rule). Make sure cases don't overlap.
"At least one"? Total minus none.
"Or" with overlap? Inclusion–exclusion.
Each outcome counted $d$ times? Divide.
Sanity check with a tiny case you can list by hand.

6.2 The Pigeonhole Principle

The two formulas you'll actually use

Guaranteed amount: $N$ objects in $k$ boxes means some box has $\geq ⌈ N / k ⌉$ .
Minimum number needed: to guarantee some box has at least $r$ objects, you need
$N = k (r - 1) + 1.$
Reason: $k (r - 1)$ objects can be spread with exactly $r - 1$ in every box. One more forces a box to reach $r$ .

Worst-case reasoning

When you need $r$ objects of a specific kind, pigeonhole isn't the right tool. Imagine the worst luck: you draw every other kind first, then $r$ of the kind you want.

Classic hole choices

Problem type	Holes
Two integers with the same remainder mod $d$	the $d$ remainders $0, 1, \dots, d - 1$
Pairs adding to a target (e.g. sum 9 from ${1..8}$ )	the pairs ${1, 8}, {2, 7}, {3, 6}, {4, 5}$
Integer midpoint of lattice points	parity patterns: (even, odd), … ( $2^{dim}$ of them)
Degrees in a network of $n$ computers	possible degrees, of which only $n - 1$ can occur
One integer divides another (from class)	odd parts: write $a = 2^{k} m$ with $m$ odd

6.3 Permutations & Combinations

Where the formula comes from (from class)

Build an $r$ -permutation in two steps: choose the $r$ objects ( $(r n)$ ways), then arrange them ( $r!$ ways). So
$P (n, r) = (r n) \cdot r! ⟹ (r n) = \frac{P ( n , r )}{r !} .$
Symmetry: $(r n) = (n - r n)$ . Choosing who's in is the same as choosing who's out. That's why 5-card hands and 47-card hands from 52 cards are equal in number.

Order matters?

	Order matters	Order doesn't matter
Words that signal it	arrange, line up, ranking, 1st/2nd/3rd, officers with titles, strings	committee, subset, hand of cards, team, group, choose
Count	$P (n, r)$	$C (n, r)$

Bit strings with

k

ones

A length- $n$ bit string with exactly $k$ ones is determined by which positions hold the 1s: $(k n)$ .

"At most $k$ ": $\sum_{i = 0}^{k} (i n)$
"At least $k$ ": $2^{n} - \sum_{i = 0}^{k - 1} (i n)$ , using the complement when that is shorter.

Same for coin flips (heads = 1).

Substrings: glue blocks together

Required substring(s): glue each into a block and permute the blocks plus the leftover letters.
Two required substrings that overlap (share letters, like ABC and CDE): merge them into one block (ABCDE).
Two required substrings that conflict (like CBA and BED, where B would need two different followers): the answer is $0$ .

"No two X adjacent": the gap method

Arrange the others first, then choose gaps for the X's. With $m$ others there are $m + 1$ gaps (including both ends), and you place the X's into distinct gaps.

8 men and 5 women, no two women adjacent: $8! \cdot P (9, 5)$ .

Committees with constraints

Exactly $a$ from group 1 and $b$ from group 2: $(a n _{1}) (b n _{2})$ (product rule).
At least one woman: $(r all) - (r men)$ .
At least one woman and at least one man: $(r all) - (r men) - (r women)$ .

Binomial values worth memorizing

$(0 n) = 1$ , $(1 n) = n$ , $(2 n) = \frac{n ( n - 1 )}{2}$
Row 5: 1, 5, 10, 10, 5, 1
Row 6: 1, 6, 15, 20, 15, 6, 1
Row 8: 1, 8, 28, 56, 70, 56, 28, 8, 1
Row 10: 1, 10, 45, 120, 210, 252, 210, 120, 45, 10, 1
$\sum_{k} (k n) = 2^{n}$ (e.g. $2^{10} = 1024$ )

To compute $(r n)$ by hand, write $\frac{n ( n - 1 ) \dots ( n - r + 1 )}{r !}$ and cancel before multiplying. Example: $(4 12) = \frac{12 \cdot 11 \cdot 10 \cdot 9}{4 \cdot 3 \cdot 2 \cdot 1} = 11 \cdot 5 \cdot 9 = 495$ .

6.4 Binomial Coefficients & Identities

Finding one coefficient: the recipe

For $(a x^{p} + b y^{q})^{n}$ :

Write the general term: $(j n) (a x^{p})^{n - j} (b y^{q})^{j} = (j n) a^{n - j} b^{j} x^{p (n - j)} y^{q j}$ .
Match exponents to solve for $j$ . If there's no integer solution, the coefficient is 0.
Plug in, keeping the constants $a^{n - j} b^{j}$ and the sign (a negative $b$ means $(- 1)^{j}$ ).

Quick facts

$(x + y)^{n}$ has $n + 1$ terms.
Coefficient of $x^{k}$ in $(1 + x)^{n}$ is $(k n)$ .

Plug in

x

and

y

to get sums

Plug in	Identity	Meaning
$x = y = 1$	$k = 0 \sum n (k n) = 2^{n}$	total number of subsets
$x = 1, y = - 1$	$k = 0 \sum n (- 1)^{k} (k n) = 0$ ( $n \geq 1$ )	# even-size subsets = # odd-size subsets
$x = 1, y = 2$	$k = 0 \sum n 2^{k} (k n) = 3^{n}$

Combinatorial proof (from class). Know how to write this.

Let $S = {x_{1}, \dots, x_{n}, x_{n + 1}}$ . Count the $k$ -subsets of $S$ , which is $(k n + 1)$ , by splitting on whether $x_{n + 1}$ is chosen:

Contains $x_{n + 1}$ : choose the other $k - 1$ from ${x_{1}, \dots, x_{n}}$ , which is $(k - 1 n)$ .
Doesn't contain $x_{n + 1}$ : choose all $k$ from ${x_{1}, \dots, x_{n}}$ , which is $(k n)$ .

The cases are disjoint, so by the sum rule $(k n + 1) = (k - 1 n) + (k n)$ .

Template: count one set in two ways

Describe a set of objects (committees, subsets, bit strings, paths…).
Count it one way, and get the left side.
Count it another way, and get the right side.
Conclude: both count the same set, so they're equal.

6.5 Generalized Permutations & Combinations

The four counting formulas. Memorize this table.

Selecting $r$ items from $n$ types/objects:

	No repetition	Repetition allowed
Order matters	$P (n, r) = \frac{n !}{( n - r )!}$	$n^{r}$
Order doesn't matter	$(r n)$	$(r n + r - 1)$

Plus: arranging $n$ objects where $n_{1}$ are identical of type 1, …, $n_{k}$ identical of type $k$ :
$\frac{n !}{n _{1} ! n _{2} ! \dots n _{k} !}$

Stars and bars. Know why it works.

Represent a selection of $r$ items from $n$ types as $r$ stars and $n - 1$ bars (dividers between the $n$ types). For example, with 4 types and 6 items:
$⋆ ⋆ ∣ ⋆ ∣ ∣ ⋆ ⋆ ⋆ = 2 of type 1, 1 of type 2, 0 of type 3, 3 of type 4.$
Every arrangement of $r$ stars and $n - 1$ bars is one selection, so the count is the number of ways to choose star positions among $n + r - 1$ spots: $(r n + r - 1)$ .

Memory aid: $(items items + types - 1)$ or, equivalently, $(types - 1 items + types - 1)$ .

Equations are stars and bars

The number of solutions of $x_{1} + x_{2} + \dots + x_{n} = r$ with every $x_{i} \geq 0$ an integer is
$(r n + r - 1) = (n - 1 n + r - 1) .$
( $x_{i}$ = how many items of type $i$ ; $n$ variables = $n$ types.)

Handling constraints

Lower bound $x_{i} \geq a$ : give $a$ to $x_{i}$ up front. Subtract $a$ from the total, then count normally.
Upper bound $x_{i} \leq b$ : complement. (All solutions) − (solutions with $x_{i} \geq b + 1$ ).
Two upper bounds: inclusion–exclusion. All − (first violated) − (second violated) + (both violated).
Inequality $x_{1} + \dots + x_{n} \leq r$ : add a slack variable $x_{n + 1} \geq 0$ to make it $x_{1} + \dots + x_{n + 1} = r$ .

"Using some or all of the letters"

Split by length and by which letters are used (sum rule), applying $n! / (n_{1}! \dots)$ to each case. Organize by how many copies of the repeated letter you use.

Multinomial facts

Coefficient of $x^{a} y^{b} z^{c}$ in $(x + y + z)^{n}$ (with $a + b + c = n$ ): $\frac{n !}{a ! b ! c !}$ .
Number of distinct terms in $(x_{1} + \dots + x_{m})^{n}$ : $(n n + m - 1)$ . That's stars and bars, distributing the exponent $n$ among $m$ variables.

Ask these in order

Are some of the objects identical and you're arranging all of them (letters of a word)? Use $\frac{n !}{n _{1} ! \dots n _{k} !}$ .
Does order matter?
- Yes, with repetition: $n^{r}$ . Without: $P (n, r)$ .
- No, with repetition ("choose 12 donuts from 21 kinds", "solutions of $x_{1} + \dots = r$ "): $(r n + r - 1)$ . Without: $(r n)$ .
Constraints? Lower bounds: give them out first. Upper bounds: complement / inclusion–exclusion.