Appendix D: Math Foundations Refresher
If the algebra in a chapter ever slows you down, this is your refresher. It covers exactly the pre-college math this book relies on — no more. Skim it now to find your gaps, and return whenever a manipulation looks unfamiliar. (None of this is discrete math; it's the toolkit you bring with you.)
Working with exponents
For real $a, b$ and integers $m, n$:
| Rule | Example |
|---|---|
| $a^m \cdot a^n = a^{m+n}$ | $2^3 \cdot 2^4 = 2^7 = 128$ |
| $\dfrac{a^m}{a^n} = a^{m-n}$ | $\dfrac{5^6}{5^2} = 5^4$ |
| $(a^m)^n = a^{mn}$ | $(2^3)^2 = 2^6 = 64$ |
| $a^0 = 1$ (for $a \ne 0$) | $7^0 = 1$ |
| $a^{-n} = \dfrac{1}{a^n}$ | $2^{-3} = \tfrac{1}{8}$ |
The move you'll use most in induction: $a \cdot a^{k} = a^{k+1}$ (e.g., $2 \cdot 2^k = 2^{k+1}$).
Logarithms
$\log_b x$ is "the power you raise $b$ to in order to get $x$": $b^{(\log_b x)} = x$. In CS, base 2 is everywhere.
| Rule | Example |
|---|---|
| $\log_b(xy) = \log_b x + \log_b y$ | $\log_2 (8 \cdot 4) = 3 + 2 = 5$ |
| $\log_b(x/y) = \log_b x - \log_b y$ | |
| $\log_b(x^k) = k \log_b x$ | $\log_2(8^2) = 2 \cdot 3 = 6$ |
| $\log_b x = \dfrac{\log_c x}{\log_c b}$ (change of base) |
Key intuition: $\log_2 n$ is roughly the number of bits in $n$, and it grows very slowly — doubling $n$ adds just 1. This is why $O(\log n)$ algorithms (like binary search) are so fast.
Fractions
- Common denominator: $\dfrac{a}{c} + \dfrac{b}{d} = \dfrac{ad + bc}{cd}$.
- The induction workhorse: $\dfrac{k(k+1)}{2} + (k+1) = \dfrac{k(k+1) + 2(k+1)}{2} = \dfrac{(k+1)(k+2)}{2}.$
Factoring and expanding
| Pattern | |
|---|---|
| $(a+b)^2 = a^2 + 2ab + b^2$ | |
| $(a-b)^2 = a^2 - 2ab + b^2$ | |
| $a^2 - b^2 = (a-b)(a+b)$ | difference of squares |
| $(x + r)(x + s) = x^2 + (r+s)x + rs$ |
Pulling out a common factor is the single most useful move: $k(k+1) + 2(k+1) = (k+1)(k+2)$.
Summation notation
$\displaystyle\sum_{i=1}^{n} a_i$ means $a_1 + a_2 + \dots + a_n$. Useful facts (proved in Chapter 11):
- $\sum_{i=1}^{n} c = cn$ (a constant added $n$ times)
- $\sum_{i=1}^{n} i = \dfrac{n(n+1)}{2}$
- $\sum_{i=0}^{n-1} r^i = \dfrac{r^n - 1}{r - 1}$ for $r \ne 1$ (geometric series)
- Linearity: $\sum (\alpha a_i + \beta b_i) = \alpha \sum a_i + \beta \sum b_i$
Functions and growth
A function $f$ takes an input and returns an output, written $f(x)$. Recognize the basic growth shapes, slowest to fastest, since Chapter 14 ranks algorithms by them: $$\text{constant} < \log n < n < n\log n < n^2 < n^3 < 2^n < n!.$$
Sets of numbers (preview of Chapter 8)
$\mathbb{N}$ (naturals, including 0 in this book), $\mathbb{Z}$ (integers), $\mathbb{Q}$ (rationals), $\mathbb{R}$ (reals). Each contains the previous: $\mathbb{N} \subseteq \mathbb{Z} \subseteq \mathbb{Q} \subseteq \mathbb{R}$.
Inequalities
- Adding the same amount to both sides preserves $<$: if $a < b$ then $a + c < b + c$.
- Multiplying by a positive preserves it; by a negative flips it: if $a < b$ and $c < 0$ then $ac > bc$.
- Transitivity: $a < b$ and $b < c$ imply $a < c$ (used constantly in inequality inductions).
Where to get more help
If any section above felt shaky, a few hours on Khan Academy's Algebra and Precalculus tracks (free) will close the gap. You need fluency with these manipulations, not deep theory — the depth in this book is all on the discrete-math side.