Order of operations

Brackets, then powers, then \(\times\)/\(\div\) left to right, then \(+\)/\(-\) left to right. \(2 + 3 \times 4^2 = 2 + 48 = 50\)

Chapter 1

Signs

\((-a)(-b) = ab\), \((-a)b = -ab\), \(a - (-b) = a + b\)

Chapter 1

Division with remainder

\(a = qb + r\) with \(0 \le r < b\) (quotient \(q\), remainder \(r\))

Chapter 1

Absolute value

\(\lvert x \rvert = x\) if \(x \ge 0\), \(-x\) if \(x < 0\); distance between \(a\) and \(b\) is \(\lvert a - b \rvert\)

Chapter 1

Place value in base \(b\)

\((d_k \ldots d_1 d_0)_b = \sum_{i=0}^{k} d_i\, b^i\), e.g. \(1011_2 = 8 + 0 + 2 + 1 = 11\)

Chapter 1

gcd and lcm

\(\gcd(a, b) \cdot \operatorname{lcm}(a, b) = ab\) for positive integers

Chapter 1

Divisibility tests

By 3 or 9: digit sum divisible by 3 or 9. By 11: alternating digit sum divisible by 11. By 4: last two digits divisible by 4.

Chapter 1

Equivalent fractions

\(\dfrac{a}{b} = \dfrac{ka}{kb}\) for \(k \ne 0\)

Chapter 2

Add / subtract fractions

\(\dfrac{a}{b} \pm \dfrac{c}{d} = \dfrac{ad \pm bc}{bd}\) (or use the least common denominator)

Chapter 2

Multiply fractions

\(\dfrac{a}{b} \cdot \dfrac{c}{d} = \dfrac{ac}{bd}\)

Chapter 2

Divide fractions

\(\dfrac{a}{b} \div \dfrac{c}{d} = \dfrac{a}{b} \cdot \dfrac{d}{c} = \dfrac{ad}{bc}\)

Chapter 2

Percent of a quantity

\(p\%\) of \(x\) is \(\dfrac{p}{100}\, x\)

Chapter 2

Percentage change

\(\dfrac{\text{new} - \text{old}}{\text{old}} \times 100\%\)

Chapter 2

Successive changes

Multiply factors: up 10% then down 10% is \(1.1 \times 0.9 = 0.99\), a 1% fall overall

Chapter 2

Ratio split

Sharing \(T\) in the ratio \(a : b\) gives \(\dfrac{a}{a + b}T\) and \(\dfrac{b}{a + b}T\)

Chapter 2

Repeating decimal to fraction

\(0.\overline{d_1 \ldots d_k} = \dfrac{d_1 \ldots d_k}{10^k - 1}\), e.g. \(0.\overline{27} = \tfrac{27}{99} = \tfrac{3}{11}\)

Chapter 2

Product of powers

\(a^m a^n = a^{m+n}\)

Chapter 3

Quotient of powers

\(\dfrac{a^m}{a^n} = a^{m-n}\)

Chapter 3

Power of a power

\((a^m)^n = a^{mn}\)

Chapter 3

Power of a product / quotient

\((ab)^n = a^n b^n\), \(\left(\dfrac{a}{b}\right)^n = \dfrac{a^n}{b^n}\)

Chapter 3

Zero and negative exponents

\(a^0 = 1\) (\(a \ne 0\)), \(a^{-n} = \dfrac{1}{a^n}\)

Chapter 3

Fractional exponents

\(a^{1/n} = \sqrt[n]{a}\), \(a^{m/n} = \left(\sqrt[n]{a}\right)^m = \sqrt[n]{a^m}\) (\(a > 0\))

Chapter 3

Root rules

\(\sqrt{ab} = \sqrt{a}\sqrt{b}\), \(\sqrt{a/b} = \sqrt{a}/\sqrt{b}\) for \(a, b \ge 0\); but \(\sqrt{a + b} \ne \sqrt{a} + \sqrt{b}\)

Chapter 3

Square root of a square

\(\sqrt{x^2} = \lvert x \rvert\)

Chapter 3

Rationalising

\(\dfrac{1}{\sqrt{a}} = \dfrac{\sqrt{a}}{a}\), \(\dfrac{1}{\sqrt{a} + \sqrt{b}} = \dfrac{\sqrt{a} - \sqrt{b}}{a - b}\)

Chapter 3

Scientific notation

\(x = m \times 10^n\) with \(1 \le \lvert m \rvert < 10\); multiply by multiplying mantissas and adding exponents

Chapter 3

Definition of logarithm

\(\log_b x = y \iff b^y = x\) (\(b > 0\), \(b \ne 1\), \(x > 0\))

Chapter 12

Product / quotient laws

\(\log_b(xy) = \log_b x + \log_b y\), \(\log_b(x/y) = \log_b x - \log_b y\)

Chapter 12

Power law

\(\log_b(x^k) = k \log_b x\)

Chapter 12

Special values

\(\log_b 1 = 0\), \(\log_b b = 1\), \(b^{\log_b x} = x\), \(\log_b(b^x) = x\)

Chapter 12

Change of base

\(\log_b x = \dfrac{\ln x}{\ln b} = \dfrac{\log_{10} x}{\log_{10} b}\); e.g. \(\log_2 x \approx 3.32 \log_{10} x\)

Chapter 12

Exponential via \(e\)

\(a^x = e^{x \ln a}\)

Chapter 12

Not a law

\(\log(x + y) \ne \log x + \log y\); \((\log x)^2 \ne \log(x^2)\)

Chapter 12

Exponential growth / decay

\(N(t) = N_0 e^{kt}\) (growth \(k > 0\), decay \(k < 0\)); half-life form \(N_0 \left(\tfrac{1}{2}\right)^{t/T}\)

Chapter 12

Doubling time

\(T_2 = \dfrac{\ln 2}{k}\); for \(r\%\) per period, roughly \(70/r\) periods ("rule of 70")

Chapter 12

Compound interest

\(A = P\left(1 + \dfrac{r}{n}\right)^{nt}\); continuously compounded \(A = Pe^{rt}\)

Chapter 12

Defining \(e\)

\(e = \lim_{n \to \infty}\left(1 + \tfrac{1}{n}\right)^n \approx 2.71828\)

Chapter 12

Distributive law

\(a(b + c) = ab + ac\)

Chapter 4

Expanding two brackets

\((a + b)(c + d) = ac + ad + bc + bd\)

Chapter 4

Square of a sum / difference

\((a \pm b)^2 = a^2 \pm 2ab + b^2\)

Chapter 4

Difference of two squares

\(a^2 - b^2 = (a + b)(a - b)\)

Chapter 4

Cube of a sum / difference

\((a \pm b)^3 = a^3 \pm 3a^2 b + 3ab^2 \pm b^3\)

Chapter 7

Sum / difference of cubes

\(a^3 + b^3 = (a + b)(a^2 - ab + b^2)\), \(a^3 - b^3 = (a - b)(a^2 + ab + b^2)\)

Chapter 7

Difference of \(n\)th powers

\(a^n - b^n = (a - b)(a^{n-1} + a^{n-2}b + \cdots + ab^{n-2} + b^{n-1})\)

Chapter 7

Binomial theorem

\((a + b)^n = \sum_{k=0}^{n} \binom{n}{k} a^{n-k} b^k\)

Chapter 24

Remainder theorem

Dividing \(p(x)\) by \((x - r)\) leaves remainder \(p(r)\)

Chapter 7

Factor theorem

\((x - r)\) is a factor of \(p(x)\) \(\iff\) \(p(r) = 0\)

Chapter 7

Rational root theorem

If \(p/q\) (lowest terms) is a root of \(a_n x^n + \cdots + a_0\) with integer coefficients, then \(p\) divides \(a_0\) and \(q\) divides \(a_n\)

Chapter 7

Number of roots

A degree-\(n\) polynomial has at most \(n\) real roots, and exactly \(n\) complex roots counted with multiplicity

Chapter 7

End behaviour

Determined by the leading term \(a_n x^n\): its sign and whether \(n\) is even or odd

Chapter 7

Simplifying rational expressions

Cancel common factors, never common terms: \(\dfrac{x(x+1)}{x} = x + 1\) for \(x \ne 0\), but \(\dfrac{x + 1}{x} \ne 1\)

Chapter 4

Quadratic formula

\(ax^2 + bx + c = 0 \implies x = \dfrac{-b \pm \sqrt{b^2 - 4ac}}{2a}\) (\(a \ne 0\))

Chapter 8

Discriminant

\(\Delta = b^2 - 4ac\): \(\Delta > 0\) two real roots; \(\Delta = 0\) one repeated real root; \(\Delta < 0\) two complex-conjugate roots

Chapter 8

Completing the square

\(x^2 + bx = \left(x + \tfrac{b}{2}\right)^2 - \tfrac{b^2}{4}\)

Chapter 8

Vertex form

\(ax^2 + bx + c = a(x - h)^2 + k\) with \(h = -\dfrac{b}{2a}\), \(k = c - \dfrac{b^2}{4a}\); vertex \((h, k)\), axis of symmetry \(x = h\)

Chapter 8

Factored form

\(a(x - r_1)(x - r_2)\) where \(r_1, r_2\) are the roots

Chapter 8

Sum and product of roots (Vieta)

\(r_1 + r_2 = -\dfrac{b}{a}\), \(r_1 r_2 = \dfrac{c}{a}\)

Chapter 8

Numerically stable roots

\(q = -\tfrac{1}{2}\left(b + \operatorname{sign}(b)\sqrt{\Delta}\right)\), then \(x_1 = q/a\), \(x_2 = c/q\) (avoids cancellation when \(b^2 \gg 4ac\))

Chapter 8

Inequalities

Multiplying or dividing both sides by a negative number reverses the inequality: \(-2x < 6 \iff x > -3\)

Chapter 5

Absolute-value inequality

\(\lvert x - a \rvert < r \iff a - r < x < a + r\)

Chapter 5

Slope

\(m = \dfrac{y_2 - y_1}{x_2 - x_1} = \dfrac{\text{rise}}{\text{run}}\)

Chapter 5

Slope-intercept form

\(y = mx + b\) (slope \(m\), \(y\)-intercept \(b\))

Chapter 5

Point-slope form

\(y - y_1 = m(x - x_1)\)

Chapter 5

Standard form

\(Ax + By = C\); slope \(-A/B\)

Chapter 5

Parallel / perpendicular

Parallel: \(m_1 = m_2\). Perpendicular: \(m_1 m_2 = -1\)

Chapter 5

Two equations, two unknowns (Cramer)

\(ax + by = e,\ cx + dy = f \implies x = \dfrac{ed - bf}{ad - bc},\ y = \dfrac{af - ec}{ad - bc}\) (if \(ad - bc \ne 0\))

Chapter 6

Number of solutions of a linear system

Exactly one, none (inconsistent), or infinitely many; never exactly two

Chapter 6

Distance

\(d = \sqrt{(x_2 - x_1)^2 + (y_2 - y_1)^2}\)

Chapter 10

Midpoint

\(\left(\dfrac{x_1 + x_2}{2}, \dfrac{y_1 + y_2}{2}\right)\)

Chapter 10

Circle

Centre \((h, k)\), radius \(r\): \((x - h)^2 + (y - k)^2 = r^2\)

Chapter 10

Point-to-line distance

From \((x_0, y_0)\) to \(Ax + By + C = 0\): \(\dfrac{\lvert Ax_0 + By_0 + C \rvert}{\sqrt{A^2 + B^2}}\)

Chapter 10

Transformations of graphs

\(y = f(x - h) + k\) shifts right \(h\), up \(k\); \(y = af(x)\) stretches vertically by \(a\); \(y = f(bx)\) compresses horizontally by \(b\); \(y = -f(x)\) reflects in the \(x\)-axis; \(y = f(-x)\) in the \(y\)-axis

Chapter 11

Composition and inverse

\((f \circ g)(x) = f(g(x))\); \(f^{-1}(f(x)) = x\); graph of \(f^{-1}\) is the reflection of the graph of \(f\) in \(y = x\)

Chapter 11

Pythagoras

Right triangle with legs \(a, b\), hypotenuse \(c\): \(a^2 + b^2 = c^2\). Triples: 3-4-5, 5-12-13, 8-15-17

Chapter 9

Angle sums

Triangle \(180^\circ\); \(n\)-sided polygon \((n - 2) \times 180^\circ\); exterior angles of a convex polygon total \(360^\circ\)

Chapter 9

Special right triangles

45-45-90: sides \(1 : 1 : \sqrt{2}\). 30-60-90: sides \(1 : \sqrt{3} : 2\)

Chapter 9

Rectangle / parallelogram

Area \(lw\); parallelogram \(bh\) (\(h\) perpendicular height)

Chapter 9

Triangle

Area \(\tfrac{1}{2}bh = \tfrac{1}{2}ab\sin C\); Heron: \(\sqrt{s(s-a)(s-b)(s-c)}\) with \(s = \tfrac{a+b+c}{2}\)

Chapter 9

Trapezoid (UK: trapezium)

Area \(\tfrac{1}{2}(a + b)h\), \(a, b\) the parallel sides

Chapter 9

Circle

Circumference \(2\pi r = \pi d\); area \(\pi r^2\)

Chapter 9

Arc and sector (radians)

Arc length \(s = r\theta\); sector area \(\tfrac{1}{2}r^2\theta\)

Chapter 9

Degrees and radians

\(\pi \text{ rad} = 180^\circ\); \(1 \text{ rad} \approx 57.3^\circ\)

Chapter 13

Prism / cylinder

Volume \(Bh\) (\(B\) = base area); cylinder \(\pi r^2 h\), surface area \(2\pi r^2 + 2\pi rh\)

Chapter 9

Pyramid / cone

Volume \(\tfrac{1}{3}Bh\); cone \(\tfrac{1}{3}\pi r^2 h\)

Chapter 9

Sphere

Volume \(\tfrac{4}{3}\pi r^3\); surface area \(4\pi r^2\)

Chapter 9

Similar figures

Scale lengths by \(k\): areas scale by \(k^2\), volumes by \(k^3\)

Chapter 9

Circle theorems

Angle in a semicircle is \(90^\circ\); inscribed angle is half the central angle on the same arc; tangent is perpendicular to the radius

Chapter 9

SOH-CAH-TOA

\(\sin\theta = \dfrac{\text{opp}}{\text{hyp}}\), \(\cos\theta = \dfrac{\text{adj}}{\text{hyp}}\), \(\tan\theta = \dfrac{\text{opp}}{\text{adj}} = \dfrac{\sin\theta}{\cos\theta}\)

Chapter 13

Reciprocal functions

\(\sec\theta = \dfrac{1}{\cos\theta}\), \(\csc\theta = \dfrac{1}{\sin\theta}\), \(\cot\theta = \dfrac{1}{\tan\theta}\)

Chapter 13

Unit circle

The point at angle \(\theta\) is \((\cos\theta, \sin\theta)\)

Chapter 13

Signs by quadrant ("All Students Take Calculus")

Q1 all positive; Q2 only \(\sin\); Q3 only \(\tan\); Q4 only \(\cos\)

Chapter 13

Pythagorean identities

\(\sin^2\theta + \cos^2\theta = 1\), \(1 + \tan^2\theta = \sec^2\theta\), \(1 + \cot^2\theta = \csc^2\theta\)

Chapter 13

Symmetry

\(\sin(-\theta) = -\sin\theta\), \(\cos(-\theta) = \cos\theta\), \(\tan(-\theta) = -\tan\theta\)

Chapter 13

Co-function

\(\sin\left(\tfrac{\pi}{2} - \theta\right) = \cos\theta\), \(\cos\left(\tfrac{\pi}{2} - \theta\right) = \sin\theta\)

Chapter 13

Periodicity

\(\sin\) and \(\cos\) have period \(2\pi\); \(\tan\) has period \(\pi\); \(A\sin(bx + c) + d\) has amplitude \(\lvert A \rvert\), period \(2\pi / \lvert b \rvert\)

Chapter 13

Angle addition

\(\sin(\alpha \pm \beta) = \sin\alpha\cos\beta \pm \cos\alpha\sin\beta\); \(\cos(\alpha \pm \beta) = \cos\alpha\cos\beta \mp \sin\alpha\sin\beta\)

Chapter 13

Tangent addition

\(\tan(\alpha \pm \beta) = \dfrac{\tan\alpha \pm \tan\beta}{1 \mp \tan\alpha\tan\beta}\)

Chapter 13

Double angle

\(\sin 2\theta = 2\sin\theta\cos\theta\); \(\cos 2\theta = \cos^2\theta - \sin^2\theta = 2\cos^2\theta - 1 = 1 - 2\sin^2\theta\); \(\tan 2\theta = \dfrac{2\tan\theta}{1 - \tan^2\theta}\)

Chapter 13

Power reduction

\(\sin^2\theta = \tfrac{1}{2}(1 - \cos 2\theta)\), \(\cos^2\theta = \tfrac{1}{2}(1 + \cos 2\theta)\)

Chapter 13

Law of sines

\(\dfrac{a}{\sin A} = \dfrac{b}{\sin B} = \dfrac{c}{\sin C}\) (\(= 2R\), \(R\) the circumradius)

Chapter 13

Law of cosines

\(c^2 = a^2 + b^2 - 2ab\cos C\)

Chapter 13

Inverse function ranges

\(\arcsin: \lbrack -\tfrac{\pi}{2}, \tfrac{\pi}{2} \rbrack\), \(\arccos: \lbrack 0, \pi \rbrack\), \(\arctan: (-\tfrac{\pi}{2}, \tfrac{\pi}{2})\)

Chapter 13

Polar coordinates

\(x = r\cos\theta\), \(y = r\sin\theta\); \(r = \sqrt{x^2 + y^2}\), \(\theta = \operatorname{atan2}(y, x)\)

Chapter 13

Rotation by \(\theta\)

\((x, y) \mapsto (x\cos\theta - y\sin\theta,\ x\sin\theta + y\cos\theta)\)

Chapter 13

\(0^\circ\)

\(0\)

\(0\)

\(1\)

\(0\)

\(30^\circ\)

\(\tfrac{\pi}{6}\)

\(\tfrac{1}{2}\)

\(\tfrac{\sqrt{3}}{2}\)

\(\tfrac{1}{\sqrt{3}} = \tfrac{\sqrt{3}}{3}\)

\(45^\circ\)

\(\tfrac{\pi}{4}\)

\(\tfrac{\sqrt{2}}{2}\)

\(\tfrac{\sqrt{2}}{2}\)

\(1\)

\(60^\circ\)

\(\tfrac{\pi}{3}\)

\(\tfrac{\sqrt{3}}{2}\)

\(\tfrac{1}{2}\)

\(\sqrt{3}\)

\(90^\circ\)

\(\tfrac{\pi}{2}\)

\(1\)

\(0\)

undefined

\(120^\circ\)

\(\tfrac{2\pi}{3}\)

\(\tfrac{\sqrt{3}}{2}\)

\(-\tfrac{1}{2}\)

\(-\sqrt{3}\)

\(135^\circ\)

\(\tfrac{3\pi}{4}\)

\(\tfrac{\sqrt{2}}{2}\)

\(-\tfrac{\sqrt{2}}{2}\)

\(-1\)

\(150^\circ\)

\(\tfrac{5\pi}{6}\)

\(\tfrac{1}{2}\)

\(-\tfrac{\sqrt{3}}{2}\)

\(-\tfrac{\sqrt{3}}{3}\)

\(180^\circ\)

\(\pi\)

\(0\)

\(-1\)

\(0\)

\(270^\circ\)

\(\tfrac{3\pi}{2}\)

\(-1\)

\(0\)

undefined

\(360^\circ\)

\(2\pi\)

\(0\)

\(1\)

\(0\)

Arithmetic sequence

\(a_n = a_1 + (n - 1)d\); sum \(S_n = \dfrac{n(a_1 + a_n)}{2} = \dfrac{n}{2}\left(2a_1 + (n - 1)d\right)\)

Chapter 14

Geometric sequence

\(a_n = a_1 r^{n-1}\); sum \(S_n = a_1 \dfrac{1 - r^n}{1 - r}\) (\(r \ne 1\))

Chapter 14

Infinite geometric series

\(\sum_{n=0}^{\infty} a r^n = \dfrac{a}{1 - r}\) if \(\lvert r \rvert < 1\); diverges otherwise (for \(a \ne 0\))

Chapter 14

Sum of first \(n\) integers

\(\sum_{k=1}^{n} k = \dfrac{n(n+1)}{2}\)

Chapter 14

Sum of squares / cubes

\(\sum_{k=1}^{n} k^2 = \dfrac{n(n+1)(2n+1)}{6}\), \(\sum_{k=1}^{n} k^3 = \left(\dfrac{n(n+1)}{2}\right)^2\)

Chapter 14

Powers of two

\(\sum_{k=0}^{n-1} 2^k = 2^n - 1\)

Chapter 14

Harmonic numbers

\(H_n = \sum_{k=1}^{n} \dfrac{1}{k} \approx \ln n + 0.5772\); the harmonic series diverges

Chapter 14

\(p\)-series

\(\sum_{n=1}^{\infty} \dfrac{1}{n^p}\) converges iff \(p > 1\); \(\sum \dfrac{1}{n^2} = \dfrac{\pi^2}{6}\)

Chapter 14

Sigma rules

\(\sum (a_k + b_k) = \sum a_k + \sum b_k\), \(\sum c\,a_k = c \sum a_k\), \(\sum_{k=1}^{n} c = nc\)

Chapter 14

Recurrence (linear, first order)

\(a_n = r a_{n-1} + d\) has fixed point \(L = \dfrac{d}{1 - r}\) and \(a_n = L + r^n (a_0 - L)\) (\(r \ne 1\))

Chapter 14

Taylor polynomial

\(T_n(x) = \sum_{k=0}^{n} \dfrac{f^{(k)}(a)}{k!}(x - a)^k\)

Chapter 18

Standard series

\(e^x = \sum_{n \ge 0} \dfrac{x^n}{n!}\); \(\sin x = x - \dfrac{x^3}{3!} + \dfrac{x^5}{5!} - \cdots\); \(\cos x = 1 - \dfrac{x^2}{2!} + \dfrac{x^4}{4!} - \cdots\) (all \(x\))

Chapter 18

More standard series

\(\dfrac{1}{1 - x} = \sum_{n \ge 0} x^n\) (\(\lvert x \rvert < 1\)); \(\ln(1 + x) = x - \dfrac{x^2}{2} + \dfrac{x^3}{3} - \cdots\) (\(-1 < x \le 1\))

Chapter 18

Imaginary unit

\(i^2 = -1\); powers cycle \(i, -1, -i, 1\)

Chapter 15

Arithmetic

\((a + bi) \pm (c + di) = (a \pm c) + (b \pm d)i\); \((a + bi)(c + di) = (ac - bd) + (ad + bc)i\)

Chapter 15

Conjugate

\(\overline{a + bi} = a - bi\); \(z\bar{z} = a^2 + b^2\); \(\overline{zw} = \bar{z}\,\bar{w}\)

Chapter 15

Division

\(\dfrac{a + bi}{c + di} = \dfrac{(a + bi)(c - di)}{c^2 + d^2} = \dfrac{(ac + bd) + (bc - ad)i}{c^2 + d^2}\)

Chapter 15

Modulus and argument

\(\lvert z \rvert = \sqrt{a^2 + b^2}\); \(\arg z = \operatorname{atan2}(b, a)\)

Chapter 15

Polar / exponential form

\(z = r(\cos\theta + i\sin\theta) = re^{i\theta}\)

Chapter 15

Euler’s formula

\(e^{i\theta} = \cos\theta + i\sin\theta\); hence \(e^{i\pi} + 1 = 0\)

Chapter 15

Multiplying in polar form

Moduli multiply, arguments add: \(r_1 e^{i\theta_1} \cdot r_2 e^{i\theta_2} = r_1 r_2\, e^{i(\theta_1 + \theta_2)}\)

Chapter 15

De Moivre

\((\cos\theta + i\sin\theta)^n = \cos n\theta + i\sin n\theta\)

Chapter 15

Roots of unity

Solutions of \(z^n = 1\): \(z_k = e^{2\pi i k/n}\), \(k = 0, 1, \ldots, n - 1\)

Chapter 15

Real polynomials

Non-real roots come in conjugate pairs \(a \pm bi\)

Chapter 15

Limit laws

Limits of sums, differences, products, constant multiples and quotients are the sums (etc.) of the limits, provided those exist and the denominator’s limit is nonzero

Chapter 16

Continuity at \(a\)

\(\lim_{x \to a} f(x) = f(a)\)

Chapter 16

Formal definition

\(\lim_{x \to a} f(x) = L\) means: for every \(\varepsilon > 0\) there is \(\delta > 0\) with \(0 < \lvert x - a \rvert < \delta \implies \lvert f(x) - L \rvert < \varepsilon\)

Chapter 16

Key trigonometric limits

\(\lim_{x \to 0} \dfrac{\sin x}{x} = 1\), \(\lim_{x \to 0} \dfrac{1 - \cos x}{x} = 0\)

Chapter 16

Limits defining \(e\)

\(\lim_{n \to \infty}\left(1 + \dfrac{1}{n}\right)^n = e\), \(\lim_{x \to 0} \dfrac{e^x - 1}{x} = 1\)

Chapter 16

Growth hierarchy as \(x \to \infty\)

\(\ln x \ll x^p \ll a^x \ll x!\) (any \(p > 0\), \(a > 1\)); e.g. \(\dfrac{x^{100}}{e^x} \to 0\)

Chapter 16

Rational functions at \(\infty\)

Compare degrees: top lower \(\to 0\); equal \(\to\) ratio of leading coefficients; top higher \(\to \pm\infty\)

Chapter 16

Squeeze theorem

If \(g \le f \le h\) near \(a\) and \(g, h \to L\), then \(f \to L\)

Chapter 16

L’Hôpital’s rule

For \(\tfrac{0}{0}\) or \(\tfrac{\infty}{\infty}\) forms: \(\lim \dfrac{f(x)}{g(x)} = \lim \dfrac{f'(x)}{g'(x)}\) if the right side exists

Chapter 18

Intermediate value theorem

If \(f\) is continuous on \(\lbrack a, b \rbrack\) and \(y\) lies between \(f(a)\) and \(f(b)\), some \(c\) in \(\lbrack a, b \rbrack\) has \(f(c) = y\)

Chapter 16

Definition

\(f'(x) = \lim_{h \to 0} \dfrac{f(x + h) - f(x)}{h}\)

Chapter 17

Constant / linearity

\((c)' = 0\); \((af + bg)' = af' + bg'\)

Chapter 17

Power rule

\(\dfrac{d}{dx} x^n = n x^{n-1}\) (any real \(n\))

Chapter 17

Product rule

\((fg)' = f'g + fg'\)

Chapter 17

Quotient rule

\(\left(\dfrac{f}{g}\right)' = \dfrac{f'g - fg'}{g^2}\)

Chapter 17

Chain rule

\(\dfrac{d}{dx} f(g(x)) = f'(g(x))\, g'(x)\); in Leibniz form \(\dfrac{dy}{dx} = \dfrac{dy}{du}\dfrac{du}{dx}\)

Chapter 17

Exponentials

\((e^x)' = e^x\); \((a^x)' = a^x \ln a\)

Chapter 17

Logarithms

\((\ln x)' = \dfrac{1}{x}\); \((\log_a x)' = \dfrac{1}{x \ln a}\); \((\ln \lvert x \rvert)' = \dfrac{1}{x}\)

Chapter 17

Trigonometric

\((\sin x)' = \cos x\); \((\cos x)' = -\sin x\); \((\tan x)' = \sec^2 x\)

Chapter 17

Inverse trigonometric

\((\arcsin x)' = \dfrac{1}{\sqrt{1 - x^2}}\); \((\arccos x)' = -\dfrac{1}{\sqrt{1 - x^2}}\); \((\arctan x)' = \dfrac{1}{1 + x^2}\)

Chapter 17

Logistic sigmoid

\(\sigma(x) = \dfrac{1}{1 + e^{-x}}\), \(\sigma'(x) = \sigma(x)\left(1 - \sigma(x)\right)\)

Chapter 33

Implicit differentiation

Differentiate both sides with respect to \(x\), treating \(y\) as \(y(x)\): e.g. \(x^2 + y^2 = 1 \implies 2x + 2y y' = 0 \implies y' = -x/y\)

Chapter 17

Tangent line / linearisation

\(y = f(a) + f'(a)(x - a)\); so \(f(a + h) \approx f(a) + h f'(a)\)

Chapter 18

Critical points and tests

Critical point: \(f'(c) = 0\) or undefined. Second-derivative test: \(f''(c) > 0\) local min, \(f''(c) < 0\) local max, \(= 0\) inconclusive

Chapter 18

Closed-interval extrema

On \(\lbrack a, b \rbrack\) check critical points and both endpoints; the largest/smallest value wins

Chapter 18

Concavity / inflection

\(f'' > 0\) concave up, \(f'' < 0\) concave down; inflection where \(f''\) changes sign

Chapter 18

Mean value theorem

\(f\) continuous on \(\lbrack a, b \rbrack\), differentiable inside \(\implies f'(c) = \dfrac{f(b) - f(a)}{b - a}\) for some \(c \in (a, b)\)

Chapter 18

Newton’s method

\(x_{n+1} = x_n - \dfrac{f(x_n)}{f'(x_n)}\)

Chapter 18

Power rule

\(\int x^n\,dx = \dfrac{x^{n+1}}{n + 1} + C\) (\(n \ne -1\))

Chapter 19

Reciprocal

\(\int \dfrac{1}{x}\,dx = \ln \lvert x \rvert + C\)

Chapter 19

Exponentials

\(\int e^x\,dx = e^x + C\); \(\int e^{kx}\,dx = \dfrac{1}{k}e^{kx} + C\); \(\int a^x\,dx = \dfrac{a^x}{\ln a} + C\)

Chapter 19

Trigonometric

\(\int \sin x\,dx = -\cos x + C\); \(\int \cos x\,dx = \sin x + C\); \(\int \sec^2 x\,dx = \tan x + C\)

Chapter 19

Inverse-trig forms

\(\int \dfrac{dx}{1 + x^2} = \arctan x + C\); \(\int \dfrac{dx}{\sqrt{1 - x^2}} = \arcsin x + C\)

Chapter 19

Logarithm

\(\int \ln x\,dx = x\ln x - x + C\)

Chapter 19

Linearity

\(\int (af + bg)\,dx = a\int f\,dx + b\int g\,dx\)

Chapter 19

Fundamental theorem (part 1)

\(\dfrac{d}{dx}\int_a^x f(t)\,dt = f(x)\)

Chapter 19

Fundamental theorem (part 2)

\(\int_a^b f(x)\,dx = F(b) - F(a)\) where \(F' = f\)

Chapter 19

Definite-integral properties

\(\int_a^a f = 0\); \(\int_b^a f = -\int_a^b f\); \(\int_a^b f + \int_b^c f = \int_a^c f\)

Chapter 19

Substitution

\(\int f(g(x))\,g'(x)\,dx = \int f(u)\,du\) with \(u = g(x)\); for definite integrals change the limits to \(g(a), g(b)\)

Chapter 19

Integration by parts

\(\int u\,dv = uv - \int v\,du\)

Chapter 19

Riemann sum

\(\int_a^b f(x)\,dx = \lim_{n \to \infty} \sum_{i=1}^{n} f(x_i^*)\,\Delta x\), \(\Delta x = \dfrac{b - a}{n}\)

Chapter 19

Area between curves

\(\int_a^b \left(f(x) - g(x)\right)dx\) where \(f \ge g\) on \(\lbrack a, b \rbrack\)

Chapter 19

Average value

\(\bar{f} = \dfrac{1}{b - a}\int_a^b f(x)\,dx\)

Chapter 19

Volume of revolution (discs)

\(V = \pi \int_a^b f(x)^2\,dx\) about the \(x\)-axis

Chapter 19

Gaussian integral

\(\int_{-\infty}^{\infty} e^{-x^2}\,dx = \sqrt{\pi}\)

Chapter 30

Partial derivative

\(\dfrac{\partial f}{\partial x}\): differentiate in \(x\) holding the other variables fixed. Example: \(f = x^2 y \implies f_x = 2xy\), \(f_y = x^2\)

Chapter 20

Gradient

\(\nabla f = \left(\dfrac{\partial f}{\partial x_1}, \ldots, \dfrac{\partial f}{\partial x_n}\right)\); points in the direction of steepest ascent; its length is that steepest rate

Chapter 20

Directional derivative

\(D_{\mathbf{u}} f = \nabla f \cdot \mathbf{u}\) for a unit vector \(\mathbf{u}\)

Chapter 20

Gradient descent

\(\mathbf{x}_{k+1} = \mathbf{x}_k - \eta\, \nabla f(\mathbf{x}_k)\) (\(\eta\) the learning rate / step size)

Chapter 20

Tangent plane

\(z = f(a, b) + f_x(a, b)(x - a) + f_y(a, b)(y - b)\)

Chapter 20

Multivariable chain rule

\(\dfrac{d}{dt} f(x(t), y(t)) = f_x \dfrac{dx}{dt} + f_y \dfrac{dy}{dt} = \nabla f \cdot \mathbf{r}'(t)\)

Chapter 20

Critical points and second-derivative test

\(\nabla f = \mathbf{0}\); with \(D = f_{xx}f_{yy} - f_{xy}^2\): \(D > 0, f_{xx} > 0\) min; \(D > 0, f_{xx} < 0\) max; \(D < 0\) saddle; \(D = 0\) inconclusive

Chapter 20

Hessian

\(H_{ij} = \dfrac{\partial^2 f}{\partial x_i \partial x_j}\); symmetric for smooth \(f\)

Chapter 20

Lagrange multipliers

Optimise \(f\) subject to \(g = c\): solve \(\nabla f = \lambda \nabla g\), \(g = c\)

Chapter 20

Conditional as "or"

\(p \to q \equiv \neg p \lor q\); false only when \(p\) is true and \(q\) false

Chapter 21

Contrapositive (equivalent)

\(p \to q \equiv \neg q \to \neg p\)

Chapter 21

Converse and inverse (not equivalent to \(p \to q\))

Converse \(q \to p\); inverse \(\neg p \to \neg q\) (these two are equivalent to each other)

Chapter 21

Negating a conditional

\(\neg(p \to q) \equiv p \land \neg q\)

Chapter 21

Biconditional

\(p \leftrightarrow q \equiv (p \to q) \land (q \to p)\)

Chapter 21

De Morgan

\(\neg(p \land q) \equiv \neg p \lor \neg q\); \(\neg(p \lor q) \equiv \neg p \land \neg q\)

Chapter 21

Double negation

\(\neg\neg p \equiv p\)

Chapter 21

Distributive

\(p \land (q \lor r) \equiv (p \land q) \lor (p \land r)\); \(p \lor (q \land r) \equiv (p \lor q) \land (p \lor r)\)

Chapter 21

Absorption

\(p \lor (p \land q) \equiv p\); \(p \land (p \lor q) \equiv p\)

Chapter 21

Excluded middle / contradiction

\(p \lor \neg p \equiv \mathbf{T}\); \(p \land \neg p \equiv \mathbf{F}\)

Chapter 21

Exclusive or

\(p \oplus q \equiv (p \lor q) \land \neg(p \land q)\)

Chapter 21

Negating quantifiers

\(\neg \forall x\, P(x) \equiv \exists x\, \neg P(x)\); \(\neg \exists x\, P(x) \equiv \forall x\, \neg P(x)\)

Chapter 21

Quantifier order matters

\(\forall x\, \exists y\, P(x, y)\) is generally not equivalent to \(\exists y\, \forall x\, P(x, y)\)

Chapter 21

Basic operations

\(A \cup B\) (in either), \(A \cap B\) (in both), \(A \setminus B\) (in \(A\) not \(B\)), \(A^c\) (not in \(A\))

Chapter 21

Difference via complement

\(A \setminus B = A \cap B^c\)

Chapter 21

De Morgan for sets

\((A \cup B)^c = A^c \cap B^c\); \((A \cap B)^c = A^c \cup B^c\)

Chapter 21

Distributive

\(A \cap (B \cup C) = (A \cap B) \cup (A \cap C)\); \(A \cup (B \cap C) = (A \cup B) \cap (A \cup C)\)

Chapter 21

Subset tests

\(A \subseteq B \iff A \cap B = A \iff A \cup B = B\)

Chapter 21

Inclusion-exclusion (two sets)

\(\lvert A \cup B \rvert = \lvert A \rvert + \lvert B \rvert - \lvert A \cap B \rvert\)

Chapter 24

Inclusion-exclusion (three sets)

\(\lvert A \cup B \cup C \rvert = \lvert A \rvert + \lvert B \rvert + \lvert C \rvert - \lvert A \cap B \rvert - \lvert A \cap C \rvert - \lvert B \cap C \rvert + \lvert A \cap B \cap C \rvert\)

Chapter 24

Power set

\(\lvert \mathcal{P}(A) \rvert = 2^{\lvert A \rvert}\)

Chapter 21

Cartesian product

\(\lvert A \times B \rvert = \lvert A \rvert \cdot \lvert B \rvert\)

Chapter 21

Direct proof

\(p \to q\): assume \(p\), deduce \(q\) step by step

Chapter 22

Contrapositive

\(p \to q\): assume \(\neg q\), deduce \(\neg p\)

Chapter 22

Contradiction

\(p\): assume \(\neg p\), derive something impossible

Chapter 22

Cases

Split into exhaustive cases and prove each

Chapter 22

Counterexample

To disprove \(\forall x\, P(x)\), exhibit one \(x\) with \(\neg P(x)\)

Chapter 22

Induction

\(P(n)\) for all \(n \ge n_0\): prove \(P(n_0)\) (base case), then \(P(k) \implies P(k+1)\) (inductive step)

Chapter 22

Strong induction

Inductive step assumes \(P(n_0), \ldots, P(k)\) all hold, then proves \(P(k+1)\)

Chapter 22

Loop invariant

Induction applied to code: true before the loop, preserved by each iteration, so true at exit

Chapter 22

Sum rule

Choose one of \(m\) options or one of \(n\) (disjoint): \(m + n\)

Chapter 24

Product rule

Make a choice with \(m\) options then one with \(n\): \(mn\)

Chapter 24

Ordered, repetition allowed

Sequences of length \(r\) from \(n\) symbols: \(n^r\)

Chapter 24

Arrangements of \(n\) distinct items

\(n! = n(n-1)\cdots 2 \cdot 1\), with \(0! = 1\)

Chapter 24

Permutations (ordered, no repetition)

\(P(n, r) = \dfrac{n!}{(n - r)!}\)

Chapter 24

Combinations (unordered, no repetition)

\(\dbinom{n}{r} = \dfrac{n!}{r!\,(n - r)!}\)

Chapter 24

Multisets / stars and bars (unordered, repetition allowed)

Choose \(r\) from \(n\) types: \(\dbinom{n + r - 1}{r}\)

Chapter 24

Arrangements with repeated items

\(\dfrac{n!}{n_1!\, n_2! \cdots n_k!}\) (e.g. MISSISSIPPI: \(\tfrac{11!}{1!\,4!\,4!\,2!} = 34650\))

Chapter 24

Pascal’s rule and symmetry

\(\dbinom{n}{k} = \dbinom{n-1}{k-1} + \dbinom{n-1}{k}\); \(\dbinom{n}{k} = \dbinom{n}{n-k}\)

Chapter 24

Row sum

\(\sum_{k=0}^{n} \dbinom{n}{k} = 2^n\) (the number of subsets of an \(n\)-set)

Chapter 24

Derangements

Permutations with no fixed point: \(D_n = n! \sum_{k=0}^{n} \dfrac{(-1)^k}{k!} \approx \dfrac{n!}{e}\)

Chapter 24

Pigeonhole principle

\(n\) items in \(m < n\) boxes: some box holds at least \(\lceil n/m \rceil\) items

Chapter 24

Handshake lemma

\(\sum_{v} \deg(v) = 2\lvert E \rvert\); so the number of odd-degree vertices is even

Chapter 25

Complete graph

\(K_n\) has \(\dbinom{n}{2} = \dfrac{n(n-1)}{2}\) edges

Chapter 25

Trees

A tree on \(n\) vertices is connected, acyclic, and has exactly \(n - 1\) edges

Chapter 25

Euler circuit

Exists in a connected graph iff every vertex has even degree (path: exactly 0 or 2 odd vertices)

Chapter 25

Euler’s formula (planar, connected)

\(V - E + F = 2\)

Chapter 25

Traversal cost

BFS and DFS run in \(O(V + E)\) with adjacency lists

Chapter 25

Congruence

\(a \equiv b \pmod{m} \iff m \mid (a - b)\) (same remainder on division by \(m\))

Chapter 23

Arithmetic respects congruence

If \(a \equiv b\) and \(c \equiv d \pmod{m}\) then \(a \pm c \equiv b \pm d\) and \(ac \equiv bd \pmod{m}\)

Chapter 23

Reduce early

\((a \cdot b) \bmod m = \left((a \bmod m)(b \bmod m)\right) \bmod m\); same for \(+\)

Chapter 23

Euclidean algorithm

\(\gcd(a, b) = \gcd(b, a \bmod b)\), \(\gcd(a, 0) = a\)

Chapter 23

Bézout’s identity

\(\gcd(a, b) = ax + by\) for some integers \(x, y\) (found by the extended Euclidean algorithm)

Chapter 23

Modular inverse

\(a^{-1} \bmod m\) exists iff \(\gcd(a, m) = 1\)

Chapter 23

Fundamental theorem of arithmetic

Every integer \(n \ge 2\) factors into primes uniquely (up to order)

Chapter 23

Fermat’s little theorem

\(p\) prime, \(p \nmid a \implies a^{p-1} \equiv 1 \pmod{p}\)

Chapter 23

Euler’s totient

\(\varphi(n)\) = number of \(1 \le k \le n\) coprime to \(n\); \(\varphi(p) = p - 1\); \(\varphi(pq) = (p-1)(q-1)\) for distinct primes

Chapter 23

Euler’s theorem

\(\gcd(a, n) = 1 \implies a^{\varphi(n)} \equiv 1 \pmod{n}\)

Chapter 23

Chinese remainder theorem

If \(m_1, \ldots, m_k\) are pairwise coprime, the system \(x \equiv a_i \pmod{m_i}\) has a unique solution modulo \(m_1 m_2 \cdots m_k\)

Chapter 23

RSA

\(n = pq\); pick \(e\) coprime to \(\varphi(n)\); \(d \equiv e^{-1} \pmod{\varphi(n)}\). Encrypt \(c = m^e \bmod n\); decrypt \(m = c^d \bmod n\)

Chapter 23

Fast exponentiation

Square-and-multiply computes \(a^k \bmod m\) in \(O(\log k)\) multiplications

Chapter 23

Length (norm)

\(\lVert \mathbf{v} \rVert = \sqrt{v_1^2 + \cdots + v_n^2}\); unit vector \(\hat{\mathbf{v}} = \mathbf{v} / \lVert \mathbf{v} \rVert\)

Chapter 26

Dot product

\(\mathbf{u} \cdot \mathbf{v} = \sum_i u_i v_i = \lVert \mathbf{u} \rVert \lVert \mathbf{v} \rVert \cos\theta\)

Chapter 26

Orthogonality

\(\mathbf{u} \perp \mathbf{v} \iff \mathbf{u} \cdot \mathbf{v} = 0\)

Chapter 26

Cosine similarity

\(\cos\theta = \dfrac{\mathbf{u} \cdot \mathbf{v}}{\lVert \mathbf{u} \rVert \lVert \mathbf{v} \rVert}\)

Chapter 26

Projection of \(\mathbf{u}\) onto \(\mathbf{v}\)

\(\operatorname{proj}_{\mathbf{v}} \mathbf{u} = \dfrac{\mathbf{u} \cdot \mathbf{v}}{\mathbf{v} \cdot \mathbf{v}}\, \mathbf{v}\)

Chapter 26

Cross product (3D)

\(\mathbf{u} \times \mathbf{v} = (u_2 v_3 - u_3 v_2,\ u_3 v_1 - u_1 v_3,\ u_1 v_2 - u_2 v_1)\); length \(\lVert \mathbf{u} \rVert \lVert \mathbf{v} \rVert \sin\theta\), perpendicular to both

Chapter 26

Triangle and Cauchy-Schwarz inequalities

\(\lVert \mathbf{u} + \mathbf{v} \rVert \le \lVert \mathbf{u} \rVert + \lVert \mathbf{v} \rVert\); \(\lvert \mathbf{u} \cdot \mathbf{v} \rvert \le \lVert \mathbf{u} \rVert \lVert \mathbf{v} \rVert\)

Chapter 26

Matrix product

\((AB)_{ij} = \sum_k A_{ik} B_{kj}\); needs (columns of \(A\)) = (rows of \(B\)); in general \(AB \ne BA\)

Chapter 27

Transpose rules

\((A^T)_{ij} = A_{ji}\); \((AB)^T = B^T A^T\)

Chapter 27

Inverse rules

\(AA^{-1} = A^{-1}A = I\); \((AB)^{-1} = B^{-1}A^{-1}\); \((A^T)^{-1} = (A^{-1})^T\)

Chapter 27

\(2 \times 2\) determinant

\(\det\begin{pmatrix} a & b \\ c & d \end{pmatrix} = ad - bc\)

Chapter 27

\(2 \times 2\) inverse

\(\begin{pmatrix} a & b \\ c & d \end{pmatrix}^{-1} = \dfrac{1}{ad - bc}\begin{pmatrix} d & -b \\ -c & a \end{pmatrix}\) (if \(ad - bc \ne 0\))

Chapter 27

\(3 \times 3\) determinant (first-row expansion)

\(a(ei - fh) - b(di - fg) + c(dh - eg)\) for rows \((a, b, c), (d, e, f), (g, h, i)\)

Chapter 27

Determinant facts

\(\det(AB) = \det A \det B\); \(\det A^T = \det A\); \(A\) invertible \(\iff \det A \ne 0\); \(\lvert \det A \rvert\) is the area/volume scale factor

Chapter 27

Rotation by \(\theta\) (2D)

\(R_\theta = \begin{pmatrix} \cos\theta & -\sin\theta \\ \sin\theta & \cos\theta \end{pmatrix}\); \(R_\theta^{-1} = R_\theta^T = R_{-\theta}\)

Chapter 27

Least squares (normal equations)

Minimise \(\lVert A\mathbf{x} - \mathbf{b} \rVert\): solve \(A^T A \mathbf{x} = A^T \mathbf{b}\)

Chapter 27

Eigenvalues and eigenvectors

\(A\mathbf{v} = \lambda \mathbf{v}\), \(\mathbf{v} \ne \mathbf{0}\); eigenvalues solve \(\det(A - \lambda I) = 0\)

Chapter 28

\(2 \times 2\) characteristic equation

\(\lambda^2 - (\operatorname{tr} A)\lambda + \det A = 0\); in general \(\operatorname{tr} A = \sum \lambda_i\), \(\det A = \prod \lambda_i\)

Chapter 28

Diagonalisation / spectral theorem

\(A = PDP^{-1}\); for symmetric \(A\), \(A = Q\Lambda Q^T\) with \(Q\) orthogonal and real eigenvalues

Chapter 28

Singular value decomposition

\(A = U\Sigma V^T\) (\(U, V\) orthogonal, \(\Sigma\) diagonal, non-negative)

Chapter 28

Range and total

\(0 \le P(A) \le 1\), \(P(\Omega) = 1\)

Chapter 29

Equally likely outcomes

\(P(A) = \dfrac{\text{number of outcomes in } A}{\text{total number of outcomes}}\)

Chapter 29

Complement

\(P(A^c) = 1 - P(A)\); "at least one" \(= 1 - P(\text{none})\)

Chapter 29

Addition rule

\(P(A \cup B) = P(A) + P(B) - P(A \cap B)\); just \(P(A) + P(B)\) if mutually exclusive

Chapter 29

Conditional probability

\(P(A \mid B) = \dfrac{P(A \cap B)}{P(B)}\) (\(P(B) > 0\))

Chapter 29

Multiplication rule

\(P(A \cap B) = P(A \mid B)\,P(B) = P(B \mid A)\,P(A)\)

Chapter 29

Independence

\(P(A \cap B) = P(A)\,P(B)\), equivalently \(P(A \mid B) = P(A)\)

Chapter 29

Law of total probability

\(P(A) = \sum_i P(A \mid B_i)\,P(B_i)\) for a partition \(B_1, B_2, \ldots\)

Chapter 29

Bayes' theorem

\(P(H \mid E) = \dfrac{P(E \mid H)\,P(H)}{P(E)} = \dfrac{P(E \mid H)\,P(H)}{P(E \mid H)\,P(H) + P(E \mid H^c)\,P(H^c)}\)

Chapter 29

Birthday bound

With \(N\) equally likely values and \(n\) draws, \(P(\text{some repeat}) \approx 1 - e^{-n(n-1)/(2N)}\); likely once \(n \approx 1.18\sqrt{N}\)

Chapter 29

Expectation

\(E[X] = \sum_x x\,P(X = x)\) (discrete) or \(\int x\,f(x)\,dx\) (continuous)

Chapter 30

Linearity of expectation

\(E[aX + bY + c] = aE[X] + bE[Y] + c\) (always, even if dependent)

Chapter 30

Variance

\(\operatorname{Var}(X) = E[(X - \mu)^2] = E[X^2] - (E[X])^2\); \(\sigma = \sqrt{\operatorname{Var}(X)}\)

Chapter 30

Variance rules

\(\operatorname{Var}(aX + b) = a^2 \operatorname{Var}(X)\); \(\operatorname{Var}(X + Y) = \operatorname{Var}(X) + \operatorname{Var}(Y) + 2\operatorname{Cov}(X, Y)\)

Chapter 30

Covariance and correlation

\(\operatorname{Cov}(X, Y) = E[XY] - E[X]E[Y]\); \(\rho = \dfrac{\operatorname{Cov}(X, Y)}{\sigma_X \sigma_Y} \in \lbrack -1, 1 \rbrack\); independent \(\implies\) covariance 0 (not conversely)

Chapter 30

Bernoulli \((p)\)

\(P(X = 1) = p\), \(P(X = 0) = 1 - p\)

\(p\)

\(p(1 - p)\)

Chapter 30

Binomial \((n, p)\)

\(\dbinom{n}{k} p^k (1 - p)^{n-k}\), \(k = 0, \ldots, n\)

\(np\)

\(np(1 - p)\)

Chapter 30

Geometric \((p)\) (trials until first success)

\((1 - p)^{k-1} p\), \(k = 1, 2, \ldots\)

\(\dfrac{1}{p}\)

\(\dfrac{1 - p}{p^2}\)

Chapter 30

Poisson \((\lambda)\)

\(\dfrac{e^{-\lambda}\lambda^k}{k!}\), \(k = 0, 1, 2, \ldots\)

\(\lambda\)

\(\lambda\)

Chapter 30

Discrete uniform on \(\{1, \ldots, n\}\)

\(\dfrac{1}{n}\)

\(\dfrac{n + 1}{2}\)

\(\dfrac{n^2 - 1}{12}\)

Chapter 30

Continuous uniform on \(\lbrack a, b \rbrack\)

\(\dfrac{1}{b - a}\) for \(a \le x \le b\)

\(\dfrac{a + b}{2}\)

\(\dfrac{(b - a)^2}{12}\)

Chapter 30

Exponential \((\lambda)\)

\(\lambda e^{-\lambda x}\) for \(x \ge 0\)

\(\dfrac{1}{\lambda}\)

\(\dfrac{1}{\lambda^2}\)

Chapter 30

Normal \((\mu, \sigma^2)\)

\(\dfrac{1}{\sigma\sqrt{2\pi}}\, e^{-(x - \mu)^2 / (2\sigma^2)}\)

\(\mu\)

\(\sigma^2\)

Chapter 30

Standardising

\(Z = \dfrac{X - \mu}{\sigma}\) has mean 0 and standard deviation 1

Chapter 30

68-95-99.7 rule

For a normal distribution, about 68%, 95% and 99.7% of values lie within 1, 2 and 3 standard deviations of the mean

Chapter 30

Central limit theorem

For \(n\) independent draws with mean \(\mu\) and variance \(\sigma^2\), the sample mean \(\bar{X}\) is approximately \(N(\mu, \sigma^2 / n)\) for large \(n\)

Chapter 30

Law of large numbers

\(\bar{X} \to \mu\) as \(n \to \infty\)

Chapter 30

Mean

\(\bar{x} = \dfrac{1}{n}\sum_{i=1}^{n} x_i\)

Chapter 31

Median, quartiles, IQR

Median: middle value of the sorted data (average the two middle values if \(n\) is even); \(\text{IQR} = Q_3 - Q_1\); outlier rule of thumb: beyond \(1.5 \times \text{IQR}\) from the quartiles

Chapter 31

Population variance

\(\sigma^2 = \dfrac{1}{N}\sum_{i=1}^{N} (x_i - \mu)^2\)

Chapter 31

Sample variance

\(s^2 = \dfrac{1}{n - 1}\sum_{i=1}^{n} (x_i - \bar{x})^2\) (divide by \(n - 1\), Bessel’s correction)

Chapter 31

z-score

\(z = \dfrac{x - \bar{x}}{s}\) (or \(\dfrac{x - \mu}{\sigma}\))

Chapter 31

Standard error of the mean

\(\text{SE} = \dfrac{\sigma}{\sqrt{n}} \approx \dfrac{s}{\sqrt{n}}\)

Chapter 31

Confidence interval for a mean

\(\bar{x} \pm t^* \dfrac{s}{\sqrt{n}}\) (\(t^* \approx z^* = 1.96\) for 95% with large \(n\))

Chapter 31

Confidence interval for a proportion

\(\hat{p} \pm z^* \sqrt{\dfrac{\hat{p}(1 - \hat{p})}{n}}\)

Chapter 31

Sample size for margin of error \(E\)

Proportion: \(n \approx \left(\dfrac{z^*}{E}\right)^2 \hat{p}(1 - \hat{p})\) (use \(\hat{p} = 0.5\) if unknown); 95%, \(\pm 3\%\) needs about 1068

Chapter 31

Correlation coefficient

\(r = \dfrac{\sum (x_i - \bar{x})(y_i - \bar{y})}{\sqrt{\sum (x_i - \bar{x})^2 \sum (y_i - \bar{y})^2}} \in \lbrack -1, 1 \rbrack\)

Chapter 31

Least-squares regression line

\(\hat{y} = a + bx\) with \(b = \dfrac{\sum (x_i - \bar{x})(y_i - \bar{y})}{\sum (x_i - \bar{x})^2} = r\dfrac{s_y}{s_x}\), \(a = \bar{y} - b\bar{x}\)

Chapter 31

Coefficient of determination

\(R^2 = 1 - \dfrac{\sum (y_i - \hat{y}_i)^2}{\sum (y_i - \bar{y})^2}\); equals \(r^2\) for a straight-line fit

Chapter 31

Hypothesis test

p-value = probability, if the null hypothesis were true, of data at least as extreme as observed. Reject \(H_0\) if p-value \(< \alpha\) (often 0.05)

Chapter 31

Test statistic for a mean

\(t = \dfrac{\bar{x} - \mu_0}{s / \sqrt{n}}\) (\(n - 1\) degrees of freedom)

Chapter 31

Newton’s method

\(x_{n+1} = x_n - \dfrac{f(x_n)}{f'(x_n)}\); quadratic convergence near a simple root (correct digits roughly double each step); can diverge from a poor start or where \(f' \approx 0\)

Chapter 32

Square root by Newton (Heron)

\(x_{n+1} = \tfrac{1}{2}\left(x_n + \dfrac{a}{x_n}\right) \to \sqrt{a}\)

Chapter 18

Bisection

If \(f(a)\) and \(f(b)\) differ in sign, test the midpoint \(m = \tfrac{a + b}{2}\) and keep the half where the sign changes. After \(n\) halvings the bracket has width \((b - a)/2^n\); need about \(\log_2\left((b - a)/\text{tol}\right)\) steps

Chapter 32

Secant method

\(x_{n+1} = x_n - f(x_n)\dfrac{x_n - x_{n-1}}{f(x_n) - f(x_{n-1})}\) (Newton without a derivative)

Chapter 32

Fixed-point iteration

\(x_{n+1} = g(x_n)\) converges near a fixed point \(x^*\) if \(\lvert g'(x^*) \rvert < 1\)

Chapter 32

Finite differences

Forward \(f'(x) \approx \dfrac{f(x + h) - f(x)}{h}\) (error \(O(h)\)); central \(f'(x) \approx \dfrac{f(x + h) - f(x - h)}{2h}\) (error \(O(h^2)\))

Chapter 32

Trapezoid rule

\(\int_a^b f \approx \dfrac{h}{2}\left(f_0 + 2f_1 + 2f_2 + \cdots + 2f_{n-1} + f_n\right)\), \(h = \dfrac{b - a}{n}\), \(f_i = f(a + ih)\); error \(O(h^2)\)

Chapter 32

Simpson’s rule (\(n\) even)

\(\int_a^b f \approx \dfrac{h}{3}\left(f_0 + 4f_1 + 2f_2 + 4f_3 + \cdots + 2f_{n-2} + 4f_{n-1} + f_n\right)\); error \(O(h^4)\)

Chapter 32

Euler’s method (ODE \(y' = f(t, y)\))

\(y_{n+1} = y_n + h\,f(t_n, y_n)\); error \(O(h)\)

Chapter 32

Floating point (IEEE double)

Machine epsilon \(2^{-52} \approx 2.2 \times 10^{-16}\); about 15-16 significant decimal digits; never test floats with \(==\), use a tolerance

Chapter 32

Absolute and relative error

\(\lvert \hat{x} - x \rvert\) and \(\dfrac{\lvert \hat{x} - x \rvert}{\lvert x \rvert}\)

Chapter 32

Mean squared error

\(\text{MSE} = \dfrac{1}{n}\sum_{i=1}^{n} (y_i - \hat{y}_i)^2\)

Chapter 33

Softmax

\(\operatorname{softmax}(\mathbf{z})_i = \dfrac{e^{z_i}}{\sum_j e^{z_j}}\) (subtract \(\max_j z_j\) first for numerical safety)

Chapter 33

Entropy (bits)

\(H(p) = -\sum_i p_i \log_2 p_i\); maximal (\(\log_2 n\)) for the uniform distribution on \(n\) outcomes

Chapter 33

Cross-entropy

\(H(p, q) = -\sum_i p_i \log q_i\); with a one-hot label it is \(-\log q_{\text{true}}\)

Chapter 33

Kullback-Leibler divergence

\(D_{\mathrm{KL}}(p \parallel q) = \sum_i p_i \log \dfrac{p_i}{q_i} = H(p, q) - H(p) \ge 0\)

Chapter 33