A Complete Guide to Integration: Single,

Double, Triple, and Line Integrals

The Nine Axioms (P1–P9)
Before any integral sign appears on the page, it’s worth naming the rules that license the symbol-
pushing to come. Every time a term moves from one side of an equation to the other, every time
an expression gets factored or two fractions get combined into one, what’s really happening is an
appeal to one of nine basic facts about how real numbers behave under addition and
multiplication. Calculus has a reputation for feeling like a bag of tricks, and the aim here is to
dismantle that reputation early: underneath every trick is ordinary algebra, and underneath
ordinary algebra sit these nine axioms, nothing more.
Let 𝑎, 𝑏, 𝑐 stand for arbitrary real numbers throughout (a real number, concretely, is any number
sitting somewhere on the number line: the integers, the fractions, and the irrational numbers like
𝜋 or √2 Are all included, with nothing left out).

• P1 (Associativity of addition): 𝑎 + (𝑏 + 𝑐) = (𝑎 + 𝑏) + 𝑐. Adding three numbers, it

makes no difference which pair gets added first; grouping is irrelevant to the outcome.

• P2 (Additive identity): There is a number 0 such that 𝑎 + 0 = 𝑎 for every 𝑎. A zero can
always be tacked onto any expression without changing its value, a move that turns out to
be surprisingly useful once “adding zero in a clever disguise” becomes a technique in its
own right.

• P3 (Additive inverse): For every 𝑎 there is a number −𝑎 such that 𝑎 + (−𝑎) = 0. Every
number, in other words, comes equipped with its own built-in undo button for addition,
and this gets used constantly to cancel a term.

• P4 (Commutativity of addition): 𝑎 + 𝑏 = 𝑏 + 𝑎. Order never matters when adding two

things, which sounds almost too obvious to bother stating, until a justification is needed
for reordering a long sum.

• P5 (Associativity of multiplication): 𝑎 ⋅ (𝑏 ⋅ 𝑐) = (𝑎 ⋅ 𝑏) ⋅ 𝑐. Just as with addition,

grouping doesn’t matter when multiplying three numbers together.

• P6 (Multiplicative identity): There is a number 1 ≠ 0 such that 𝑎 ⋅ 1 = 𝑎 for every 𝑎.

Multiplying by one leaves everything unchanged, and like P2, this becomes genuinely
!
useful the moment multiplying by a disguised version of 1 (say, !) becomes a way to
rewrite an expression.
 #
• P7 (Multiplicative inverse): For every 𝑎 ≠ 0 there is a number 𝑎"# (also written $) such
that 𝑎 ⋅ 𝑎"# = 1. Every nonzero number has an undo button for multiplication too, and
the word “nonzero” is doing real work there: dividing by zero is precisely the one
operation these nine axioms refuse to license.
• P8 (Commutativity of multiplication): 𝑎 ⋅ 𝑏 = 𝑏 ⋅ 𝑎. Order doesn’t matter when
multiplying, mirroring P4 for addition.

• P9 (Distributive law): 𝑎 ⋅ (𝑏 + 𝑐) = 𝑎 ⋅ 𝑏 + 𝑎 ⋅ 𝑐. Multiplication distributes over addition,

and of the nine axioms, this is the one that gets invoked the most by a wide margin.
Expanding a bracket and factoring an expression are the same move, P9, just run in
opposite directions.
Throughout this guide, every algebraic rearrangement gets flagged with whichever of P1–P9
licenses the step, in brackets, right where it happens. This will feel like overkill at first,
especially in the early worked examples, where the justification can seem more elaborate than
the algebra it’s justifying. The payoff, by the time triple integrals and beyond come into view, is a
clear picture of what calculus actually is: nothing but these nine facts about arithmetic, plus one
genuinely new idea, the limit, layered carefully on top. Limits get defined properly the moment
they’re needed, in the very next section, since they aren’t an algebraic concept and don’t reduce
to P1–P9 the way everything else here does.

PART 1: Single-Variable (Ordinary) Integrals

1.1 What problem is the integral trying to solve?
Start with a function 𝑓, meaning nothing more exotic than a rule: feed it an input number 𝑥, and
it hands back an output number 𝑓(𝑥). Suppose further that 𝑓 is continuous on some interval
[𝑎, 𝑏]. Informally, continuity means the graph of 𝑓 has no breaks, no sudden jumps, and no
missing points anywhere between 𝑥 = 𝑎 and 𝑥 = 𝑏; the whole curve could be traced without
lifting a pen. Here 𝑎 and 𝑏 are simply two real numbers with 𝑎 < 𝑏, marking the left and right
ends of the stretch under consideration.
Here is the question actually being asked, stated as precisely as possible: what is the exact area
trapped between the graph of 𝑓 and the horizontal axis, running from 𝑥 = 𝑎 to 𝑥 = 𝑏?

If 𝑓 happened to be constant, say 𝑓(𝑥) = 5, this would be no trouble at all: the region is just a
rectangle, width (𝑏 − 𝑎) Times height 5. But the moment 𝑓 curves, say 𝑓(𝑥) = 𝑥 % , that
rectangle formula stops applying entirely; there is no elementary shape whose area formula can
simply be borrowed. A genuinely new tool is needed, and building that tool is the point of
everything that follows.
1.2 Riemann sums: approximating the area with rectangles
Here is the idea, due to Bernhard Riemann, and it counts as one of the cleverest moves in
introductory calculus: the exact curved area can’t be computed directly, in one step, but it can be
approximated with a bunch of thin rectangles whose areas are already known, and then, crucially,
those rectangles can be made thinner and thinner until the approximation stops being an
approximation and becomes the exact answer. The construction is worth walking through slowly,
piece by piece, since every later technique in this guide is really just a variation on this same
idea.

Partition. A partition of [𝑎, 𝑏] into 𝑛 pieces (where 𝑛 is a positive integer, chosen freely, the
number of pieces desired) is a choice of points

𝑎 = 𝑥& < 𝑥# < 𝑥% < ⋯ < 𝑥' = 𝑏

Chopping the interval into 𝑛 smaller subintervals [𝑥& , 𝑥# ], [𝑥# , 𝑥% ], … , [𝑥'"# , 𝑥' ], laid end to end
with no gaps and no overlaps, covering the whole original interval exactly once.

Subinterval width. Write 𝛥𝑥( = 𝑥( − 𝑥("# For the width of the 𝑖-th subinterval. Splitting the
interval into equal pieces, by far the simplest and most common case, makes every one of these
)"$
widths the same: 𝛥𝑥 = '
. That equal-width version is what shows up in nearly every Calc 2
course, and it’s what gets used almost exclusively from here on.

Sample point. Inside each subinterval [𝑥("# , 𝑥( ], some point 𝑥(∗ Gets picked, and truly any point
will do; it could be the left endpoint, the right endpoint, the midpoint, or anywhere at all in
between. Whatever gets picked is called the “sample point” for that particular rectangle, since it’s
the single 𝑥-value used to decide how tall the rectangle over that subinterval should stand.

The Riemann sum. Now build an actual rectangle over each subinterval, with height 𝑓(𝑥(∗ ), the
function’s value at the sample point, and width 𝛥𝑥( , the width of that subinterval. Each rectangle
has area (height)(width), and adding up all 𝑛 of these areas gives the total approximation:
'

𝑆' = = 𝑓 (𝑥(∗ ) 𝛥𝑥(

(+#

The symbol ∑'(+# (“sigma notation”) is a compact way of writing “add up the following
expression as 𝑖 runs through 1,2, … , 𝑛.” It helps, the first time this notation appears, to write out
what it’s shorthand for in full: 𝑓(𝑥#∗ )𝛥𝑥# + 𝑓(𝑥%∗ )𝛥𝑥% + ⋯ + 𝑓(𝑥'∗ )𝛥𝑥' . Once that expansion
feels natural, the sigma notation stops looking mysterious and starts looking like exactly what it
is: a labor-saving abbreviation, nothing more.

The definite integral. Here is the payoff. As 𝑛 → ∞, meaning more and more rectangles get used,
each one thinner than the last, those rectangles hug the true curve more and more tightly. For a
continuous function 𝑓, something remarkable happens: the sum 𝑆' Approaches one specific
number, and it approaches that same number no matter how the sample points were chosen along
the way. That single limiting number is the definite integral, written:
'
)
B 𝑓 (𝑥) 𝑑𝑥 = Lim = 𝑓 (𝑥(∗ ) 𝛥𝑥(
$ '→-
(+#

This notation is genuinely strange the first time it’s encountered, so it’s worth unpacking every
piece individually, since each symbol carries real information:

• ∫ Is an elongated “S,” and that’s not decoration, it’s a historical fossil: it stands for
“sum,” a direct nod to the fact that the integral is, underneath everything, a limit of sums.

• 𝑎 and 𝑏 are the limits of integration, the left and right boundaries of the region being
measured.

• 𝑓(𝑥) Is the integrand, the function actually being integrated.

• 𝑑𝑥 represents an “infinitesimally small width,” the limiting descendant of 𝛥𝑥 once the

rectangles have become infinitely thin. It does double duty, too: it also indicates which
variable the integration is with respect to, a distinction that seems pointless right now but
becomes essential the moment more than one variable is in play, starting in Parts 2
through 4.
%
Worked example 1.1. Estimate ∫& 𝑥 % 𝑑𝑥 using a Riemann sum with 𝑛 = 4 equal subintervals
and right endpoints as sample points.
)"$ %"&
Step 1: Compute 𝛥𝑥 = '
= .
= 0.5.

Step 2: The subintervals are [0,0.5], [0.5,1], [1,1.5], [1.5,2]. With right endpoints chosen, the
sample points are the right edge of each one: 𝑥#∗ = 0.5, 𝑥%∗ = 1, 𝑥/∗ = 1.5, 𝑥.∗ = 2.

Step 3: Evaluate 𝑓(𝑥) = 𝑥 % At each sample point: 𝑓(0.5) = 0.25, 𝑓(1) = 1, 𝑓(1.5) =
2.25, 𝑓(2) = 4.

Step 4: Multiply each height by 𝛥𝑥 = 0.5 and add the results (this step is really just an
application of the distributive law, P9, factoring the common 𝛥𝑥 out of the whole sum):

𝑆. = 0.5(0.25 + 1 + 2.25 + 4) = 0.5 × 7.5 = 3.75

This is only an approximation, and not a particularly tight one at that. The true value, confirmed
0
in a moment using a shortcut, is / ≈ 2.667. The estimate of 3.75 overshoots the true value, and
that’s not a coincidence or an arithmetic slip: right endpoints on a function that’s increasing over
this interval mean every rectangle top sits above the curve rather than below it, overcounting the
area on every single subinterval. With 𝑛 = 100 rectangles instead of 4, the estimate would land
much closer to 2.667; that’s the “limit” idea described above, made concrete and numerical.
1.3 The Fundamental Theorem of Calculus: why we don’t compute
limits of sums by hand
Computing a Riemann sum limit by hand every single time an integral is needed would make
calculus a miserable, impractical subject. Fortunately that’s never necessary, thanks to the
Fundamental Theorem of Calculus. A theorem, to be precise about the word, is a statement
proven true starting from other established facts; this particular one connects integration to its
opposite operation, differentiation, and that connection is what supplies the shortcut.

Antiderivative. A function 𝐹 is called an antiderivative of 𝑓 if 𝐹 1 (𝑥) = 𝑓(𝑥) For every 𝑥 in the

interval under consideration. In plain language: differentiating 𝐹 gives back 𝑓. Differentiation
itself, from Calc 1, is taken for granted here, since it’s the prerequisite this whole guide builds
on; recall that it’s the operation finding a function’s instantaneous rate of change.

Fundamental Theorem of Calculus (Part 2, the evaluation part). If 𝐹 is any antiderivative of a

continuous function 𝑓 on [𝑎, 𝑏], then
)
B 𝑓 (𝑥) 𝑑𝑥 = 𝐹(𝑏) − 𝐹(𝑎)
$

This is usually written with the shorthand [𝐹(𝑥)])$ , read as “evaluate 𝐹 at 𝑏, then subtract 𝐹
evaluated at 𝑎.”
It’s worth pausing to let this shortcut’s power actually land, because it’s easy to read past it.
Instead of grinding through an infinite process, a limit of an ever-refining sum, only two things
are needed now: one antiderivative, and two numbers to plug in. That is an enormous reduction
in labor, and it’s the single fact that makes the rest of this guide practical rather than purely
theoretical.

Why does this work, intuitively? Picture 𝐹(𝑥) As “the accumulated area so far, measured from 𝑎
up to whatever point 𝑥 is being considered.” As 𝑥 creeps forward by some tiny amount, the
accumulated area grows by roughly (height of the curve there) × (that tiny width), and that is
exactly what a derivative measures: a rate of accumulation. So the rate at which “area so far” is
growing turns out to be nothing but the height of the function itself at that point, which is
precisely the statement 𝐹1 (𝑥) = 𝑓(𝑥). That’s the content of Part 1 of the Fundamental Theorem
(not dwelt on further here), and Part 2, stated above, is the practical half that actually produces a
number.
Antiderivative of power functions. The single most basic antiderivative rule, simply the power
rule from differentiation run in reverse, is:

'
𝑥 '2#
B 𝑥 𝑑𝑥 = + 𝐶 (𝑛 ≠ −1)
𝑛+1
That 𝐶, called the constant of integration, has to be there, and it’s worth explaining why rather
than treating it as decoration. Differentiating any constant gives 0, so reversing the process of
differentiation can never fully confirm whether some constant was quietly present in the original
function before it got differentiated away. For a definite integral, one with limits 𝑎 and 𝑏
attached, this constant cancels out automatically and never needs worrying about: 𝐹(𝑏) + 𝐶 −
(𝐹(𝑎) + 𝐶) = 𝐹(𝑏) − 𝐹(𝑎), since the two 𝐶’s subtract away by P3, the additive inverse axiom,
𝐶 + (−𝐶) = 0. That’s exactly why a lingering 𝐶 never shows up in the answer to a definite
integral, only in an indefinite integral, one without limits, which represents an entire family of
antiderivatives rather than a single number.
%
Worked example 1.2 (confirming example 1.1 exactly). Compute ∫& 𝑥 % 𝑑𝑥 exactly, rather than
approximately, and compare it to the earlier estimate.
3!
Step 1: Find an antiderivative of 𝑥 % . Using the power rule with 𝑛 = 2: ∫ 𝑥 % 𝑑𝑥 = /
+ 𝐶. Take
3!
𝐹(𝑥) = /
, dropping the 𝐶 since it’s about to cancel anyway.

% %! &! 0 0
Step 2: Apply the Fundamental Theorem: ∫& 𝑥 % 𝑑𝑥 = 𝐹(2) − 𝐹(0) = /
− /
= / − 0 = /.

This matches the approximation found above: 3.75 from only four rectangles, against a true
value of 2.667. Given how coarse that partition was, it’s a reasonably close match, and a nice
sanity check that the machinery behaves as claimed.

1.4 Substitution: undoing the chain rule

Plenty of integrands aren’t simple powers of 𝑥 sitting by themselves; they’re compositions of
functions layered inside one another, things like 𝑓(𝑥) = (3𝑥 + 1)4 Or 𝑓(𝑥) = sin(𝑥 % ) ⋅ 2𝑥. The
technique for these is called 𝑢-substitution, and it’s worth stressing that it isn’t a new,
independent trick; it is the direct algebraic reversal of the chain rule from differentiation, run
backward.
56
Recall the chain rule (from Calc 1): if 𝑦 = 𝑔(𝑢) And 𝑢 = ℎ(𝑥), then 53 = 𝑔1 (𝑢) ⋅ ℎ1 (𝑥).

Substitution simply reverses this chain. The procedure runs the same way every time:

1. Identify a piece of the integrand to call 𝑢, usually an “inner function” whose derivative
also shows up, possibly scaled by a constant, elsewhere in the integrand.

2. Compute 𝑑𝑢 = 𝑢1 (𝑥) 𝑑𝑥 (this is just notation asserting that the differential of 𝑢 equals its
derivative times 𝑑𝑥).

3. Rewrite the entire integral purely in terms of 𝑢, substituting out every remaining
occurrence of 𝑥.
 4. Integrate with respect to 𝑢, using whatever ordinary rules apply.

5. Substitute back to express the final answer in terms of 𝑥 again, since that’s the variable
the problem started with.

Worked example 1.3. Evaluate ∫ (3𝑥 + 1)4 𝑑𝑥.

Step 1: Let 𝑢 = 3𝑥 + 1, the inner function.

5! #
Step 2: Differentiate: 53 = 3, so 𝑑𝑢 = 3 𝑑𝑥. Rearranging, by multiplying both sides by /
#
(licensed by P7, since 3 has a multiplicative inverse), this becomes 𝑑𝑥 = / 𝑑𝑢.
# #
Step 3: Substitute everything in: ∫ (3𝑥 + 1)4 𝑑𝑥 = ∫ 𝑢4 ⋅ / 𝑑𝑢 = / ∫ 𝑢4 𝑑𝑢. Pulling the
#
constant / Out in front like this is licensed by P9, the distributive law, applied in reverse: a
common constant multiplier factored out of what is, underneath the integral sign, a sum-like
expression.
# # !" !"
Step 4: Integrate: / ∫ 𝑢4 𝑑𝑢 = / ⋅ 7
+ 𝐶 = #0 + 𝐶.

Step 5: Substitute back 𝑢 = 3𝑥 + 1 to land on the final answer:

(3𝑥 + 1)7
B (3𝑥 + 1)4 𝑑𝑥 = +𝐶
18
# #
Worked example 1.4 (definite integral with substitution). Evaluate ∫& 2 𝑥 𝑒 3 𝑑𝑥 (here 𝑒 is
#
Euler’s number, approximately 2.71828, and 𝑒 3 Means 𝑒 raised to the power 𝑥 % ).

Step 1: Let 𝑢 = 𝑥 % . Then 𝑑𝑢 = 2𝑥 𝑑𝑥, and something convenient shows up here: 2𝑥 𝑑𝑥 is

exactly what already appears in the integral, so there’s no leftover constant to solve for and
multiply through by, unlike in the previous example.
Step 2: Because this is a definite integral, the limits of integration need to change too, translating
them from 𝑥-values to 𝑢-values: when 𝑥 = 0, 𝑢 = 0% = 0; when 𝑥 = 1, 𝑢 = 1% = 1.

Step 3: Rewrite the integral entirely in terms of 𝑢:

# #
#
B 2 𝑥 𝑒 3 𝑑𝑥 = B 𝑒 ! 𝑑𝑢
& &

Step 4: The antiderivative of 𝑒 ! Is, famously, itself: 𝑒 ! . Applying the Fundamental Theorem:

[𝑒 ! ]#& = 𝑒 # − 𝑒 & = 𝑒 − 1
# #
So ∫& 2 𝑥 𝑒 3 𝑑𝑥 = 𝑒 − 1 ≈ 1.718.
That closes out the single-variable machinery: Riemann sums to define what an integral even
means, the Fundamental Theorem to actually evaluate one, and substitution to handle
compositions of functions when the integrand isn’t a bare power. Everything below is built
directly on top of this toolkit. Double, triple, and line integrals are all just variations on the same
underlying idea, “chop the domain into pieces, multiply by a value, sum everything up, and take
a limit,” just applied to two- or three-dimensional regions, or to curves, instead of to a single
one-dimensional interval.

1.5 A Table of Basic Antiderivatives

Before tackling more elaborate techniques, it is worth having the standard antiderivatives
collected in one place, since every technique from here on eventually reduces to recognizing one
of these forms. Each follows directly by reversing the corresponding differentiation rule from
Calc 1.

𝑥 '2# 1
∫ 𝑥 ' 𝑑𝑥 = + 𝐶 (𝑛 ≠ −1), ∫ 𝑑𝑥 = ln|𝑥| + 𝐶, ∫ 𝑒 3 𝑑𝑥 = 𝑒 3 + 𝐶
𝑛+1 𝑥
∫ sin𝑥 𝑑𝑥 = −cos𝑥 + 𝐶, ∫ cos𝑥 𝑑𝑥 = sin𝑥 + 𝐶, ∫ Sec % 𝑥 𝑑𝑥 = tan𝑥 + 𝐶

∫ Csc % 𝑥 𝑑𝑥 = −cot𝑥 + 𝐶, ∫ sec𝑥tan𝑥 𝑑𝑥 = sec𝑥 + 𝐶, ∫ csc𝑥cot𝑥 𝑑𝑥 = −csc𝑥 + 𝐶

1 1
∫ 𝑑𝑥 = arctan𝑥 + 𝐶, ∫ 𝑑𝑥 = arcsin𝑥 + 𝐶
1 + 𝑥% √1 − 𝑥 %
#
The absolute value in ∫ 3
𝑑𝑥 = ln|𝑥| + 𝐶 is not decorative: ln𝑥 alone is undefined for 𝑥 < 0,
#
but 3 Is perfectly well-defined there, so the antiderivative needs |𝑥| To be valid on both sides of
0 (differentiating ln|𝑥| Confirms this: for 𝑥 < 0, ln|𝑥| = ln(−𝑥), and by the chain rule
5 # #
53
Ln(−𝑥) = "3 ⋅ (−1) = 3, matching the integrand exactly).

1.6 Integration by Parts

Substitution reverses the chain rule; integration by parts reverses the product rule. Recall the
5
product rule from Calc 1: 53 [𝑢(𝑥)𝑣(𝑥)] = 𝑢′(𝑥)𝑣(𝑥) + 𝑢(𝑥)𝑣′(𝑥). Integrating both sides with
respect to 𝑥:

𝑢(𝑥)𝑣(𝑥) = ∫ 𝑢′(𝑥)𝑣(𝑥) 𝑑𝑥 + ∫ 𝑢(𝑥)𝑣′(𝑥) 𝑑𝑥

Rearranging (P3, moving one integral to the other side) and switching to the standard shorthand
𝑑𝑢 = 𝑢′(𝑥) 𝑑𝑥, 𝑑𝑣 = 𝑣′(𝑥) 𝑑𝑥:

∫ 𝑢 𝑑𝑣 = 𝑢𝑣 − ∫ 𝑣 𝑑𝑢
This is the integration by parts formula. It trades one integral, ∫ 𝑢 𝑑𝑣, for a different one, ∫ 𝑣 𝑑𝑢,
which is only useful when the new integral is genuinely easier than the original. Choosing which
factor of the integrand to call 𝑢 and which to call 𝑑𝑣 is the entire skill of the technique; a
common mnemonic for what to choose as 𝑢, in order of priority, is LIATE: Logarithmic, Inverse
trigonometric, Algebraic (polynomial), Trigonometric, Exponential, whichever type appears first
in this list is generally the better choice for 𝑢, since it tends to simplify (or stay the same
complexity) upon differentiation, while the remaining factor, chosen as 𝑑𝑣, needs to be readily
integrable.

Worked example 1.5. Evaluate ∫ 𝑥 𝑒 3 𝑑𝑥.

Step 1: By LIATE, the polynomial factor 𝑥 (Algebraic) outranks the exponential 𝑒 3 , so let 𝑢 = 𝑥
and 𝑑𝑣 = 𝑒 3 𝑑𝑥.

Step 2: Compute 𝑑𝑢 and 𝑣: 𝑑𝑢 = 𝑑𝑥 (differentiating 𝑢 = 𝑥), and 𝑣 = ∫ 𝑒 3 𝑑𝑥 = 𝑒 3 (integrating

𝑑𝑣; the constant of integration can be dropped here since it will not affect the final answer, it
would simply cancel out later).

Step 3: Apply the formula: ∫ 𝑥 𝑒 3 𝑑𝑥 = 𝑢𝑣 − ∫ 𝑣 𝑑𝑢 = 𝑥𝑒 3 − ∫ 𝑒 3 𝑑𝑥.

Step 4: Integrate the remaining piece: ∫ 𝑒 3 𝑑𝑥 = 𝑒 3 + 𝐶.

∫ 𝑥 𝑒 3 𝑑𝑥 = 𝑥𝑒 3 − 𝑒 3 + 𝐶

Worked example 1.6 (repeated application). Evaluate ∫ 𝑥 % 𝑒 3 𝑑𝑥.

Step 1: Let 𝑢 = 𝑥 % , 𝑑𝑣 = 𝑒 3 𝑑𝑥, so 𝑑𝑢 = 2𝑥 𝑑𝑥, 𝑣 = 𝑒 3 .

Step 2: ∫ 𝑥 % 𝑒 3 𝑑𝑥 = 𝑥 % 𝑒 3 − ∫ 𝑒 3 (2𝑥) 𝑑𝑥 = 𝑥 % 𝑒 3 − 2∫ 𝑥𝑒 3 𝑑𝑥.

Step 3: The remaining integral ∫ 𝑥𝑒 3 𝑑𝑥 is exactly Worked example 1.5, already known to equal
𝑥𝑒 3 − 𝑒 3 + 𝐶. Substituting:

∫ 𝑥 % 𝑒 3 𝑑𝑥 = 𝑥 % 𝑒 3 − 2(𝑥𝑒 3 − 𝑒 3 ) + 𝐶 = 𝑥 % 𝑒 3 − 2𝑥𝑒 3 + 2𝑒 3 + 𝐶

This illustrates a common pattern: integration by parts sometimes needs to be applied more than
once, each application knocking the power of the polynomial factor down by one, until it is
reduced to a constant.

Worked example 1.7 (the “solve for the integral” trick). Evaluate ∫ 𝑒 3 Sin𝑥 𝑑𝑥.

Step 1: Let 𝑢 = sin𝑥, 𝑑𝑣 = 𝑒 3 𝑑𝑥, so 𝑑𝑢 = cos𝑥 𝑑𝑥, 𝑣 = 𝑒 3 .

∫ 𝑒 3 Sin𝑥 𝑑𝑥 = 𝑒 3 Sin𝑥 − ∫ 𝑒 3 Cos𝑥 𝑑𝑥

Step 2: The new integral ∫ 𝑒 3 Cos𝑥 𝑑𝑥 still needs parts. Let 𝑢 = cos𝑥, 𝑑𝑣 = 𝑒 3 𝑑𝑥, so 𝑑𝑢 =
−sin𝑥 𝑑𝑥, 𝑣 = 𝑒 3 .
 ∫ 𝑒 3 Cos𝑥 𝑑𝑥 = 𝑒 3 Cos𝑥 − ∫ 𝑒 3 (−sin𝑥) 𝑑𝑥 = 𝑒 3 Cos𝑥 + ∫ 𝑒 3 Sin𝑥 𝑑𝑥

Step 3: Substitute this back into the Step 1 result. Writing 𝐼 = ∫ 𝑒 3 Sin𝑥 𝑑𝑥 for brevity:

𝐼 = 𝑒 3 Sin𝑥 − (𝑒 3 Cos𝑥 + 𝐼) = 𝑒 3 Sin𝑥 − 𝑒 3 Cos𝑥 − 𝐼

Step 4: The unknown integral 𝐼 now appears on both sides of the equation, so it can be solved for
algebraically, exactly like an ordinary linear equation. Adding 𝐼 to both sides (P1):

2𝐼 = 𝑒 3 Sin𝑥 − 𝑒 3 Cos𝑥

Dividing both sides by 2 (P7):

𝑒 3 (Sin𝑥 − cos𝑥)
𝐼 = ∫ 𝑒 3 Sin𝑥 𝑑𝑥 = +𝐶
2
This “solve for the integral algebraically” move is a standard trick whenever integration by parts,
applied twice, returns to the original integral rather than eliminating it.
)
Definite integrals by parts. The formula carries over directly with limits attached: ∫$ 𝑢 𝑑𝑣 =
)
[𝑢𝑣])$ − ∫$ 𝑣 𝑑𝑢.

1.7 Trigonometric Integrals

This section develops systematic strategies for integrals built from powers and products of
trigonometric functions, which cannot generally be handled by substitution or parts alone
without a preliminary rewriting step.

Case ∫ Sin8 𝑥Cos' 𝑥 𝑑𝑥, with 𝑚 or 𝑛 odd. Peel off a single copy of the odd-powered function,
convert the remaining even power of that same function into the other function using the
Pythagorean identity Sin% 𝑥 + Cos% 𝑥 = 1, and substitute 𝑢 equal to the other function.

Worked example 1.8. Evaluate ∫ Sin/ 𝑥 Cos% 𝑥 𝑑𝑥 (𝑚 = 3 is odd).

Step 1: Peel off one factor of sin𝑥 to save for the substitution differential, and rewrite the
remaining even power Sin% 𝑥 using Sin% 𝑥 = 1 − Cos% 𝑥:

∫ Sin/ 𝑥Cos% 𝑥 𝑑𝑥 = ∫ Sin% 𝑥Cos% 𝑥 ⋅ sin𝑥 𝑑𝑥 = ∫ (1 − Cos % 𝑥)Cos% 𝑥sin𝑥 𝑑𝑥

Step 2: Let 𝑢 = cos𝑥, so 𝑑𝑢 = −sin𝑥 𝑑𝑥, i.e., sin𝑥 𝑑𝑥 = −𝑑𝑢:

∫ (1 − 𝑢% )𝑢% (−𝑑𝑢) = −∫ (𝑢% − 𝑢. ) 𝑑𝑢

!! !$ !! !$
Step 3: Integrate term by term: − i / − 4
j+𝐶 =− /
+ 4
+ 𝐶.

Step 4: Substitute back 𝑢 = cos𝑥:

 / %
Cos 4 𝑥 Cos / 𝑥
∫ Sin 𝑥Cos 𝑥 𝑑𝑥 = − +𝐶
5 3
Case ∫ Sin8 𝑥Cos' 𝑥 𝑑𝑥, with 𝑚 and 𝑛 both even. Use the power-reduction identities Sin% 𝑥 =
#"9:;%3 #29:;%3
%
And Cos% 𝑥 = %
To rewrite everything at half the original power (at double the
angle), repeating as needed until all powers are odd or reduced to degree 1.

Worked example 1.9. Evaluate ∫ Sin% 𝑥 𝑑𝑥.

#"9:;%3
Step 1: Apply the power-reduction identity directly: Sin% 𝑥 = %
.

Step 2: Integrate term by term:

1 − cos2𝑥 1 1 𝑥 1 Sin2𝑥 𝑥 Sin2𝑥
∫ 𝑑𝑥 = ∫ 1 𝑑𝑥 − ∫ cos2𝑥 𝑑𝑥 = − ⋅ +𝐶 = − +𝐶
2 2 2 2 2 2 2 4
(the second integral used substitution with 𝑢 = 2𝑥, a routine application of Section 1.4).

Case ∫ Tan8 𝑥Sec ' 𝑥 𝑑𝑥. Two sub-strategies, chosen depending on which power is more
convenient: if 𝑛 (the secant power) is even, peel off Sec % 𝑥 and convert the rest to tangent via
Sec % 𝑥 = 1 + Tan% 𝑥, then substitute 𝑢 = tan𝑥; if 𝑚 (the tangent power) is odd, peel off one
factor of sec𝑥tan𝑥 and convert the rest to secant via Tan% 𝑥 = Sec % 𝑥 − 1, then substitute 𝑢 =
sec𝑥.

Worked example 1.10. Evaluate ∫ Tan/ 𝑥Sec % 𝑥 𝑑𝑥 (𝑛 = 2 is even).

Step 1: Since the secant power is even, peel off Sec % 𝑥 𝑑𝑥 directly as the substitution differential,
leaving the tangent power untouched (no identity conversion needed, since a full Sec % 𝑥 is
exactly what is needed to form 𝑑𝑢).

Step 2: Let 𝑢 = tan𝑥, so 𝑑𝑢 = Sec % 𝑥 𝑑𝑥:

𝑢.
∫ Tan/ 𝑥Sec % 𝑥 𝑑𝑥 = ∫ 𝑢/ 𝑑𝑢 = +𝐶
4
Step 3: Substitute back:

/ %
Tan. 𝑥
∫ Tan 𝑥Sec 𝑥 𝑑𝑥 = +𝐶
4

1.8 Trigonometric Substitution

Trigonometric substitution handles integrands containing √𝑎% − 𝑥 % , √𝑎% + 𝑥 % , or √𝑥 % − 𝑎% (for
some constant 𝑎 > 0), forms that ordinary substitution cannot simplify, by replacing 𝑥 with a
trigonometric function of a new variable 𝜃, chosen specifically to make the square root collapse
via a Pythagorean identity.
 • For √𝑎% − 𝑥 % : let 𝑥 = 𝑎sin𝜃, so 𝑎% − 𝑥 % = 𝑎% − 𝑎% Sin% 𝜃 = 𝑎% (1 − Sin% 𝜃) = 𝑎% Cos% 𝜃,
and √𝑎% − 𝑥 % = 𝑎cos𝜃 (dropping the absolute value by restricting 𝜃 to an interval,
< <
typically − % ≤ 𝜃 ≤ % , where cos𝜃 ≥ 0).

• For √𝑎% + 𝑥 % : let 𝑥 = 𝑎tan𝜃, so 𝑎% + 𝑥 % = 𝑎% (1 + Tan% 𝜃) = 𝑎% Sec % 𝜃, and

√𝑎% + 𝑥 % = 𝑎sec𝜃.

• For √𝑥 % − 𝑎% : let 𝑥 = 𝑎sec𝜃, so 𝑥 % − 𝑎% = 𝑎% (Sec % 𝜃 − 1) = 𝑎% Tan% 𝜃, and

√𝑥 % − 𝑎% = 𝑎tan𝜃.

In every case, once the integral has been fully rewritten in terms of 𝜃 and evaluated, the final
step (back-substitution) requires expressing the answer in terms of 𝑥 again; this is most cleanly
done by drawing a right triangle labeled according to the substitution equation, and reading the
needed trigonometric ratio directly off its sides.
53
Worked example 1.11. Evaluate ∫ √."3 #
.

Step 1: Match the form √𝑎% − 𝑥 % With 𝑎 = 2. Let 𝑥 = 2sin𝜃, so 𝑑𝑥 = 2cos𝜃 𝑑𝜃, and
√4 − 𝑥 % = 2cos𝜃 (per the identity above).

Step 2: Substitute:
2cos𝜃 𝑑𝜃
∫ = ∫ 1 𝑑𝜃 = 𝜃 + 𝐶
2cos𝜃
3 3
Step 3: Back-substitute. From 𝑥 = 2sin𝜃, sin𝜃 = %, so 𝜃 = arcsin i%j.

𝑑𝑥 𝑥
∫ = arcsin i j + 𝐶
√4 − 𝑥 % 2
√3 # ">
Worked example 1.12 (using the reference triangle). Evaluate ∫ 3
𝑑𝑥 (𝑥 > 3).

Step 1: Match √𝑥 % − 𝑎% With 𝑎 = 3. Let 𝑥 = 3sec𝜃, so 𝑑𝑥 = 3sec𝜃tan𝜃 𝑑𝜃, and √𝑥 % − 9 =

3tan𝜃.

Step 2: Substitute:
3tan𝜃
∫ ⋅ 3sec𝜃tan𝜃 𝑑𝜃 = ∫ 3Tan% 𝜃 𝑑𝜃
3sec𝜃
Step 3: Use the identity Tan% 𝜃 = Sec % 𝜃 − 1 (a rearrangement of Sec % 𝜃 = 1 + Tan% 𝜃, via P3):

3∫ (Sec % 𝜃 − 1) 𝑑𝜃 = 3(Tan𝜃 − 𝜃) + 𝐶
 3
Step 4: Back-substitute using a reference triangle: since sec𝜃 = , draw a right triangle with
/
hypotenuse 𝑥, adjacent side 3, and (by the Pythagorean theorem) opposite side √𝑥 % − 9. Reading
Opposite √3 # "> 3
off the triangle, tan𝜃 = Adjacent = /
, and 𝜃 = arcsec i/j.

√𝑥 % − 9 √𝑥 % − 9 𝑥 𝑥
∫ 𝑑𝑥 = 3 q r − 3 arcsec i j + 𝐶 = s𝑥 % − 9 − 3 arcsec i j + 𝐶
𝑥 3 3 3

1.9 Partial Fractions

Partial fraction decomposition rewrites a rational function (a ratio of polynomials) as a sum of
simpler fractions, each of which is directly integrable by the basic rules of Section 1.5. It applies
?(3)
to a proper rational function B(3) (degree of 𝑃 strictly less than degree of 𝑄; if not proper,
polynomial long division is performed first to reduce it to a polynomial plus a proper remainder).

Case: distinct linear factors. If 𝑄(𝑥) Factors into distinct linear factors (𝑥 − 𝑟# )(𝑥 − 𝑟% ) ⋯ (𝑥 −
𝑟C ), write:
𝑃(𝑥) 𝐴# 𝐴% 𝐴C
= + + ⋯+
𝑄(𝑥) 𝑥 − 𝑟# 𝑥 − 𝑟% 𝑥 − 𝑟C

For constants 𝐴# , … , 𝐴C To be determined.

/324
Worked example 1.13. Evaluate ∫ 3 # "#
𝑑𝑥.

Step 1: Factor the denominator: 𝑥 % − 1 = (𝑥 − 1)(𝑥 + 1) (distinct linear factors), so set up:
3𝑥 + 5 𝐴 𝐵
= +
(𝑥 − 1)(𝑥 + 1) 𝑥 − 1 𝑥 + 1

Step 2: Multiply both sides by (𝑥 − 1)(𝑥 + 1) To clear denominators:

3𝑥 + 5 = 𝐴(𝑥 + 1) + 𝐵(𝑥 − 1)

Step 3: Solve for 𝐴, 𝐵 using strategic 𝑥-values. Setting 𝑥 = 1: 3(1) + 5 = 𝐴(2) + 𝐵(0) ⇒ 8 =
2𝐴 ⇒ 𝐴 = 4. Setting 𝑥 = −1: 3(−1) + 5 = 𝐴(0) + 𝐵(−2) ⇒ 2 = −2𝐵 ⇒ 𝐵 = −1.

Step 4: Rewrite and integrate each piece separately:

4 1
∫z − { 𝑑𝑥 = 4ln|𝑥 − 1| − ln|𝑥 + 1| + 𝐶
𝑥−1 𝑥+1
D D
Case: repeated linear factors. A factor (𝑥 − 𝑟)8 Contributes 𝑚 separate terms: 3"E
% #
+ (3"E) #
+
D
&
⋯ + (3"E) &
, one for each power from 1 up to 𝑚.
Case: irreducible quadratic factors. A quadratic factor 𝑎𝑥 % + 𝑏𝑥 + 𝑐 that cannot be factored
F32G
further over the reals (discriminant 𝑏 % − 4𝑎𝑐 < 0) contributes a term of the form $3 # 2)32H
D
(linear numerator, since the quadratic denominator alone cannot be handled by the simple …
Form used for linear factors).
%3 # 2#
Worked example 1.14 (irreducible quadratic factor). Evaluate ∫ 3 ! 23
𝑑𝑥.

Step 1: Factor the denominator: 𝑥 / + 𝑥 = 𝑥(𝑥 % + 1), where 𝑥 % + 1 is irreducible (its

discriminant is 0 − 4(1)(1) = −4 < 0). Set up:

2𝑥 % + 1 𝐴 𝐵𝑥 + 𝐶
%
= + %
𝑥(𝑥 + 1) 𝑥 𝑥 + 1
Step 2: Clear denominators: 2𝑥 % + 1 = 𝐴(𝑥 % + 1) + (𝐵𝑥 + 𝐶)(𝑥).

Step 3: Setting 𝑥 = 0: 1 = 𝐴(1) + 0 ⇒ 𝐴 = 1. Expanding the rest and matching coefficients of

𝑥 % : 2 = 𝐴 + 𝐵 ⇒ 𝐵 = 2 − 1 = 1. Matching coefficients of 𝑥 # : 0 = 𝐶 (there is no bare-𝑥 term
on the left side).
Step 4: Rewrite and integrate:
1 𝑥 1
∫z + % { 𝑑𝑥 = ln|𝑥| + Ln(𝑥 % + 1) + 𝐶
𝑥 𝑥 +1 2
(the second piece used substitution with 𝑢 = 𝑥 % + 1, per Section 1.4).

1.10 Improper Integrals

)
An integral ∫$ 𝑓 (𝑥) 𝑑𝑥 is improper if either the interval of integration is infinite (one or both
limits are ±∞), or the integrand becomes unbounded (blows up to ±∞) somewhere on [𝑎, 𝑏].
Both cases are handled the same way in principle: replace the problematic boundary with a
variable, evaluate the resulting ordinary (proper) integral, and take a limit as that variable
approaches the true boundary.
Type 1: infinite limits of integration.
- J
B 𝑓 (𝑥) 𝑑𝑥 = Lim B 𝑓 (𝑥) 𝑑𝑥
$ J→- $

If this limit exists (is a finite number), the improper integral converges to that value. If the limit
is ±∞ or fails to exist, the improper integral diverges.
- #
Worked example 1.15. Evaluate ∫# 3#
𝑑𝑥.
- # J
Step 1: Rewrite as a limit: ∫# 3#
𝑑𝑥 = LimJ→- ∫# 𝑥 "% 𝑑𝑥.
 J #
Step 2: Evaluate the proper integral using the power rule: ∫# 𝑥 "% 𝑑𝑥 = [−𝑥 "# ]#J = − J −
# #
i− #j = 1 − J .

# #
Step 3: Take the limit: LimJ→- i1 − J j = 1 − 0 = 1 (since J → 0 as 𝑡 → ∞).

Since the limit exists and equals 1, the improper integral converges to 1.
-#
Worked example 1.16 (a divergent case, for contrast). Evaluate ∫# 3
𝑑𝑥.
-# J#
Step 1: ∫# 3
𝑑𝑥 = LimJ→- ∫# 3 𝑑𝑥 = LimJ→- [Ln|𝑥|]#J = LimJ→- (Ln𝑡 − ln1) = LimJ→- Ln𝑡.

Step 2: Since ln𝑡 → ∞ as 𝑡 → ∞, the limit does not exist as a finite number. The improper
integral diverges.
# # - #
This pair of examples (3# Converging, 3 Diverging) illustrates the general p-test: ∫# 3'
𝑑𝑥
converges if 𝑝 > 1 and diverges if 𝑝 ≤ 1, a fact provable by running the identical limit
computation with a general exponent 𝑝 in place of the specific values 2 and 1 used above.

Type 2: discontinuous integrand. If 𝑓 is unbounded at an endpoint, say at 𝑥 = 𝑏, then:

) J
B 𝑓 (𝑥) 𝑑𝑥 = Lim( B 𝑓 (𝑥) 𝑑𝑥
$ J→) $

(approaching 𝑏 from the left, since 𝑏 itself cannot be plugged in directly). An analogous one-
sided limit from the right handles a discontinuity at the left endpoint 𝑥 = 𝑎, and a discontinuity
in the interior of [𝑎, 𝑏] Is handled by splitting the integral into two pieces at that point and
applying the appropriate one-sided limit to each piece separately.
# #
Worked example 1.17. Evaluate ∫& 𝑑𝑥 (the integrand blows up at 𝑥 = 0).
√3

# #
Step 1: Rewrite as a limit: ∫& 𝑥 "#/% 𝑑𝑥 = LimJ→&) ∫J 𝑥 "#/% 𝑑𝑥.
# #
Step 2: Evaluate: ∫J 𝑥 "#/% 𝑑𝑥 = •2𝑥#/% €J = 2√1 − 2√𝑡 = 2 − 2√𝑡.

Step 3: Take the limit: LimJ→&) •2 − 2√𝑡‚ = 2 − 0 = 2 (since √𝑡 → 0 as 𝑡 → 02 ).

Since the limit exists, the improper integral converges to 2, even though the integrand itself
grows without bound near 𝑥 = 0, the area underneath it still comes out finite, a genuinely non-
obvious fact that the limit definition makes rigorous.
That completes the single-variable toolkit: Riemann sums to define what an integral even means,
the Fundamental Theorem to evaluate one, substitution and integration by parts to handle
compositions and products, trigonometric integrals and trigonometric substitution for the specific
families of integrands those methods are built for, partial fractions for rational functions, and
improper integrals for infinite domains or unbounded integrands. Everything below is built
directly on top of this toolkit. Double, triple, and line integrals are all variations on the same
underlying idea, chop the domain into pieces, multiply by a value, sum everything up, and take a
limit, just applied to two- or three-dimensional regions, or to curves, instead of to a single one-
dimensional interval, and every one of them will, sooner or later, require evaluating an ordinary
single-variable integral using exactly the techniques developed here.

PART 2: Double Integrals

2.1 What problem does the double integral solve?
Suppose now that 𝑓(𝑥, 𝑦) Is a function of two variables: it takes in a pair of numbers (𝑥, 𝑦), a
point in the flat, two-dimensional plane, and returns a single number 𝑓(𝑥, 𝑦). It helps to picture
the graph of 𝑧 = 𝑓(𝑥, 𝑦) As a surface floating above the 𝑥𝑦-plane, where 𝑧 is the output, or
height, value at each point of that plane.

Given a region 𝑅, some two-dimensional patch, perhaps a rectangle, perhaps a more irregular
blob, sitting in the 𝑥𝑦-plane, the double integral answers a natural three-dimensional question:
what is the exact volume trapped between the surface 𝑧 = 𝑓(𝑥, 𝑦) And the flat region 𝑅 directly
below it?
That question is the direct generalization of “area under a curve” to “volume under a surface,”
and the strategy for answering it, unsurprisingly, is going to look extremely familiar: chop,
approximate, refine, and take a limit, exactly the plan from Part 1, just now carried out in two
dimensions instead of one.

2.2 Double Riemann sums

The construction mirrors Part 1 almost exactly, and it’s worth noticing just how little actually
changes; the extra dimension adds bookkeeping, not new ideas.

Partitioning a region. Suppose 𝑅 is the rectangle [𝑎, 𝑏] × [𝑐, 𝑑], meaning 𝑥 ranges over [𝑎, 𝑏]
)"$
and, independently, 𝑦 ranges over [𝑐, 𝑑]. Chop [𝑎, 𝑏] into 𝑚 equal pieces of width 𝛥𝑥 = 8
, and
5"H
chop [𝑐, 𝑑] into 𝑛 equal pieces of height 𝛥𝑦 = '
. Together these two sets of cuts lay a grid of
𝑚 × 𝑛 small rectangles over 𝑅, each one with area 𝛥𝐴 = 𝛥𝑥 𝛥𝑦.

Sample point and Riemann sum. In each small rectangle, pick a sample point •𝑥(L∗ , 𝑦(L∗ ‚, where
the double subscript 𝑖𝑗 is just a label for which grid cell is being described, the 𝑖-th column and 𝑗-
th row. Build a thin rectangular box over each grid cell, with height 𝑓•𝑥(L∗ , 𝑦(L∗ ‚ And base area 𝛥𝐴.
Adding up the volume of every box in the grid gives the double Riemann sum:
 8 '
∗
𝑆8' = = = 𝑓 •𝑥(L , 𝑦(L∗ ‚ 𝛥𝐴
(+# L+#

The double integral. As 𝑚, 𝑛 → ∞, meaning the grid becomes infinitely fine in both directions at
once, this sum approaches a limiting value:
8 '
∗
† 𝑓 (𝑥, 𝑦) 𝑑𝐴 = Lim = = 𝑓 •𝑥(L , 𝑦(L∗ ‚ 𝛥𝐴
M 8,'→-
(+# L+#

The double integral symbol ∬ Is literally two integral signs stacked side by side, a visual
reminder that summing is happening over two dimensions at once rather than one. And 𝑑𝐴 stands
for “differential of area,” the infinitely small piece of area that 𝛥𝐴 shrinks down to in the limit,
playing exactly the role that 𝑑𝑥 played back in Part 1.

2.3 Fubini’s Theorem: turning a double integral into two single integrals
Computing that double limit directly, cell by cell, would be far worse than the single-variable
case ever was. Fubini’s Theorem rescues the situation: if 𝑓 is continuous on the rectangle 𝑅 =
[𝑎, 𝑏] × [𝑐, 𝑑], the double integral can be computed as an iterated integral, meaning the two
single-variable integrals get done one after another, treating whichever variable isn’t currently
being integrated as a fixed constant:
) 5 5 )
† 𝑓 (𝑥, 𝑦) 𝑑𝐴 = B qB 𝑓 (𝑥, 𝑦) 𝑑𝑦r 𝑑𝑥 = B qB 𝑓 (𝑥, 𝑦) 𝑑𝑥r 𝑑𝑦
M $ H H $

Both orders give the same final answer whenever 𝑓 is continuous over a rectangle; that
equivalence of orders is exactly the content of the theorem, and it’s a genuinely convenient fact,
since it means either order can be chosen based on whichever is algebraically easier for a given
integrand. The one mechanical skill that has to be internalized here is short but essential: when
integrating with respect to one variable, treat the other variable as if it were just a constant
number, exactly the way any ordinary constant got treated back in Part 1.

Worked example 2.1. Evaluate ∬M (𝑥 % 𝑦 + 𝑦) 𝑑𝐴 where 𝑅 = [0,2] × [0,1], so 𝑥 ranges from 0 to

2 and 𝑦 ranges from 0 to 1.

Step 1, the inner integral, with respect to 𝑦, treating 𝑥 as a constant:

#
B (𝑥 % 𝑦 + 𝑦) 𝑑𝑦
&

Since 𝑥 % Is being treated as fixed while the integration proceeds in 𝑦, it helps to factor it out
using P9, the distributive law, or simply integrate term by term:
 # # # #
𝑦% 𝑦% 1 1 𝑥% 1
B 𝑥 𝑦 𝑑𝑦 + B 𝑦 𝑑𝑦 = 𝑥 ˆ ‰ + ˆ ‰ = 𝑥 % z { + =
% %
+
& & 2 & 2 & 2 2 2 2

Step 2, the outer integral, with respect to 𝑥, using the Step 1 result as the new integrand:
% %
𝑥% 1 𝑥/ 𝑥 8 2 4 7
B q + r 𝑑𝑥 = ˆ + ‰ = z + { − (0) = + 1 =
& 2 2 6 2& 6 2 3 3
O
So ∬M (𝑥 % 𝑦 + 𝑦) 𝑑𝐴 = /.

2.4 Double integrals over general (non-rectangular) regions

Often the region 𝑅 isn’t a clean rectangle at all; it might instead be the area trapped between two
curves, an altogether more common situation in practice than the tidy rectangle used above.
There are two standard shapes worth knowing by name, since recognizing which one applies is
most of the battle in setting a problem up correctly:

Type I region: bounded left and right by vertical constants 𝑥 = 𝑎 and 𝑥 = 𝑏, and bounded top
and bottom by functions of 𝑥: 𝑔# (𝑥) ≤ 𝑦 ≤ 𝑔% (𝑥). For a region shaped like this, the integration
order matters: 𝑦 gets integrated first, on the inside, and 𝑥 second, on the outside:
) P# (3)
† 𝑓 (𝑥, 𝑦) 𝑑𝐴 = B B 𝑓 (𝑥, 𝑦) 𝑑𝑦 𝑑𝑥
M $ P% (3)

Type II region: bounded top and bottom by horizontal constants 𝑦 = 𝑐 and 𝑦 = 𝑑, and bounded
left and right by functions of 𝑦: ℎ# (𝑦) ≤ 𝑥 ≤ ℎ% (𝑦). Here the order flips: 𝑥 gets integrated first,
then 𝑦:
5 Q# (6)
† 𝑓 (𝑥, 𝑦) 𝑑𝐴 = B B 𝑓 (𝑥, 𝑦) 𝑑𝑥 𝑑𝑦
M H Q%(6)

The core idea worth holding onto through both cases is this: the bounds of the inner integral are
allowed to depend on the outer variable, since that variable’s value hasn’t been fixed yet at the
inner stage, whereas the bounds of the outer integral must be plain constants, because by the time
the outer integral is being evaluated, the inner variable has already been integrated away and no
longer exists in the expression.

Worked example 2.2. Evaluate ∬M 𝑥 𝑦 𝑑𝐴 where 𝑅 is the region bounded below by 𝑦 = 𝑥 % And
above by 𝑦 = 𝑥, for 𝑥 between 0 and 1, a Type I region, since it’s naturally described by 𝑥 % ≤
𝑦 ≤ 𝑥 over a fixed range of 𝑥.

First, check that these two curves actually bound a sensible region: at 𝑥 = 0, both give 𝑦 = 0; at
𝑥 = 1, both give 𝑦 = 1; and for 0 < 𝑥 < 1, it’s always true that 𝑥 > 𝑥 % (checking, say, 𝑥 = 0.5:
𝑥 = 0.5 against 𝑥 % = 0.25 confirms this), so 𝑦 = 𝑥 is indeed the upper curve and 𝑦 = 𝑥 % The
lower curve across this whole interval.

Step 1, the inner integral, with respect to 𝑦, running from 𝑦 = 𝑥 % Up to 𝑦 = 𝑥, treating 𝑥 as a

constant:
3 3
𝑦% 𝑥 % 𝑥. 𝑥/ 𝑥 4
B 𝑥 𝑦 𝑑𝑦 = 𝑥 ˆ ‰ = 𝑥 q − r = −
3# 2 3# 2 2 2 2

(That last step distributes 𝑥 across the difference, another use of P9.)

Step 2, the outer integral, with respect to 𝑥, from 0 to 1:

# #
𝑥/ 𝑥 4 𝑥. 𝑥7 1 1
B q − r 𝑑𝑥 = ˆ − ‰ = −
& 2 2 8 12 & 8 12
# / # %
Subtracting these fractions requires a common denominator of 24 (rewriting 0 = %. And #% = %.
C
Uses P8 and P9, since multiplying a fraction by C = 1, itself an application of P6 and P7, never
changes its value):
3 2 1
− =
24 24 24
#
So ∬M 𝑥 𝑦 𝑑𝐴 = %..

2.5 Double integrals in polar coordinates

Sometimes a region is naturally circular, a disk, a ring, a pie-slice, and describing its boundaries
in terms of 𝑥 and 𝑦 becomes clumsy fast. Polar coordinates describe a point instead by its
distance 𝑟 from the origin and its angle 𝜃, measured counterclockwise from the positive 𝑥-axis,
using the conversion:

𝑥 = 𝑟cos𝜃, 𝑦 = 𝑟sin𝜃
There is one crucial fact that cannot be skipped or approximated here: the area element changes
when switching to polar coordinates. It is emphatically not true that 𝑑𝐴 = 𝑑𝑟 𝑑𝜃; a shockingly
common error worth flagging before it happens. Instead:

𝑑𝐴 = 𝑟 𝑑𝑟 𝑑𝜃

Why the extra factor of 𝑟? A tiny “polar rectangle,” spanning a small change 𝑑𝑟 in radius and a
small change 𝑑𝜃 in angle, is not actually a true rectangle at all; it’s closer to a thin curved wedge.
Its two dimensions are 𝑑𝑟, the radial thickness, and 𝑟 𝑑𝜃, the arc length along the circle of radius
𝑟 (arc length equals radius times angle, when the angle is measured in radians). So its area works
out to (radial thickness) × (arc length) = 𝑑𝑟 × 𝑟 𝑑𝜃 = 𝑟 𝑑𝑟 𝑑𝜃. Forgetting this extra factor of 𝑟
is one of the single most common errors students make in this entire topic, and it’s worth
committing to memory right now, before it becomes a habit to unlearn later.

Worked example 2.3. Evaluate ∬M (𝑥 % + 𝑦 % ) 𝑑𝐴 where 𝑅 is the disk of radius 2 centered at the
origin.

Step 1: Convert the integrand. Since 𝑥 = 𝑟cos𝜃 and 𝑦 = 𝑟sin𝜃:

𝑥 % + 𝑦 % = 𝑟 % Cos% 𝜃 + 𝑟 % Sin% 𝜃 = 𝑟 % (Cos% 𝜃 + Sin% 𝜃) = 𝑟 % ⋅ 1 = 𝑟 %

(This uses the trigonometric identity Cos% 𝜃 + Sin% 𝜃 = 1, together with P9 to factor 𝑟 % Out in
the middle step.)

Step 2: Set up the region’s bounds. A full disk of radius 2 means 𝑟 ranges from 0 to 2, while 𝜃
ranges all the way around, from 0 to 2𝜋, a full circle measured in radians.

Step 3: Assemble the iterated integral, remembering the crucial extra factor of 𝑟 from 𝑑𝐴 =
𝑟 𝑑𝑟 𝑑𝜃:
%< % %< %
† (𝑥 % + 𝑦 % ) 𝑑𝐴 = B B 𝑟 % ⋅ 𝑟 𝑑𝑟 𝑑𝜃 = B B 𝑟 / 𝑑𝑟 𝑑𝜃
M & & & &

Step 4, the inner integral, with respect to 𝑟:

% %
/
𝑟. 16
B 𝑟 𝑑𝑟 = ˆ ‰ = =4
& 4 & 4

Step 5, the outer integral, with respect to 𝜃 (here 4 is a constant with respect to 𝜃, so it factors
straight out by P9):
%<
B 4 𝑑𝜃 = 4[𝜃]%<
& = 4(2𝜋 − 0) = 8𝜋
&

So ∬M (𝑥 % + 𝑦 % ) 𝑑𝐴 = 8𝜋.

PART 3: Triple Integrals

3.1 What problem does the triple integral solve?
Extend the pattern once more: let 𝑓(𝑥, 𝑦, 𝑧) Be a function of three variables, and let 𝐸 be some
solid region sitting in three-dimensional space. The triple integral computes quantities like the
total mass of a solid object 𝐸, when 𝑓(𝑥, 𝑦, 𝑧) Represents its density, that is, its mass per unit
volume, at each point inside it. More abstractly, it’s simply the natural three-dimensional
generalization of “sum a quantity over a region,” continuing the exact same progression that took
the single integral up to the double integral:
 ‹ 𝑓 (𝑥, 𝑦, 𝑧) 𝑑𝑉
R

Here 𝑑𝑉 is the differential of volume, the limit of a tiny three-dimensional box’s volume 𝛥𝑉 =
𝛥𝑥 𝛥𝑦 𝛥𝑧 as all three of its dimensions shrink toward zero at once. The construction follows
exactly the same pattern established twice already: chop the solid 𝐸 into a fine three-dimensional
grid of tiny boxes, evaluate 𝑓 at a sample point inside each box, multiply by that box’s tiny
volume, sum everything across the whole grid, and take the limit as the grid becomes infinitely
fine.

3.2 Evaluating triple integrals as iterated integrals

Just as with double integrals, evaluation proceeds by peeling off one variable at a time, working
from the innermost integral outward, treating every variable not yet integrated as a fixed
constant. If 𝐸 is described by

𝑎 ≤ 𝑥 ≤ 𝑏, 𝑔# (𝑥) ≤ 𝑦 ≤ 𝑔% (𝑥), ℎ# (𝑥, 𝑦) ≤ 𝑧 ≤ ℎ% (𝑥, 𝑦)

Meaning 𝑥’s bounds are plain numbers, 𝑦’s bounds may depend on 𝑥, and 𝑧’s bounds may
depend on both 𝑥 and 𝑦 (since 𝑧 is integrated first, innermost, its bounds are allowed to depend
on both variables not yet resolved at that stage), then:
) P# (3) Q# (3,6)
‹𝑓 (𝑥, 𝑦, 𝑧) 𝑑𝑉 = B B B 𝑓 (𝑥, 𝑦, 𝑧) 𝑑𝑧 𝑑𝑦 𝑑𝑥
R $ P% (3) Q% (3,6)

Worked example 3.1. Evaluate ∭R 2 𝑥 𝑑𝑉 where 𝐸 is the solid region satisfying 0 ≤ 𝑥 ≤ 1, 0 ≤

𝑦 ≤ 𝑥, 0 ≤ 𝑧 ≤ 𝑥 + 𝑦.

Step 1, the innermost integral, with respect to 𝑧, from 0 to 𝑥 + 𝑦, treating 𝑥, 𝑦 as constants:

326
B 2 𝑥 𝑑𝑧 = 2𝑥[𝑧]&326 = 2𝑥(𝑥 + 𝑦) = 2𝑥 % + 2𝑥𝑦
&

(this last step distributes 2𝑥 across (𝑥 + 𝑦), another instance of P9.)

Step 2, the middle integral, with respect to 𝑦, from 0 to 𝑥, treating 𝑥 as constant:

3
B (2𝑥 % + 2𝑥𝑦) 𝑑𝑦 = [2𝑥 % 𝑦 + 𝑥𝑦 % ]&3 = 2𝑥 % ⋅ 𝑥 + 𝑥 ⋅ 𝑥 % = 2𝑥 / + 𝑥 / = 3𝑥 /
&

(combining 2𝑥 / And 𝑥 / Into 3𝑥 / Is the distributive law P9 read in reverse: 2𝑥 / + 1 ⋅ 𝑥 / =

(2 + 1)𝑥 / .)

Step 3, the outer integral, with respect to 𝑥, from 0 to 1:

 # #
/
𝑥. 1 3
B 3 𝑥 𝑑𝑥 = 3 ˆ ‰ = 3 ⋅ =
& 4 & 4 4
/
So ∭R 2 𝑥 𝑑𝑉 = ..

3.3 Cylindrical coordinates

When a solid has circular symmetry around an axis, think of a cylinder, a cone, or a paraboloid,
cylindrical coordinates are the natural fit. They amount to nothing more than polar coordinates
applied to 𝑥, 𝑦, with 𝑧 left completely alone:

𝑥 = 𝑟cos𝜃, 𝑦 = 𝑟sin𝜃, 𝑧 = 𝑧

Matching Section 2.5’s logic exactly, since the 𝑧-direction doesn’t distort anything at all (it’s
perpendicular to the 𝑟, 𝜃 plane and unaffected by the polar substitution), the volume element
becomes:

𝑑𝑉 = 𝑟 𝑑𝑧 𝑑𝑟 𝑑𝜃

Worked example 3.2. Find the volume of the solid cylinder of radius 3 and height 5, standing
with its base on the 𝑥𝑦-plane, centered on the 𝑧-axis. (Volume is given by ∭R 1 𝑑𝑉; integrating
the constant function 1 over a region gives exactly that region’s volume, since it amounts to
summing “1 times each tiny volume piece,” which just adds up all the tiny pieces themselves.)

Step 1: Bounds. The base disk has radius 3, so 0 ≤ 𝑟 ≤ 3 and 0 ≤ 𝜃 ≤ 2𝜋. The height runs from
𝑧 = 0 to 𝑧 = 5.

Step 2: Set up, including the factor of 𝑟 from 𝑑𝑉 = 𝑟 𝑑𝑧 𝑑𝑟 𝑑𝜃:

%< / 4
‹ 1 𝑑𝑉 = B B B 𝑟 𝑑𝑧 𝑑𝑟 𝑑𝜃
R & & &

Step 3, the innermost integral, with respect to 𝑧 (the integrand 𝑟 is constant with respect to 𝑧):
4
B 𝑟 𝑑𝑧 = 𝑟[𝑧]4& = 5𝑟
&

Step 4, the middle integral, with respect to 𝑟:

/ /
𝑟% 9 45
B 5 𝑟 𝑑𝑟 = 5 ˆ ‰ = 5 ⋅ =
& 2 & 2 2

Step 5, the outer integral, with respect to 𝜃:

%<
45 45
B 𝑑𝜃 = (2𝜋) = 45𝜋
& 2 2
So the volume comes out to 45𝜋, which sanity-checks nicely against the elementary formula for
a cylinder’s volume, 𝜋𝑟 % ℎ = 𝜋(3% )(5) = 45𝜋. The two approaches agree, exactly as they
should.

3.4 Spherical coordinates

For solids with symmetry around a single point rather than an axis, spheres, cones measured
from the origin, balls, spherical coordinates describe a point using three quantities: 𝜌 (rho, the
straight-line distance from the origin to the point), 𝜙 (phi, the angle measured down from the
positive 𝑧-axis, ranging from 0 to 𝜋), and 𝜃 (the same angle as in polar and cylindrical
coordinates, measured around the 𝑧-axis, ranging from 0 to 2𝜋). The conversion is:

𝑥 = 𝜌sin𝜙cos𝜃, 𝑦 = 𝜌sin𝜙sin𝜃, 𝑧 = 𝜌cos𝜙

And the volume element, derived from the geometry of a small spherical “box” in a manner
directly analogous to the polar-rectangle argument back in Section 2.5, but now carrying two
angular distortions instead of just one, works out to:

𝑑𝑉 = 𝜌% Sin𝜙 𝑑𝜌 𝑑𝜙 𝑑𝜃

Worked example 3.3. Find the volume of a solid ball of radius 2 centered at the origin.

Step 1: Bounds, 0 ≤ 𝜌 ≤ 2 (distance from the center out to the surface), 0 ≤ 𝜙 ≤ 𝜋 (from
straight up to straight down), 0 ≤ 𝜃 ≤ 2𝜋 (all the way around).

Step 2: Set up:

%< < %
B B B 𝜌 % Sin𝜙 𝑑𝜌 𝑑𝜙 𝑑𝜃
& & &

Step 3, the innermost integral, with respect to 𝜌:

% %
𝜌/%
8
B 𝜌 𝑑𝜌 = ˆ ‰ =
& 3 & 3
0
Step 4, the middle integral, with respect to 𝜙 (the constant / Factors straight out by P9):
<
8 8 8 8 16
B Sin𝜙 𝑑𝜙 = [−cos𝜙]<& = •−cos𝜋 − (−cos0)‚ = (1 + 1) =
& 3 3 3 3 3

Step 5, the outer integral, with respect to 𝜃:

%<
16 16 32𝜋
B 𝑑𝜃 = (2𝜋) =
& 3 3 3
 . . /%<
This matches the known formula for a sphere’s volume, / 𝜋𝑟 / = / 𝜋(2/ ) = /
, exactly as
expected of a correct calculation.

PART 4: Line Integrals

4.1 What problem does the line integral solve?
Everything up to this point has been integrated over an interval, a flat region, or a solid. A line
integral instead integrates along a curve, a one-dimensional path that is nonetheless allowed to
bend and twist its way through two- or three-dimensional space, unlike the straight interval [𝑎, 𝑏]
that Part 1 was built around.
There are two flavors worth distinguishing carefully: line integrals of scalar functions, meaning
functions with a plain number output, and line integrals of vector fields, meaning functions
whose output is itself a vector, an arrow carrying both length and direction. Both get developed
below, since each shows up in different physical and geometric contexts.

4.2 Parametrizing a curve

Before integrating along a curve 𝐶, the curve first needs to be described mathematically in a
usable form. A parametrization describes every point on the curve as a function of a single
variable 𝑡, the parameter, typically ranging over some interval 𝑡 ∈ [𝛼, 𝛽]:

𝑟⃗(𝑡) = •𝑥(𝑡), 𝑦(𝑡)‚ (𝑖𝑛 𝑡ℎ𝑒 𝑝𝑙𝑎𝑛𝑒) 𝑜𝑟 𝑟⃗(𝑡) = •𝑥(𝑡), 𝑦(𝑡), 𝑧(𝑡)‚ (𝑖𝑛 𝑠𝑝𝑎𝑐𝑒)

Here 𝑟⃗(𝑡) Is a vector-valued function: at each value of 𝑡, it outputs a point’s coordinates, and as 𝑡
sweeps from 𝛼 to 𝛽, that point traces out the curve 𝐶 in its entirety.

Example parametrization. The unit circle, radius 1, centered at the origin, is parametrized by
𝑥(𝑡) = cos𝑡, 𝑦(𝑡) = sin𝑡, for 𝑡 ∈ [0,2𝜋]. As 𝑡 increases across that interval, the point
(Cos𝑡, sin𝑡) Traces the whole circle exactly once, moving counterclockwise.

The speed factor ∣ 𝑟⃗ 1 (𝑡) ∣. Differentiating the parametrization component by component gives
𝑟⃗ 1 (𝑡) = •𝑥 1 (𝑡), 𝑦 1 (𝑡)‚, or with an additional 𝑧 1 (𝑡) Term in three dimensions. This vector points
in the direction of travel along the curve at parameter value 𝑡, and its length,

∣ 𝑟⃗ 1 (𝑡) ∣= s𝑥 1 (𝑡)% + 𝑦 1 (𝑡)% i𝑜𝑟 s𝑥 1 (𝑡)% + 𝑦 1 (𝑡)% + 𝑧 1 (𝑡)% 𝑖𝑛 𝑠𝑝𝑎𝑐𝑒j

Represents the “speed” at which the curve is being traced out, meaning how much actual arc
length is covered per unit change in 𝑡. This quantity turns out to be essential below, because it’s
exactly what converts a chunk of the abstract parameter 𝑡 into the corresponding chunk of actual,
physical arc length along the curve.
4.3 Line integral of a scalar function (with respect to arc length)
Suppose 𝑓(𝑥, 𝑦) Is a scalar function, meaning a single-number output, and 𝐶 is a curve. The arc
length differential is 𝑑𝑠 =∣ 𝑟⃗ 1 (𝑡) ∣ 𝑑𝑡; it converts the abstract parameter-width 𝑑𝑡 into a genuine
length along the curve itself. With that piece in hand:
S
B𝑓 (𝑥, 𝑦) 𝑑𝑠 = B 𝑓 •𝑥(𝑡), 𝑦(𝑡)‚ ∣ 𝑟⃗ 1 (𝑡) ∣ 𝑑𝑡
G T

In words: evaluate 𝑓 along the curve, weight each value by how fast the curve is being traced
there (converting parameter-time into actual distance covered), and add it all up. A physical use
for this: if 𝑓(𝑥, 𝑦) Represents the linear density, mass per unit length, of a bent wire shaped like
𝐶, then ∫G 𝑓 𝑑𝑠 gives that wire’s total mass.

Worked example 4.1. Evaluate ∫G (𝑥 + 𝑦) 𝑑𝑠 where 𝐶 is the line segment from (0,0) To (1,1).

Step 1: Parametrize the segment. A straight line from (0,0) To (1,1) Is simply 𝑥(𝑡) = 𝑡, 𝑦(𝑡) =
𝑡, for 𝑡 ∈ [0,1] (as 𝑡 goes from 0 to 1, the point (𝑡, 𝑡) Moves steadily from (0,0) To (1,1)).

Step 2: Differentiate: 𝑥 1 (𝑡) = 1, 𝑦 1 (𝑡) = 1. So ∣ 𝑟⃗ 1 (𝑡) ∣= √1% + 1% = √2, a constant, since the
line is straight and 𝑡 measures progress along it at a perfectly uniform rate.

Step 3: Substitute into the integrand: 𝑓•𝑥(𝑡), 𝑦(𝑡)‚ = 𝑥(𝑡) + 𝑦(𝑡) = 𝑡 + 𝑡 = 2𝑡.

Step 4: Assemble and evaluate:

# # #
𝑡% 1
B(𝑥 + 𝑦) 𝑑𝑠 = B (2𝑡) •√2‚ 𝑑𝑡 = 2√2 B 𝑡 𝑑𝑡 = 2√2 ˆ ‰ = 2√2 ⋅ = √2
G & & 2 & 2

So ∫G (𝑥 + 𝑦) 𝑑𝑠 = √2.

4.4 Line integral of a vector field (work done along a path)

Now suppose 𝐹⃗ (𝑥, 𝑦) = •𝑃(𝑥, 𝑦), 𝑄(𝑥, 𝑦)‚ Is a vector field: at every point in the plane, it
assigns a vector, built from two component functions 𝑃 and 𝑄, rather than a single plain number.
Physically, 𝐹⃗ Very often represents a force acting at each point in space, which is exactly the
interpretation used below.

The line integral of 𝐹⃗ Along a curve 𝐶, parametrized by 𝑟⃗(𝑡) For 𝑡 ∈ [𝛼, 𝛽], is defined as:
S
B𝐹⃗ ⋅ 𝑑𝑟⃗ = B 𝐹⃗ •𝑟⃗(𝑡)‚ ⋅ 𝑟⃗ 1 (𝑡) 𝑑𝑡
G T
Here ⋅ denotes the dot product of two vectors: for vectors (𝑃, 𝑄) And •𝑥 1 (𝑡), 𝑦 1 (𝑡)‚, the dot
product works out to 𝑃 𝑥 1 (𝑡) + 𝑄 𝑦 1 (𝑡), a plain number, obtained by multiplying corresponding
components together and adding the results.

Physical meaning: this quantity is exactly the work done by a force field 𝐹⃗ On an object moving
along the path 𝐶. At each instant, only the component of force acting in the direction of motion
contributes to work; the dot product automatically extracts precisely that component, since 𝑢 ˜⃗ ⋅
𝑣⃗ =∣ 𝑢
˜⃗ ∣∣ 𝑣⃗ ∣ cos𝛾 (where 𝛾 is the angle between the two vectors), a quantity that is largest when
the force aligns with the direction of travel and drops to zero the moment the force is
perpendicular to the motion.
An equivalent and very common way to write the same integral, expanding the dot product
before integrating rather than after, is:

B𝐹⃗ ⋅ 𝑑𝑟⃗ = B𝑃 𝑑𝑥 + 𝑄 𝑑𝑦
G G

Worked example 4.2. Compute the work done by the force field 𝐹⃗(𝑥, 𝑦) = (𝑦, −𝑥) Moving a
particle along the curve 𝐶, the unit circle, parametrized by 𝑥(𝑡) = cos𝑡, 𝑦(𝑡) = sin𝑡, for 𝑡 ∈
[0,2𝜋], one full counterclockwise trip around the circle.

Step 1: Differentiate the parametrization: 𝑥 1 (𝑡) = −sin𝑡, 𝑦 1 (𝑡) = cos𝑡.

Step 2: Evaluate 𝐹⃗ Along the curve, substituting 𝑥 = cos𝑡, 𝑦 = sin𝑡: 𝐹⃗ •𝑥(𝑡), 𝑦(𝑡)‚ =
(Sin𝑡, −cos𝑡).

Step 3: Take the dot product 𝐹⃗ ⋅ 𝑟⃗ 1 (𝑡):

(Sin𝑡)(−sin𝑡) + (−cos𝑡)(Cos𝑡) = −Sin% 𝑡 − Cos % 𝑡 = −(Sin% 𝑡 + Cos % 𝑡) = −1

(using the trigonometric identity Sin% 𝑡 + Cos% 𝑡 = 1, then factoring out the negative sign using
P9).
Step 4: Integrate:
%<
B𝐹⃗ ⋅ 𝑑𝑟⃗ = B (−1) 𝑑𝑡 = −[𝑡]%<
& = −2𝜋
G &

So the force field does −2𝜋 units of work on the particle over one full loop. The negative sign is
meaningful, not just an artifact of the arithmetic: it means the force field, on net, opposes the
direction of travel around this particular loop. This particular field, (𝑦, −𝑥), actually points
“clockwise” everywhere in the plane, so tracing the circle counterclockwise fights against it the
entire way around.
4.5 The Fundamental Theorem for Line Integrals (a preview of
“conservative” fields)
There’s a beautiful shortcut here, directly analogous to the single-variable Fundamental Theorem
of Calculus. If a vector field 𝐹⃗ Happens to be a gradient field, meaning there exists a scalar
function 𝜙(𝑥, 𝑦), called a potential function, such that 𝐹⃗ = ∇𝜙 (the gradient of 𝜙, meaning 𝐹⃗ =
UV UV
i U3 , U6 j, the vector built from the partial derivatives of 𝜙), then for any curve 𝐶 running from a
start point 𝐴 to an end point 𝐵:

B𝐹⃗ ⋅ 𝑑𝑟⃗ = 𝜙(𝐵) − 𝜙(𝐴)

G

This says the line integral doesn’t depend on the specific path taken at all, only on the start and
)
end points, which mirrors exactly how ∫$ 𝑓 (𝑥) 𝑑𝑥 = 𝐹(𝑏) − 𝐹(𝑎) Depended only on the
endpoints 𝑎, 𝑏, never on the specific way the interval was approached. It’s a genuinely deep and
useful fact; it’s precisely why, physically, gravity and electric forces are described as
“conservative”: the work they do only depends on where an object starts and ends, never on the
U
particular path it wanders along in between. Stating it fully requires partial derivatives (the U3
Notation above), which belongs to Calc 3 material not yet reached here. It’s flagged now purely
as a preview, so that when “conservative vector fields” and “potential functions” show up later in
Calc 3, they’re recognizable as the direct sequel to what’s just been learned here.
Summary: how the four types relate
Type Domain being Formula pattern Key “extra factor” to remember
summed over
Single Interval [𝑎, 𝑏] ) None; Fundamental Theorem
B 𝑓 (𝑥) 𝑑𝑥
integral $
directly

Double Flat region 𝑅 ∬M 𝑓 𝑑𝐴, iterate as ∫ In polar: 𝑑𝐴 = 𝑟 𝑑𝑟 𝑑𝜃

integral ∫ 𝑓 𝑑𝑦 𝑑𝑥

Triple Solid region 𝐸 ∭R 𝑓 𝑑𝑉, iterate Cylindrical: 𝑑𝑉 = 𝑟 𝑑𝑧 𝑑𝑟 𝑑𝜃;

%
integral innermost-to-outermost spherical: 𝑑𝑉 = 𝜌 Sin𝜙 𝑑𝜌 𝑑𝜙 𝑑𝜃
Line Curve 𝐶 Scalar: ∫G 𝑓 𝑑𝑠; vector: 𝑑𝑠 =∣ 𝑟⃗ 1 (𝑡) ∣ 𝑑𝑡
integral ∫G 𝐹⃗ ⋅ 𝑑𝑟⃗

Every single one of these is built from the same three-step skeleton: (1) chop the domain into
infinitesimal pieces, (2) multiply the function’s value by the size of each piece, (3) sum and take
a limit, and every evaluation technique developed above, the Fundamental Theorem, iterated
integrals, substitution, coordinate changes, exists purely to make that limit computable without
ever literally having to take one by hand.

PART A: Sequences and Series: A Complete Guide

A.1 What is a sequence?
A sequence is an ordered, infinite list of numbers, written 𝑎# , 𝑎% , 𝑎/ , …, or compactly
{𝑎' }-
'+# (read: "the sequence whose 𝑛-th term is 𝑎' , for 𝑛running through the positive integers
1,2,3, …"). Formally, a sequence is a function whose input is a positive integer 𝑛(called the
index) and whose output is a real number 𝑎' (called the 𝑛-th term).
# # # #
Example: 𝑎' = 'Generates the sequence 1, % , / , . , …

A.2 Limits of sequences: convergence and divergence

The central question about a sequence is: as 𝑛grows without bound, does 𝑎' Settle down and
approach one specific number, or not?

Definition (limit of a sequence). We say a sequence {𝑎' }Converges to a number 𝐿(called the
limit), written

Lim𝑎' = 𝐿
'→-

If, informally, the terms 𝑎' Get arbitrarily close to 𝐿and stay close as 𝑛increases. (The fully
rigorous version: for every 𝜀 > 0, read "epsilon," representing an arbitrarily small positive
tolerance, there exists an integer 𝑁such that ∣ 𝑎' − 𝐿 ∣< 𝜀for every 𝑛 > 𝑁. You won't need to
grind through this 𝜀-𝑁 definition for routine Calc 2 problems, but it's the rigorous backbone
behind "gets arbitrarily close.")

If no such number 𝐿exists, the sequence diverges.

'
Worked example A.1. Determine whether 𝑎' = '2#Converges, and if so, to what.

Step 1: Rewrite 𝑎' To see its behavior for large 𝑛. Divide numerator and denominator by 𝑛(legal
#
since 𝑛 ≠ 0, using P7, the multiplicative-inverse axiom, to form '):

𝑛 𝑛/𝑛 1
𝑎' = = =
𝑛 + 1 (𝑛 + 1)/𝑛 1 + 1
𝑛
#
Step 2: As 𝑛 → ∞, the term ' → 0(since dividing 1by an ever-larger number produces an ever-
#
smaller result). So the denominator 1 + ' → 1 + 0 = 1(using P2, the additive-identity axiom).
 #
Step 3: Therefore 𝑎' → # = 1. The sequence converges to 𝐿 = 1.

Worked example A.2 (divergence). Determine whether 𝑎' = (−1)' Converges.

The terms alternate forever: −1,1, −1,1, …. They never settle near one single number, they
perpetually bounce between two values. So this sequence diverges (specifically, this is called
"diverges by oscillation").

A.3 Monotonic and bounded sequences

Monotonic. A sequence is increasing if 𝑎'2# ≥ 𝑎' For every 𝑛(each term is at least as big as the
one before), and decreasing if 𝑎'2# ≤ 𝑎' For every 𝑛. A sequence that is either increasing or
decreasing throughout is called monotonic.

Bounded. A sequence is bounded above if there's some number 𝑀with 𝑎' ≤ 𝑀for every 𝑛;
bounded below if there's some number 𝑚with 𝑎' ≥ 𝑚for every 𝑛; and simply bounded if both
hold.
The Monotone Convergence Theorem. If a sequence is monotonic and bounded, it is guaranteed
to converge. (Intuitively: an increasing sequence that's bounded above can't blow up to infinity
(it has a ceiling) and since it never decreases, it must creep up toward some limiting value just
below that ceiling.) This theorem is powerful precisely because it lets you prove a limit exists
without computing it directly.

A.4 Series: summing infinitely many terms

A series is the result of adding up all the terms of a sequence:
-

= 𝑎' = 𝑎# + 𝑎% + 𝑎/ + ⋯
'+#

This raises an obvious puzzle: how can adding infinitely many numbers produce a finite answer?
The resolution mirrors the Riemann-sum idea from Part 1 of the integrals guide, build up a
sequence of partial sums and take a limit.

Partial sum. The 𝑁-th partial sum is 𝑆W = ∑W

'+# 𝑎' = 𝑎# + 𝑎% + ⋯ + 𝑎W , the sum of just the first
𝑁terms, a perfectly ordinary finite sum.

Definition (convergence of a series). The series ∑-

'+# 𝑎' Converges to a sum 𝑆if the sequence of
{ }
partial sums 𝑆W Converges to 𝑆:
-

= 𝑎' = 𝑆 ⇔ Lim 𝑆W = 𝑆
W→-
'+#

If {𝑆W }Diverges, the series diverges.

A.5 The Geometric Series
A geometric series has the form
-

= 𝑎 𝑟 ' = 𝑎 + 𝑎𝑟 + 𝑎𝑟 % + 𝑎𝑟 / + ⋯
'+&

Where 𝑎is the first term (a fixed nonzero constant) and 𝑟is the common ratio (each term is
𝑟times the previous one).

Convergence rule (derivation). Consider the partial sum 𝑆W = 𝑎 + 𝑎𝑟 + 𝑎𝑟 % + ⋯ + 𝑎𝑟 W"# .

Multiply both sides by 𝑟:

𝑟𝑆W = 𝑎𝑟 + 𝑎𝑟 % + ⋯ + 𝑎𝑟 W

Subtract (this is licensed by P3, the additive-inverse axiom, letting us cancel matching terms):

𝑆W − 𝑟𝑆W = 𝑎 − 𝑎𝑟 W ⇒ 𝑆W (1 − 𝑟) = 𝑎(1 − 𝑟 W )

(the left side used P9, the distributive law, in reverse to factor 𝑆W Out; the right side used P9 to
factor 𝑎out). If 𝑟 ≠ 1, divide both sides by (1 − 𝑟)(valid by P7, since 1 − 𝑟 ≠ 0):

𝑎(1 − 𝑟 W )
𝑆W =
1−𝑟
Now take the limit as 𝑁 → ∞. If ∣ 𝑟 ∣< 1, then 𝑟 W → 0(a fraction raised to an ever-larger power
shrinks toward zero), so:
-
𝑎
= 𝑎 𝑟' = (𝑜𝑛𝑙𝑦 𝑣𝑎𝑙𝑖𝑑 𝑤ℎ𝑒𝑛 ∣ 𝑟 ∣< 1)
1−𝑟
'+&

If ∣ 𝑟 ∣≥ 1, 𝑟 W Does not shrink to zero (it either grows without bound or oscillates), so the series
diverges.
# '
Worked example A.3. Evaluate ∑-
'+& 3 i%j .

# #
Here 𝑎 = 3, 𝑟 = %, and ∣ 𝑟 ∣= % < 1, so it converges:
-
1 ' 3 3
=3z { = = =3⋅2 =6
2 1 1
'+& 1−2 2
#
(the last step used P7, dividing by %Is the same as multiplying by its multiplicative inverse, 2).
A.6 The Divergence Test (the first, cheapest check)
Divergence Test. If Lim'→- 𝑎' ≠ 0(or the limit doesn't exist), then ∑ 𝑎' Diverges.

Why? If the individual terms don't shrink toward zero, you're perpetually adding non-negligible
chunks, the partial sums can never settle down to one value.
Critical warning, worth memorizing precisely: this test can only prove divergence, never
convergence. If 𝑎' → 0, the series might converge or might still diverge, you need a different test
#
to decide. (The classic counterexample is the harmonic series ∑ ', whose terms shrink to 0, yet
the series still diverges, see below.)
'
Worked example A.4. Test ∑-
'+# %'2#For divergence.

'
Step 1: Compute Lim'→- %'2#. Divide numerator and denominator by 𝑛(P7 again):

𝑛 1 1 1
= → =
2𝑛 + 1 2 + 1 2+0 2
𝑛
#
Step 2: Since the limit is % ≠ 0, the Divergence Test tells us this series diverges.

A.7 The Integral Test

Integral Test. Suppose 𝑓(𝑥)Is continuous, positive, and decreasing for 𝑥 ≥ 1, and 𝑎' = 𝑓(𝑛).
-
Then ∑- '+# 𝑎' Converges if and only if ∫# 𝑓 (𝑥) 𝑑𝑥converges (this is an improper integral, an
J
integral with an infinite bound, itself defined as LimJ→- ∫# 𝑓 (𝑥) 𝑑𝑥).

Why does this work? Picture the rectangles of a Riemann sum (from Part 1 of the integral guide)
sitting either just above or just below the curve 𝑦 = 𝑓(𝑥). Because 𝑓is decreasing, the sum ∑
-
𝑎' And the integral ∫# 𝑓 (𝑥) 𝑑𝑥trap each other between bounds that behave the same way, either
both stay finite or both blow up together.
Worked example A.5 (the harmonic series, and the p-series test). Determine whether
#
∑-
'+# 'Converges.

#
Step 1: Let 𝑓(𝑥) = 3, which is continuous, positive, and decreasing for 𝑥 ≥ 1.
-# J#
Step 2: Evaluate ∫# 3
𝑑𝑥 = LimJ→- ∫# 3 𝑑𝑥 = LimJ→- [ln𝑥]#J = LimJ→- (Ln𝑡 − ln1) =
LimJ→- Ln𝑡 = ∞.
 #
Step 3: Since the integral diverges (grows without bound), the Integral Test says ∑ 'Diverges
#
too, despite the fact that ' → 0. This confirms the warning in A.6: individual terms shrinking to
zero is not enough to guarantee convergence.
#
This generalizes to the 𝑝-series: ∑-
'+# '' Converges if 𝑝 > 1and diverges if 𝑝 ≤ 1(provable by
-
the same integral-test argument, since ∫# 𝑥 "X 𝑑𝑥converges exactly when 𝑝 > 1).

A.8 The Comparison Test and Limit Comparison Test

(Direct) Comparison Test. Suppose 0 ≤ 𝑎' ≤ 𝑏' For all 𝑛(past some starting point). Then:

• If ∑ 𝑏' Converges, so does ∑ 𝑎' (a series squeezed underneath a convergent series can't
itself blow up).
• If ∑ 𝑎' Diverges, so does ∑ 𝑏' (a series sitting above a divergent series must also blow
up).
#
Worked example A.6. Test ∑-
'+# ' #2#For convergence.

# #
Step 1: Notice '# 2# < '# For every 𝑛(since 𝑛% + 1 > 𝑛% , and taking the reciprocal of a larger
positive number gives a smaller result).
#
Step 2: We know ∑ '#
Is a 𝑝-series with 𝑝 = 2 > 1, so it converges (Section A.7).

Step 3: By the Comparison Test, since our series is squeezed below a convergent series, ∑
#
' #2#
Converges too.

Limit Comparison Test. Sometimes a clean term-by-term inequality is hard to find. Instead, pick
a comparison series ∑ 𝑏' (usually the "dominant part" of 𝑎' For large 𝑛) and compute 𝐿 =
$
Lim'→- )*. If 𝐿is a finite positive number (not 0, not ∞), then ∑ 𝑎' And ∑ 𝑏' Either both
*
converge or both diverge together.
/' #2#
Worked example A.7. Test ∑-
'+# ' +2'2%.

Step 1: For large 𝑛, the dominant terms are 3𝑛% On top and 𝑛. On bottom, so guess the
/'# /
comparison series 𝑏' = '+
= '# .

Step 2: Compute the ratio:

𝑎' 3𝑛% + 1 𝑛% 3𝑛. + 𝑛%

= ⋅ = .
𝑏' 𝑛. + 𝑛 + 2 3 3𝑛 + 3𝑛 + 6

Dividing numerator and denominator by 𝑛. (P7):

 1
3+ 3+0
𝑛% → =1
3 6 3+0+0
3+ + .
𝑛 / 𝑛
/ #
Step 3: The limit is 1, a finite positive number, so ∑ 𝑎' Behaves like ∑ '#
. Since ∑ '#
Is a
convergent 𝑝-series (𝑝 = 2), and constant multiples of convergent series converge, ∑
/' #2#
' +2'2%
Converges.

A.9 The Ratio Test

Ratio Test. For a series ∑ 𝑎' , compute
𝑎'2#
𝐿 = Lim ¥ ¥
'→- 𝑎'

• If 𝐿 < 1: the series converges absolutely (see A.11 for what this means).

• If 𝐿 > 1(including 𝐿 = ∞): the series diverges.

• If 𝐿 = 1: the test is inconclusive, you must use a different test.

Why does this work? If consecutive terms shrink by a fixed ratio 𝐿 < 1eventually, the tail of the
series behaves like a convergent geometric series (Section A.5) with ratio 𝐿. If 𝐿 > 1, terms are
eventually growing, so the Divergence Test guarantees divergence.

This test is especially good for series involving factorials (written 𝑛! = 𝑛 ⋅ (𝑛 − 1) ⋅

(𝑛 − 2) ⋯ 2 ⋅ 1, "𝑛 factorial," the product of all positive integers up to 𝑛) or exponentials, since
these simplify nicely under a ratio.
'!
Worked example A.8. Test ∑-
'+# %* For convergence using the Ratio Test.

'! ('2#)!
Step 1: Write out 𝑎' = %*And 𝑎'2# = %*)%
.

Step 2: Form the ratio:

𝑎'2# (𝑛 + 1)! 2' (𝑛 + 1)! 2'
¥ ¥= ⋅ = ⋅ '2#
𝑎' 2'2# 𝑛! 𝑛! 2

Step 3: Simplify each piece. Since (𝑛 + 1)! = (𝑛 + 1) ⋅ 𝑛!(the definition of factorial, multiply by
('2#)! %* # %*
the next integer), '!
= 𝑛 + 1. And %*)% = %(using the exponent rule %*)% = 2'"('2#) = 2"# ).
So:
𝑎'2# 1 𝑛+1
¥ ¥ = (𝑛 + 1) ⋅ =
𝑎' 2 2
 '2#
Step 4: Take the limit: Lim'→- %
= ∞.

Step 5: Since 𝐿 = ∞ > 1, the series diverges.

A.10 The Root Test

Root Test. Compute 𝐿 = Lim'→- *s∣ 𝑎' ∣(the 𝑛-th root of ∣ 𝑎' ∣). The convergence/divergence
conclusions are identical in structure to the Ratio Test: 𝐿 < 1converges absolutely, 𝐿 >
1diverges, 𝐿 = 1inconclusive. This test is most useful when 𝑎' Itself involves an 𝑛-th power (so
the 𝑛-th root directly cancels it).
%'2# '
Worked example A.9. Test ∑-
'+# i/'2%j .

*
%'2# %'2# '
Step 1: Compute *s∣ 𝑎' ∣= §i/'2%j = /'2%(the 𝑛-th root exactly undoes the 𝑛-th power).

%
%2 %
Step 2: Take the limit as 𝑛 → ∞(dividing numerator and denominator by 𝑛, P7): *
# → /.
/2
*

%
Step 3: Since 𝐿 = / < 1, the series converges absolutely.

A.11 Absolute vs. Conditional Convergence, and the Alternating Series

Test
Absolute convergence. A series ∑ 𝑎' Converges absolutely if ∑ ∣ 𝑎' ∣(the series of absolute
values, stripping away all the minus signs) converges. Absolute convergence is a stronger
statement: if a series converges absolutely, it is guaranteed to converge in the ordinary sense too.

Conditional convergence. If ∑ 𝑎' Converges, but ∑ ∣ 𝑎' ∣diverges, the series is said to converge
conditionally, it only converges because of cancellation between positive and negative terms, not
because the terms are "small enough" on their own.
Alternating series. A series where the terms strictly alternate in sign, written ${n = 1}^{}(- 1) ^{n
+ 1}b{n} $or ${}^{}(- 1) ^{n}b{n} $, with 𝑏' > 0for every 𝑛.
Alternating Series Test. An alternating series ${}^{}(- 1) ^{n + 1}b{n} $converges if both:

1. 𝑏' Is eventually decreasing (𝑏'2# ≤ 𝑏' ), and

2. Lim'→- 𝑏' = 0.
("#)*)%
Worked example A.10. Test ∑-
'+# '
(the "alternating harmonic series") for convergence, and
classify it.
 #
Step 1: Check the Alternating Series Test conditions with 𝑏' = ': it's decreasing (each reciprocal
#
is smaller than the last), and Lim'→- ' = 0. Both conditions hold, so the series converges.

("#)*)% #
Step 2: Check absolute convergence: ∑ ¨ '
¨ = ∑ ', the harmonic series, which we showed
diverges in Example A.5.
Step 3: Since the series converges but its absolute-value version diverges, this series converges
conditionally (not absolutely).

A.12 Power Series

A power series centered at 𝑥 = 𝑐is a series of the form
-

= 𝑐' (𝑥 − 𝑐)' = 𝑐& + 𝑐# (𝑥 − 𝑐) + 𝑐% (𝑥 − 𝑐)% + ⋯

'+&

Where 𝑐& , 𝑐# , 𝑐% , …are fixed constants called coefficients, 𝑐is a fixed constant called the center,
and 𝑥is a variable. Unlike an ordinary series of numbers, a power series is really a function of 𝑥,
for each value you plug in for 𝑥, you get a (possibly different) numerical series, which may
converge or diverge depending on 𝑥.

Radius and interval of convergence. For every power series, there is a number 𝑅(the radius of
convergence, possibly 0, a finite positive number, or ∞) such that the series converges absolutely
for ∣ 𝑥 − 𝑐 ∣< 𝑅and diverges for ∣ 𝑥 − 𝑐 ∣> 𝑅. The set of all 𝑥where the series converges is
called the interval of convergence, you find 𝑅using the Ratio Test (Section A.9) applied to the
terms of the power series, then separately check the two endpoints 𝑥 = 𝑐 − 𝑅and 𝑥 = 𝑐 + 𝑅by
hand (the Ratio Test is always inconclusive exactly at the endpoints, so those require a separate
test, like comparison or alternating-series).
(3"%)*
Worked example A.11. Find the radius and interval of convergence of ∑-
'+# '⋅/*
.

(3"%)*
Step 1: Apply the Ratio Test to 𝑎' = '⋅/*
:

𝑎'2# (𝑥 − 2)'2# 𝑛 ⋅ 3' 𝑛 1

¥ ¥=© ⋅ © =∣ 𝑥 − 2 ∣⋅ ⋅
𝑎' (𝑛 + 1)3 '2# (𝑥 − 2) ' 𝑛+1 3
' ∣3"%∣
Step 2: Take the limit as 𝑛 → ∞: '2# → 1, so this simplifies to /
.

Step 3: For convergence, we need this limit < 1:

∣𝑥−2∣
< 1 ⇒ ∣ 𝑥 − 2 ∣< 3
3
(multiplying both sides by 3, licensed by P7). So the radius of convergence is 𝑅 = 3, and the
series converges absolutely for −1 < 𝑥 < 5(since ∣ 𝑥 − 2 ∣< 3means −3 < 𝑥 − 2 < 3, and
adding 2to all three parts, using P1/P2, gives −1 < 𝑥 < 5).
Step 4: Check the endpoints separately.
/* #
• At 𝑥 = 5: the series becomes ∑ '⋅/*
= ∑ ', the harmonic series, diverges (Example A.5).

("/)* ("#)*
• At 𝑥 = −1: the series becomes ∑ '⋅/*
=∑ '
, the alternating harmonic series,
converges conditionally (Example A.10).

Step 5: Combine: the interval of convergence is [−,15), including −1, excluding 5.

A.13 Taylor and Maclaurin Series

If a function 𝑓(𝑥)Has derivatives of every order at a point 𝑥 = 𝑐, its Taylor series centered at 𝑐is:
-
𝑓 (')(𝑐) 𝑓 \ (𝑐)
𝑓(𝑥) = = (𝑥 − 𝑐)' = 𝑓(𝑐) + 𝑓 1 (𝑐)(𝑥 − 𝑐) + (𝑥 − 𝑐)% + ⋯
𝑛! 2!
'+&

Where 𝑓 (')(𝑐)Denotes the 𝑛-th derivative of 𝑓evaluated at 𝑐(with 𝑓 (&) (𝑐) = 𝑓(𝑐)Itself, by
convention). A Maclaurin series is simply the special case 𝑐 = 0.

The idea, in words: this expresses 𝑓(𝑥)As an "infinite polynomial" built entirely from
information about 𝑓and all its derivatives at a single point. The more terms you include, the
better this polynomial approximates 𝑓(𝑥)Near 𝑥 = 𝑐.

Worked example A.12. Find the Maclaurin series for 𝑓(𝑥) = 𝑒 3 .

Step 1: Every derivative of 𝑒 3 Is 𝑒 3 Itself, so 𝑓 (') (𝑥) = 𝑒 3 For every 𝑛.

Step 2: Evaluate at 𝑐 = 0: 𝑓 (') (0) = 𝑒 & = 1for every 𝑛.

Step 3: Plug into the formula:

-
3
1 ' 𝑥% 𝑥 /
𝑒 = = 𝑥 = 1+𝑥+ + +⋯
𝑛! 2! 3!
'+&

This particular series converges for all real 𝑥(its radius of convergence is 𝑅 = ∞, checkable via
$*)% ∣3∣
the Ratio Test, factorials in the denominator grow so fast that the ratio ¨ $*
¨ = '2# → 0for every
fixed 𝑥, always less than 1).
PART B: Linear Algebra: A Complete Guide (MATH
2232 Level)
Linear algebra studies systems of linear equations and the objects, vectors and matrices, that
organize them. The field axioms P1–P9 still govern any ordinary-number arithmetic that shows
up along the way (adding two matrix entries, say, is still just real-number addition underneath).
Vectors, however, are a new kind of object, so this part introduces a separate, self-contained set
of axioms for vector spaces at the point they first become necessary, in Section B.5.

B.1 Systems of Linear Equations

A linear equation in variables 𝑥# , 𝑥% , … , 𝑥' Is an equation of the form 𝑎# 𝑥# + 𝑎% 𝑥% + ⋯ +
𝑎' 𝑥' = 𝑏, where 𝑎# , … , 𝑎' (the coefficients) and 𝑏 (the constant term) are fixed numbers, and
every variable appears only to the first power, with no products of variables (𝑥# 𝑥% ) and no
variables inside other functions (sin(𝑥# ), √𝑥% ). This restriction is what makes the equation
“linear,” geometrically, it describes a flat object, a line, plane, or higher-dimensional analog,
rather than a curved one. A system of linear equations is a collection of such equations
considered together, and a solution is an assignment of values to 𝑥# , … , 𝑥' That satisfies every
equation simultaneously. Solving a system means finding every such assignment, or showing
there are none.

B.1.1 The augmented matrix

A matrix is a rectangular array of numbers, arranged in rows and columns. An 𝑚 × 𝑛 matrix has
𝑚 rows and 𝑛 columns (rows always listed first, by convention). Writing out variable names and
plus signs over and over is wasteful once a system has many equations, so the augmented matrix
of a linear system strips away everything except the coefficients and constants, packaging them
into one matrix, with a vertical bar sometimes drawn to remind you where the equals signs were.
For the system
2𝑥 + 𝑦 − 𝑧 =3
𝑥 − 𝑦 + 2𝑧 =1
3𝑥 + 2𝑦 + 𝑧 =8
The augmented matrix is:
2 1 −1 3
ª1 −1 2 1«
3 2 1 8
Every row operation performed on this matrix corresponds exactly to a legal algebraic move on
the original equations (multiplying an equation by a nonzero constant, adding a multiple of one
equation to another, or reordering the equations), so nothing is lost by working with the matrix
instead of the equations themselves; the matrix is simply a bookkeeping device.
B.1.2 Elementary row operations
To solve a system, three moves are permitted, called elementary row operations, each of which
changes the matrix’s appearance but never changes the underlying solution set:
1. Swap two rows.
2. Scale a row by a nonzero constant (multiply every entry in the row by that constant; P7,
the multiplicative-inverse axiom, is what guarantees this move is reversible, since the
constant being nonzero means it has an inverse to undo the scaling).
3. Add a multiple of one row to another row.

Each operation is reversible (swapping twice undoes itself, scaling by 𝑘 is undone by scaling by
#
C
, adding a multiple of one row to another is undone by subtracting that same multiple back), and
this reversibility is exactly why the solution set never changes: any solution to the new system
can be converted back into a solution of the old system by undoing the operation, and vice versa.

B.1.3 Gaussian elimination and row-echelon form

Gaussian elimination uses elementary row operations to bring the matrix into row-echelon form:
a shape where (a) all-zero rows sit at the bottom, and (b) each row’s first nonzero entry (called a
pivot) sits strictly to the right of the pivot in the row above it. Once in this form, the system is
solved by back-substitution: solve the bottom-most equation for its one remaining variable, then
substitute that value upward into the equation above, and repeat.
Gauss-Jordan elimination goes one step further, using row operations to reach reduced row-
echelon form: every pivot is exactly 1, and every pivot is the only nonzero entry in its entire
column. This form directly displays the solution with no back-substitution needed, at the cost of
somewhat more row-operation work to get there.
Worked example B.1. Solve the system above using Gauss-Jordan elimination.
Starting matrix:
2 1 −1 3
ª1 −1 2 1«
3 2 1 8
Step 1: Swap Row 1 and Row 2, to get a 1 in the top-left corner without introducing fractions
yet:
1 −1 2 1
ª2 1 −1 3«
3 2 1 8
Step 2: Eliminate below the first pivot. Replace Row 2 with (Row 2 −2 × Row 1), and Row 3
with (Row 3 −3 × Row 1), computing each entry of the new row by subtracting the
corresponding entry of 2 × Row 1 (respectively 3 × Row 1) from Row 2 (respectively Row 3):

𝑅% → 𝑅% − 2𝑅# : (2 − 2, 1 − (−2), −1 − 4, 3 − 2) = (0, 3, −5, 1)

𝑅/ → 𝑅/ − 3𝑅# : (3 − 3, 2 − (−3), 1 − 6, 8 − 3) = (0, 5, −5, 5)

1 −1 2 1
ª0 3 −5 1«
0 5 −5 5
Step 3: Make the Row 2 pivot equal to 1: divide Row 2 by 3 (P7):

𝑅% → 1⁄3 𝑅% : (0, 1, − 5⁄3 , 1⁄3)

1 −1 2 1
ª0 1 − 5⁄3 1⁄3«
0 5 −5 5
Step 4: Eliminate above and below the second pivot. Replace Row 1 with (Row 1 + Row 2), and
Row 3 with (Row 3 −5 × Row 2):

𝑅# → 𝑅# + 𝑅% : (1, −1 + 1, 2 − 5⁄3 , 1 + 1⁄3) = (1, 0, 1⁄3 , 4⁄3)

𝑅/ → 𝑅/ − 5𝑅% : •0, 5 − 5, −5 − 5(− 5⁄3), 5 − 5(1⁄3)‚ = (0, 0, 10⁄3 , 10⁄3)

1 0 1⁄3 4⁄3
ª0 1 − 5⁄3 1⁄3 «
0 0 10⁄3 10⁄3
/
Step 5: Make the Row 3 pivot equal to 1: multiply Row 3 by #& (P7):

1 0 1⁄3 4⁄3
ª0 1 − 5⁄3 1⁄3«
0 0 1 1
#
Step 6: Eliminate above the third pivot. Replace Row 1 with (Row 1 − / × Row 3), and Row 2
4
with (Row 2 + / × Row 3):

𝑅# → 𝑅# − 1⁄3 𝑅/ : (1, 0, 0, 4⁄3 − 1⁄3) = (1,0,0,1)

𝑅% → 𝑅% + 5⁄3 𝑅/ : (0, 1, 0, 1⁄3 + 5⁄3) = (0,1,0,2)

1 0 0 1
ª0 1 0 2«
0 0 1 1
This is reduced row-echelon form, and it directly reads off the solution: 𝑥 = 1, 𝑦 = 2, 𝑧 = 1.
Checking against the original three equations: 2(1) + 2 − 1 = 3 ✓; 1 − 2 + 2(1) = 1 ✓;
3(1) + 2(2) + 1 = 8 ✓. All three hold, confirming the solution.

B.2 The Algebra of Matrices

B.2.1 Special types of matrices (terminology)
• Square matrix: a matrix with the same number of rows as columns (𝑛 × 𝑛).

• Zero matrix (written 0): every entry is 0.

• Diagonal matrix: a square matrix whose only possibly-nonzero entries lie on the main
diagonal (the entries from top-left to bottom-right, position (𝑖, 𝑖)); every off-diagonal
entry is 0.
• Triangular matrix: a square matrix that is either upper triangular (every entry below the
main diagonal is 0) or lower triangular (every entry above the main diagonal is 0).

• Identity matrix (written 𝐼 or 𝐼' ): the diagonal matrix with every diagonal entry equal to 1.
It behaves like the number 1 does for ordinary multiplication: 𝐴𝐼 = 𝐼𝐴 = 𝐴 for any
compatible matrix 𝐴, which is exactly why it earns the name.

• Symmetric matrix: a square matrix 𝐴 satisfying 𝐴 = 𝐴] , where 𝐴] (the transpose of 𝐴) is

formed by flipping 𝐴 across its main diagonal, turning rows into columns. In symbols, the
entry in row 𝑖, column 𝑗 of 𝐴] Equals the entry in row 𝑗, column 𝑖 of 𝐴. A symmetric
matrix mirrors itself across the main diagonal, swapping any two reflected entries leaves
the matrix unchanged.

B.2.2 Matrix addition and scalar multiplication

If 𝐴 and 𝐵 are matrices of the same size (𝑚 × 𝑛), their sum 𝐴 + 𝐵 is formed by adding
corresponding entries; addition is simply undefined for matrices of different sizes, since there is
no sensible way to pair up their entries. Scalar multiplication 𝑘𝐴 (where 𝑘 is an ordinary number,
called a scalar to distinguish it from a matrix or vector) multiplies every entry of 𝐴 by 𝑘.
1 2 0 −1
Worked example B.2. Let 𝐴 = ¯ °, 𝐵 = ¯ °. Compute 2𝐴 − 𝐵.
3 4 2 1
2 4
Step 1: Compute 2𝐴 (multiply every entry by 2): 2𝐴 = ¯ °.
6 8
Step 2: Compute 2𝐴 − 𝐵 (subtract corresponding entries, i.e., add 2𝐴 and (−1)𝐵):
( ) 2 5
2𝐴 − 𝐵 = ¯2 − 0 4 − −1 ° = ¯ °
6−2 8−1 4 7
B.2.3 Matrix multiplication
Matrix multiplication is more intricate than addition, and it is not simply “multiply
corresponding entries” the way addition is “add corresponding entries.” If 𝐴 is 𝑚 × 𝑛 and 𝐵 is
𝑛 × 𝑝 (the number of columns of 𝐴 must match the number of rows of 𝐵, otherwise the product
is undefined), the product 𝐴𝐵 is an 𝑚 × 𝑝 matrix, where the entry in row 𝑖, column 𝑗 of 𝐴𝐵 is
computed by taking the dot product (defined formally in Section B.6) of row 𝑖 of 𝐴 with column
𝑗 of 𝐵: multiply corresponding entries and add the results. The size requirement is easy to
remember as “inner dimensions must match, outer dimensions survive”: (𝑚 × 𝑛)(𝑛 × 𝑝) =
(𝑚 × 𝑝).
1 2 2 0
Worked example B.3. Let 𝐴 = ¯ ° (2 × 2), 𝐵 = ¯ ° (2 × 2). Compute 𝐴𝐵.
3 4 1 −1
The entry in row 1, column 1 of 𝐴𝐵: (row 1 of 𝐴) ⋅ (column 1 of 𝐵) = (1)(2) + (2)(1) = 2 +
2 = 4.

The entry in row 1, column 2: (1)(0) + (2)(−1) = 0 − 2 = −2.

The entry in row 2, column 1: (3)(2) + (4)(1) = 6 + 4 = 10.

The entry in row 2, column 2: (3)(0) + (4)(−1) = 0 − 4 = −4.

4 −2
𝐴𝐵 = ¯ °
10 −4
Important warning: matrix multiplication is generally not commutative, 𝐴𝐵 ≠ 𝐵𝐴 in general
(unlike ordinary number multiplication, P8 does not carry over to matrices, and in fact 𝐵𝐴 may
not even be defined when 𝐴𝐵 is, if the sizes don’t match up both ways). Always keep track of the
order in which matrices are multiplied.

B.2.4 Proving basic properties of matrix operations

Working directly from the definitions above, several matrix-level properties can be proven
rigorously rather than just asserted.

Claim: For matrices 𝐴, 𝐵 of the same size, 𝐴 + 𝐵 = 𝐵 + 𝐴 (matrix addition is commutative).

Proof. Let 𝐴 and 𝐵 both be 𝑚 × 𝑛 matrices, and let 𝑎(L Denote the entry of 𝐴 in row 𝑖, column 𝑗,
and 𝑏(L The corresponding entry of 𝐵. By the definition of matrix addition, the entry in row 𝑖,
column 𝑗 of 𝐴 + 𝐵 is 𝑎(L + 𝑏(L , and the entry in the same position of 𝐵 + 𝐴 is 𝑏(L + 𝑎(L . Since 𝑎(L
And 𝑏(L Are ordinary real numbers, P4 (commutativity of addition for real numbers) gives 𝑎(L +
𝑏(L = 𝑏(L + 𝑎(L Directly. Since every corresponding entry of 𝐴 + 𝐵 and 𝐵 + 𝐴 is equal, the
matrices themselves are equal: 𝐴 + 𝐵 = 𝐵 + 𝐴.
Notice the pattern: every entrywise matrix property reduces to the corresponding real-number
axiom (P1–P9), applied one entry at a time. This is true across the board: associativity of matrix
addition follows from P1 applied entrywise, the distributive law 𝑘(𝐴 + 𝐵) = 𝑘𝐴 + 𝑘𝐵 follows
from P9 applied entrywise, and so on. Matrix algebra does not introduce new arithmetic; it
packages the ordinary arithmetic of P1–P9 into a grid and applies it position by position.

Claim: Matrix multiplication distributes over addition: 𝐴(𝐵 + 𝐶) = 𝐴𝐵 + 𝐴𝐶 (when the sizes
are compatible).

Proof sketch. The (𝑖, 𝑗) Entry of 𝐴(𝐵 + 𝐶) Is ∑C 𝑎(C •𝑏CL + 𝑐CL ‚ (the dot-product definition of
multiplication, summing over the shared index 𝑘). By P9 applied to each term in the sum,
𝑎(C •𝑏CL + 𝑐CL ‚ = 𝑎(C 𝑏CL + 𝑎(C 𝑐CL . Summing both sides over 𝑘 and regrouping (licensed by P1
and P4, which let a sum be reordered and regrouped freely) gives ∑C 𝑎(C 𝑏CL + ∑C 𝑎(C 𝑐CL , which
is exactly the (𝑖, 𝑗) Entry of 𝐴𝐵 + 𝐴𝐶. Since this holds for every entry, 𝐴(𝐵 + 𝐶) = 𝐴𝐵 + 𝐴𝐶.

B.3 Determinants
The determinant of a square matrix 𝐴, written det(𝐴) Or |𝐴|, is a single number computed from
𝐴’s entries that encodes important structural information about 𝐴, most crucially, whether 𝐴 is
invertible (Section B.4), but also geometric information such as how 𝐴 scales area or volume.
𝑎 𝑏
2 × 2 determinant. For 𝐴 = ¯ °:
𝑐 𝑑
Det(𝐴) = 𝑎𝑑 − 𝑏𝑐
3 1
Worked example B.4. Compute det ¯ °.
2 5
Det(𝐴) = (3)(5) − (1)(2) = 15 − 2 = 13
Cofactor expansion (general method). For larger matrices, the determinant is computed by
expanding along any row or column using minors and cofactors:

• The minor 𝑀(L Of entry 𝑎(L Is the determinant of the smaller matrix left over after
deleting row 𝑖 and column 𝑗 from 𝐴.

• The cofactor 𝐶(L Is the minor with an attached sign: 𝐶(L = (−1)(2L 𝑀(L (the sign alternates
in a checkerboard pattern across the matrix, +, −, +, −, …, starting with + in position
(1,1)).

• Cofactor expansion along row 𝑖: det(𝐴) = ∑L 𝑎(L 𝐶(L (multiply each entry in the chosen
row by its cofactor, and add the results). Expanding along any row or column always
gives the same value, a fact that is not obvious from the definition but is a standard
theorem of linear algebra.
1 2 3
Worked example B.5 (3 × 3). Compute det(𝐴) For 𝐴 = ª0 4 5«, expanding along Row 1.
1 0 6
Step 1: Compute each minor for Row 1, deleting Row 1 and the relevant column each time.
4 5
𝑀## = det ¯ ° = (4)(6) − (5)(0) = 24
0 6
0 5
𝑀#% = det ¯ ° = (0)(6) − (5)(1) = −5
1 6
0 4
𝑀#/ = det ¯ ° = (0)(0) − (4)(1) = −4
1 0
Step 2: Attach the checkerboard signs: 𝐶## = (+1)(24) = 24, 𝐶#% = (−1)(−5) = 5, 𝐶#/ =
(+1)(−4) = −4.

Step 3: Combine using Row 1’s entries (1,2,3):

Det(𝐴) = (1)(24) + (2)(5) + (3)(−4) = 24 + 10 − 12 = 22

B.4 Singular, Non-singular, and Invertible Matrices

Invertible (nonsingular) matrix: a square matrix 𝐴 for which there exists another matrix 𝐴"# (its
inverse) satisfying 𝐴𝐴"# = 𝐴"# 𝐴 = 𝐼 (the identity matrix). Singular matrix: a square matrix that
has no inverse.

Key fact linking these to determinants: 𝐴 is invertible if and only if det(𝐴) ≠ 0; if det(𝐴) = 0,
the matrix is singular. This mirrors, at the matrix level, the field axiom P7: just as an ordinary
number needs to be nonzero to have a multiplicative inverse, a matrix needs a nonzero
determinant to have a matrix inverse. This is not a coincidence, both facts trace back to division-
by-something being the one operation that can fail.

B.4.1 Finding an inverse via Gauss-Jordan elimination

To find 𝐴"# : form the augmented matrix [𝐴 ∣ 𝐼] (place the identity matrix beside 𝐴), then apply
Gauss-Jordan row operations until the left side becomes 𝐼. Whatever ends up on the right side is
𝐴"# . This works because each row operation corresponds to multiplying on the left by an
invertible “elementary matrix,” so reducing 𝐴 to 𝐼 via a sequence of such operations
simultaneously transforms 𝐼 into 𝐴"# .
2 1
Worked example B.6. Find the inverse of 𝐴 = ¯ °.
1 1
Step 1: Set up the augmented matrix:
2 1 1 0
¯ °
1 1 0 1
Step 2: Swap rows to get a clean leading 1:
1 1 0 1
¯ °
2 1 1 0
Step 3: 𝑅% → 𝑅% − 2𝑅# : (2 − 2, 1 − 2, 1 − 0, 0 − 2) = (0, −1,1, −2):
1 1 0 1
¯ °
0 −1 1 −2
Step 4: 𝑅% → −𝑅% (multiply by −1, P7):
1 1 0 1
¯ °
0 1 −1 2
Step 5: 𝑅# → 𝑅# − 𝑅% : (1 − 0, 1 − 1, 0 − (−1), 1 − 2) = (1,0,1, −1):
1 0 1 −1
¯ °
0 1 −1 2
The left side is now 𝐼, so the right side is the inverse:
1 −1
𝐴"# = ¯ °
−1 2
2 1 1 −1 2−1 −2 + 2 1 0
Check: 𝐴𝐴"# = ¯ °¯ °=¯ °=¯ ° = 𝐼 ✓.
1 1 −1 2 1−1 −1 + 2 0 1
B.4.2 The adjoint method for the inverse
The adjoint (or adjugate) of 𝐴, written adj(𝐴), is the transpose of the matrix of cofactors of 𝐴
(build the matrix whose (𝑖, 𝑗) Entry is the cofactor 𝐶(L , then transpose it). The inverse can be
computed directly by:
1
𝐴"# = adj(𝐴)
Det(𝐴)
This formula also makes visible, algebraically, why det(𝐴) ≠ 0 is required: the formula divides
by det(𝐴), and P7 only grants a multiplicative inverse to nonzero numbers.
2 1
Worked example B.7. Use the adjoint method to find the inverse of 𝐴 = ¯ ° (the same matrix
1 1
as above, to compare methods).

Step 1: Compute det(𝐴) = (2)(1) − (1)(1) = 1.

𝑎𝑏
Step 2: For a 2 × 2 matrix ¯ °, the adjoint has a well-known shortcut: swap the diagonal
𝑐𝑑
𝑑 −𝑏 1 −1
entries and negate the off-diagonal entries, giving adj(𝐴) = ¯ °=¯ °.
−𝑐 𝑎 −1 2
# 1 −1 1 −1
Step 3: 𝐴"# = # ¯ °=¯ °, matching Worked example B.6 exactly, as it should,
−1 2 −1 2
since both methods compute the same object by different routes.
B.4.3 Expressing a system as 𝐴𝑥⃗ = 𝑏&⃗, and Cramer’s Rule
Any system of linear equations can be written in matrix form 𝐴𝑥⃗ = 𝑏˜⃗, where 𝐴 is the coefficient
matrix (just the coefficients, no augmentation), 𝑥⃗ Is the column vector of unknowns, and 𝑏˜⃗ Is the
column vector of constants. For example, the system in Worked example B.1 becomes:
2 1 −1 𝑥 3
ª1 −1 2 « ˆ𝑦‰ = ª1«
3 2 1 𝑧 8
(Multiplying out 𝐴𝑥⃗ Symbolically, using the row-times-column rule of Section B.2.3, and
matching the result to 𝑏˜⃗ Reconstructs the original three equations exactly, so nothing has been
lost in this repackaging.)

If 𝐴 is invertible, the unique solution is 𝑥⃗ = 𝐴"# 𝑏˜⃗, obtained by multiplying both sides of 𝐴𝑥⃗ = 𝑏˜⃗
On the left by 𝐴"# :

𝐴"# 𝐴𝑥⃗ = 𝐴"# 𝑏˜⃗ ⟹ 𝐼𝑥⃗ = 𝐴"# 𝑏˜⃗ ⟹ 𝑥⃗ = 𝐴"# 𝑏˜⃗

Cramer’s Rule is an alternative that uses determinants directly, without computing the full
inverse. For a system 𝐴𝑥⃗ = 𝑏˜⃗ With 𝐴 an 𝑛 × 𝑛 invertible matrix, the 𝑖-th unknown is:
Det(𝐴( )
𝑥( =
Det(𝐴)

Where 𝐴( Is the matrix formed by replacing the 𝑖-th column of 𝐴 with 𝑏˜⃗.
2𝑥 + 𝑦 = 5
Worked example B.8. Solve µ Using Cramer’s Rule.
𝑥−𝑦=1
2 1 ˜⃗ 5
Step 1: Identify 𝐴 = ¯ °, 𝑏 = ¯ °.
1 −1 1
Step 2: det(𝐴) = (2)(−1) − (1)(1) = −2 − 1 = −3.
5 1
Step 3: Form 𝐴# (replace column 1 with 𝑏˜⃗): 𝐴# = ¯ °, so det(𝐴# ) = (5)(−1) − (1)(1) =
1 −1
−5 − 1 = −6.
2 5
Step 4: Form 𝐴% (replace column 2 with 𝑏˜⃗): 𝐴% = ¯ °, so det(𝐴% ) = (2)(1) − (5)(1) = 2 −
1 1
5 = −3.
Step 5: Apply the rule:
Det(𝐴# ) −6 Det(𝐴% ) −3
𝑥= = = 2, 𝑦= = =1
Det(𝐴) −3 Det(𝐴) −3
Check: 2(2) + 1 = 5 ✓; 2 − 1 = 1 ✓.

B.5 The Vector Space ℝ!

B.5.1 Definition of a vector space, and the vector space axioms
A vector space is a set 𝑉 of objects (called vectors) together with two operations, vector addition
and scalar multiplication (multiplying a vector by an ordinary real number, called a scalar),
satisfying the following ten axioms, for all vectors 𝑢
˜⃗, 𝑣⃗, 𝑤
˜˜⃗ ∈ 𝑉 and all scalars 𝑘, 𝑚:

• V1 (closure under addition): 𝑢

˜⃗ + 𝑣⃗ Is also in 𝑉.

• V2 (commutativity): 𝑢
˜⃗ + 𝑣⃗ = 𝑣⃗ + 𝑢
˜⃗.

• V3 (associativity): (𝑢
˜⃗ + 𝑣⃗) + 𝑤 ˜⃗ + (𝑣⃗ + 𝑤
˜˜⃗ = 𝑢 ˜˜⃗).

• V4 (zero vector): there exists a vector 0̃⃗ ∈ 𝑉 with 𝑢

˜⃗ + 0̃⃗ = 𝑢
˜⃗.

• V5 (additive inverse): for each 𝑢

˜⃗, there is a vector −𝑢
˜⃗ With 𝑢 ˜⃗) = 0̃⃗.
˜⃗ + (−𝑢

• V6 (closure under scalar multiplication): 𝑘𝑢

˜⃗ Is also in 𝑉.

• V7 (distributivity over vector addition): 𝑘(𝑢

˜⃗ + 𝑣⃗) = 𝑘𝑢
˜⃗ + 𝑘𝑣⃗.

• V8 (distributivity over scalar addition): (𝑘 + 𝑚)𝑢

˜⃗ = 𝑘𝑢
˜⃗ + 𝑚𝑢
˜⃗.

• ˜⃗) = (𝑘𝑚)𝑢
V9 (associativity of scalar multiplication): 𝑘(𝑚𝑢 ˜⃗.

• V10 (scalar identity): 1𝑢

˜⃗ = 𝑢
˜⃗.
These ten axioms are deliberately parallel to the field axioms P1–P9: V1–V5 mirror the additive
structure (P1–P4, plus P3’s inverse), and V6–V10 mirror the multiplicative/distributive structure
(P5–P9), just applied to a new kind of object rather than to ordinary numbers. Any set equipped
with an addition and scalar multiplication satisfying all ten, no matter how exotic its elements
look, counts as a vector space and inherits every theorem proven from these axioms alone.

ℝ' (read “R-n”) is the set of all ordered 𝑛-tuples of real numbers, (𝑥# , 𝑥% , … , 𝑥' ), with addition
and scalar multiplication defined component-by-component. It is the most important example of
a vector space, and, since each component is an ordinary real number, every one of V1–V10 for
ℝ' Reduces directly to the field axioms P1–P9 applied componentwise, exactly the same pattern
used to prove matrix properties in Section B.2.4. This is why ℝ' Is the natural first example:
verifying its ten axioms is really just re-verifying P1–P9, once per coordinate.

B.5.2 Subspaces, with a full proof example

A subspace 𝑊 of a vector space 𝑉 is a subset of 𝑉 that is itself a vector space, using the same
addition and scalar multiplication rules inherited from 𝑉. Rather than re-checking all ten axioms
V1–V10 every time (properties like commutativity and associativity are automatically inherited
from 𝑉, since 𝑊’s elements are also elements of 𝑉), there is a shortcut, the Subspace Test: 𝑊 is a
subspace of 𝑉 if and only if all three hold:

1. 0̃⃗ ∈ 𝑊 (the zero vector is in 𝑊).

2. 𝑊 is closed under addition: if 𝑢

˜⃗, 𝑣⃗ ∈ 𝑊, then 𝑢
˜⃗ + 𝑣⃗ ∈ 𝑊.

3. 𝑊 is closed under scalar multiplication: if 𝑢

˜⃗ ∈ 𝑊 and 𝑘 is any scalar, then 𝑘𝑢
˜⃗ ∈ 𝑊.
Only these three need checking because the remaining seven axioms (commutativity,
associativity, existence of additive inverses, and so on) are properties of how addition and scalar
multiplication behave, not properties of which elements happen to be included, so they
automatically carry over from 𝑉 to any subset of it. What can fail for a subset is closure, that
combining elements of 𝑊 might accidentally leave 𝑊, and the Subspace Test checks exactly
that.

Worked example B.9 (full proof). Prove that 𝑊 = {(𝑥, 𝑦, 𝑧) ∈ ℝ/ : 𝑥 + 𝑦 + 𝑧 = 0} (all vectors
whose components sum to zero) is a subspace of ℝ/ .

Proof.

Check 1, zero vector. The zero vector of ℝ/ Is (0,0,0). Its components sum to 0 + 0 + 0 = 0,
satisfying the defining condition of 𝑊. So (0,0,0) ∈ 𝑊. ✓

Check 2, closure under addition. Let 𝑢 ˜⃗ = (𝑥# , 𝑦# , 𝑧# ) And 𝑣⃗ = (𝑥% , 𝑦% , 𝑧% ) Be any two vectors in
𝑊. By the definition of 𝑊, this means 𝑥# + 𝑦# + 𝑧# = 0 and 𝑥% + 𝑦% + 𝑧% = 0. Their sum is 𝑢 ˜⃗ +
𝑣⃗ = (𝑥# + 𝑥% , 𝑦# + 𝑦% , 𝑧# + 𝑧% ). To confirm this sum is also in 𝑊, check that its components
add to zero:
(𝑥# + 𝑥% ) + (𝑦# + 𝑦% ) + (𝑧# + 𝑧% )

By P1 and P4 (associativity and commutativity of addition), this sum can be freely reordered and
regrouped:

= (𝑥# + 𝑦# + 𝑧# ) + (𝑥% + 𝑦% + 𝑧% ) = 0 + 0 = 0
Using the two facts assumed above, together with P2, the additive-identity axiom, for the final
˜⃗ + 𝑣⃗ ∈ 𝑊. ✓
step. So 𝑢

˜⃗ = (𝑥, 𝑦, 𝑧) ∈ 𝑊 (so 𝑥 + 𝑦 + 𝑧 = 0), and let

Check 3, closure under scalar multiplication. Let 𝑢
˜⃗ = (𝑘𝑥, 𝑘𝑦, 𝑘𝑧). Check the sum of its components:
𝑘 be any scalar. Then 𝑘𝑢

𝑘𝑥 + 𝑘𝑦 + 𝑘𝑧 = 𝑘(𝑥 + 𝑦 + 𝑧)

Using P9, the distributive law, in reverse to factor 𝑘 out of the sum. Since 𝑥 + 𝑦 + 𝑧 = 0 by
assumption, this becomes 𝑘(0) = 0 (any number times zero is zero, a consequence of P9 and P2
˜⃗ ∈ 𝑊. ✓
together). So 𝑘𝑢
All three conditions of the Subspace Test hold, so 𝑊 is a subspace of ℝ/ .

Geometrically, this subspace is a plane through the origin in ℝ/ . More generally, the only
subspaces of ℝ% Are {0̃⃗}, lines through the origin, or all of ℝ% ; the only subspaces of ℝ/ Are {0̃⃗},
lines through the origin, planes through the origin, or all of ℝ/ . The phrase “through the origin”
is not incidental: any subset failing to contain 0̃⃗ Automatically fails Check 1 and can never be a
subspace, no matter how natural it otherwise looks (a line that misses the origin, for instance, is
never a subspace).

B.5.3 Span, linear independence/dependence, basis, dimension

• Linear combination: a vector formed as 𝑘# 𝑣⃗# + 𝑘% 𝑣⃗% + ⋯ + 𝑘8 𝑣⃗8 , for some vectors
𝑣⃗# , … , 𝑣⃗8 And scalars 𝑘# , … , 𝑘8 . This is the single most common way new vectors are
built out of old ones throughout linear algebra.

• Span: the span of a set of vectors {𝑣⃗# , … , 𝑣⃗8 }, written span(𝑣⃗# , … , 𝑣⃗8 ), is the set of all
possible linear combinations of those vectors. The span is always itself a subspace (each
of the three Subspace Test conditions can be verified directly from the definition of linear
combination).

• Linear independence: a set of vectors {𝑣⃗# , … , 𝑣⃗8 } is linearly independent if the only
solution to 𝑘# 𝑣⃗# + ⋯ + 𝑘8 𝑣⃗8 = 0̃⃗ Is the trivial solution 𝑘# = 𝑘% = ⋯ = 𝑘8 = 0. In
words: no vector in the set can be written as a combination of the others, every vector is
pulling its own weight, contributing a direction the others cannot reach.
• Linear dependence: a set that is not linearly independent, meaning there is a nontrivial
way (not all 𝑘( = 0) to combine the vectors to get 0̃⃗, which implies at least one vector in
the set is redundant, expressible in terms of the others, and could be discarded without
shrinking the span.

• Basis: a set of vectors {𝑣⃗# , … , 𝑣⃗8 } is a basis for a vector space (or subspace) 𝑉 if (a) it
spans 𝑉, and (b) it is linearly independent. A basis is, informally, a minimal “coordinate
system” for 𝑉: enough vectors to reach every point in 𝑉 via linear combinations (that is
what spanning guarantees), with no redundancy among them (that is what independence
guarantees).

• Dimension: the dimension of a vector space 𝑉, written dim(𝑉), is the number of vectors
in any basis for 𝑉 (every basis for the same space has the same number of vectors, itself a
theorem, so the count is well-defined regardless of which basis is chosen). For instance,
dim(ℝ' ) = 𝑛, witnessed by the standard basis {𝑒⃗# , … , 𝑒⃗' } where 𝑒⃗( Has a 1 in position 𝑖
and 0 elsewhere.
B.6 Vector Geometry: Dot Product, Norm, Angle, Orthogonality,
Projection
• Dot product: for 𝑢˜⃗ = (𝑢# , … , 𝑢' ) And 𝑣⃗ = (𝑣# , … , 𝑣' ) In ℝ' , 𝑢
˜⃗ ⋅ 𝑣⃗ = 𝑢# 𝑣# + 𝑢% 𝑣% +
⋯ + 𝑢' 𝑣' (multiply corresponding components, add). The result is a single number (a
scalar), not a vector, this is what distinguishes the dot product from other vector
operations.

• ˜⃗ ∥= √𝑢
Norm (length): ∥ 𝑢 ˜⃗ = s𝑢#% + 𝑢%% + ⋯ + 𝑢'% , the vector’s length, generalizing
˜⃗ ⋅ 𝑢
the Pythagorean theorem to 𝑛 dimensions (in ℝ% This is literally the Pythagorean
theorem applied to the vector’s two components).

• Angle between vectors: the angle 𝛾 between two nonzero vectors 𝑢

˜⃗, 𝑣⃗ Satisfies 𝑢
˜⃗ ⋅ 𝑣⃗ =∥
^⃗⋅`
! ^⃗
𝑢
˜⃗ ∥∥ 𝑣⃗ ∥ cos𝛾, so cos𝛾 = ∥!^⃗∥∥`^⃗∥.

• Orthogonality: 𝑢
˜⃗ And 𝑣⃗ Are orthogonal (perpendicular) precisely when 𝑢
˜⃗ ⋅ 𝑣⃗ = 0 (from
∘
the angle formula, this forces cos𝛾 = 0, i.e., 𝛾 = 90 ).

• Distance between two vectors: ∥ 𝑢

˜⃗ − 𝑣⃗ ∥, the norm of their difference.

• Projection: the orthogonal projection of 𝑢

˜⃗ Onto 𝑣⃗ (the “shadow” 𝑢
˜⃗ Casts along the
direction of 𝑣⃗) is:
𝑢
˜⃗ ⋅ 𝑣⃗
Proj`^⃗ 𝑢
˜⃗ = 𝑣⃗
∥ 𝑣⃗ ∥%
Worked example B.10. Let 𝑢˜⃗ = (3,4) And 𝑣⃗ = (1,0). Compute the dot product, the norm of 𝑢
˜⃗,
the angle between them, and Proj`^⃗ 𝑢
˜⃗.

˜⃗ ⋅ 𝑣⃗ = (3)(1) + (4)(0) = 3.
Step 1: 𝑢

˜⃗ ∥= √3% + 4% = √9 + 16 = √25 = 5.
Step 2: ∥ 𝑢
/ /
Step 3: ∥ 𝑣⃗ ∥= √1% + 0% = 1. So cos𝛾 = (4)(#) = 4, meaning 𝛾 = Cos"# (0.6) ≈ 53.13∘ .

/
˜⃗ = ## (1,0) = (3,0).
Step 4: Proj`^⃗ 𝑢

Standard, orthogonal, and orthonormal bases. The standard basis for ℝ' Is {𝑒⃗# , 𝑒⃗% , … , 𝑒⃗' } where
𝑒⃗( Has a 1 in position 𝑖 and 0 elsewhere (e.g., in ℝ/ : 𝑒⃗# = (1,0,0), 𝑒⃗% = (0,1,0), 𝑒⃗/ = (0,0,1)).
An orthogonal basis is any basis whose vectors are all mutually perpendicular to each other. An
orthonormal basis is an orthogonal basis where, additionally, every vector has length exactly 1
(called a unit vector); orthonormal bases are especially convenient because coordinates relative
to them can be read off directly using dot products, with no system-solving required.
Gram-Schmidt process. Given any basis {𝑣⃗# , … , 𝑣⃗8 } for a subspace, the Gram-Schmidt process
systematically constructs an orthogonal (then, after normalizing lengths, orthonormal) basis for
the same subspace, by taking each vector in turn and subtracting off its projections onto all the
previously-built orthogonal vectors, removing whatever “overlap” it has with the directions
already accounted for, so that only genuinely new direction remains.

Worked example B.11 (Gram-Schmidt, three vectors). Apply Gram-Schmidt to 𝑣⃗# = (1,1,0),
𝑣⃗% = (1,0,1), 𝑣⃗/ = (0,1,1) To produce an orthogonal basis.

˜˜⃗# = 𝑣⃗# = (1,1,0) (the first vector is kept as-is; it becomes the first direction of the
Step 1: Set 𝑤
new basis).

Step 2: Build 𝑤
˜˜⃗% By subtracting 𝑣⃗% ’S projection onto 𝑤
˜˜⃗# :

𝑣⃗% ⋅ 𝑤
˜˜⃗#
Projc
^^⃗% 𝑣
⃗% = 𝑤
˜˜⃗
∥𝑤˜˜⃗# ∥% #

˜˜⃗# ∥% = 1% + 1% + 0% = 2. So
˜˜⃗# = (1)(1) + (0)(1) + (1)(0) = 1, and ∥ 𝑤
Compute 𝑣⃗% ⋅ 𝑤
#
Projc ⃗% = % (1,1,0) = (1⁄2 , 1⁄2 , 0).
^^⃗% 𝑣

𝑤
˜˜⃗% = 𝑣⃗% − Projc ⃗% = (1,0,1) − (1⁄2 , 1⁄2 , 0) = (1⁄2 , − 1⁄2 , 1)
^^⃗% 𝑣

Step 3: Build 𝑤
˜˜⃗/ By subtracting 𝑣⃗/ ’S projections onto both 𝑤
˜˜⃗# And 𝑤
˜˜⃗% :

˜˜⃗# = (0)(1) + (1)(1) + (1)(0) = 1

𝑣⃗/ ⋅ 𝑤 ⇒ Projc ⃗/ = 1⁄2 (1,1,0) = (1⁄2 , 1⁄2 , 0)
^^⃗% 𝑣

˜˜⃗% = (0)(1⁄2) + (1)(− 1⁄2) + (1)(1) = 1⁄2 ,

𝑣⃗/ ⋅ 𝑤 ˜˜⃗% ∥% = (1⁄2)% + (− 1⁄2)% + 1%
∥𝑤
= 1⁄4 + 1⁄4 + 1 = 3⁄2
1/2
Projc
^^⃗# 𝑣
⃗/ = (1⁄2 , − 1⁄2 , 1) = 1⁄3 (1⁄2 , − 1⁄2 , 1) = (1⁄6 , − 1⁄6 , 1⁄3)
3/2

𝑤
˜˜⃗/ = 𝑣⃗/ − Projc
^^⃗% 𝑣
⃗/ − Projc ⃗/ = (0,1,1) − (1⁄2 , 1⁄2 , 0) − (1⁄6 , − 1⁄6 , 1⁄3)
^^⃗# 𝑣

Combining componentwise: first component 0 − 1⁄2 − 1⁄6 = − 2⁄3; second component 1 −

1⁄2 + 1⁄6 = 2⁄3; third component 1 − 0 − 1⁄3 = 2⁄3.

˜˜⃗/ = (− 2⁄3 , 2⁄3 , 2⁄3)

𝑤

The set {𝑤
˜˜⃗# , 𝑤
˜˜⃗% , 𝑤
˜˜⃗/ } is now an orthogonal basis (each pair’s dot product can be checked to equal
0). To make it orthonormal, divide each 𝑤 ˜˜⃗( By its own norm ∥ 𝑤˜˜⃗( ∥.

B.6.1 Basis for the orthogonal complement of a vector

The set of all vectors orthogonal to a given vector 𝑣⃗ Forms a subspace (this itself follows the
Subspace Test, similarly to Worked example B.9) called the orthogonal complement, written 𝑣⃗ d .
To find a basis for it: set up the equation 𝑣⃗ ⋅ 𝑥⃗ = 0 (a single linear equation in the components of
𝑥⃗) and solve it like an ordinary linear system, expressing the general solution in terms of free
parameters; each parameter’s coefficient vector becomes a basis vector.

Worked example B.12. Find a basis for 𝑣⃗ d Where 𝑣⃗ = (1,2,3) ∈ ℝ/ .

Step 1: All (𝑥, 𝑦, 𝑧) With 𝑣⃗ ⋅ (𝑥, 𝑦, 𝑧) = 0 are needed: 𝑥 + 2𝑦 + 3𝑧 = 0.

Step 2: Solve for 𝑥 in terms of the free variables 𝑦, 𝑧: 𝑥 = −2𝑦 − 3𝑧.

Step 3: Write the general solution as a linear combination:
(𝑥, 𝑦, 𝑧) = (−2𝑦 − 3𝑧, 𝑦, 𝑧) = 𝑦(−2,1,0) + 𝑧(−3,0,1)

So {(−2,1,0), (−3,0,1)} is a basis for 𝑣⃗ d (a 2-dimensional plane through the origin,

perpendicular to 𝑣⃗; the dimension count matches the general pattern that a single linear equation
in ℝ/ Carves out a 2-dimensional solution set).

B.7 Lines and Planes in Three-Space

B.7.1 Lines
A line in ℝ/ Is determined by a point it passes through, 𝑃& = (𝑥& , 𝑦& , 𝑧& ), and a direction vector
𝑑⃗ = (𝑎, 𝑏, 𝑐) It runs parallel to. The parametric equations of the line are:

𝑥 = 𝑥& + 𝑎𝑡, 𝑦 = 𝑦& + 𝑏𝑡, 𝑧 = 𝑧& + 𝑐𝑡

Where 𝑡 ranges over all real numbers; as 𝑡 varies continuously, the point (𝑥, 𝑦, 𝑧) Traces out the
entire line, with 𝑡 = 0 recovering 𝑃& Itself.

B.7.2 Planes
A plane in ℝ/ Is determined by a point 𝑃& = (𝑥& , 𝑦& , 𝑧& ) On it and a normal vector 𝑛˜⃗ = (𝑎, 𝑏, 𝑐)
(a vector perpendicular to the entire plane). The normal form of the plane’s equation comes from
requiring that for any point (𝑥, 𝑦, 𝑧) On the plane, the vector from 𝑃& To (𝑥, 𝑦, 𝑧) Must be
orthogonal to 𝑛˜⃗:

𝑛˜⃗ ⋅ •(𝑥, 𝑦, 𝑧) − (𝑥& , 𝑦& , 𝑧& )‚ = 0 ⇒ 𝑎(𝑥 − 𝑥& ) + 𝑏(𝑦 − 𝑦& ) + 𝑐(𝑧 − 𝑧& ) = 0

Expanding (P9) and collecting the constant terms gives the common form 𝑎𝑥 + 𝑏𝑦 + 𝑐𝑧 = 𝑑
(where 𝑑 = 𝑎𝑥& + 𝑏𝑦& + 𝑐𝑧& ).

B.7.3 Distance from a point to a plane

Given a plane 𝑎𝑥 + 𝑏𝑦 + 𝑐𝑧 = 𝑑 (with normal vector 𝑛˜⃗ = (𝑎, 𝑏, 𝑐)) and a point 𝑄 = (𝑥# , 𝑦# , 𝑧# )
Not necessarily on the plane, the distance is:
|𝑎𝑥# + 𝑏𝑦# + 𝑐𝑧# − 𝑑| |𝑎𝑥# + 𝑏𝑦# + 𝑐𝑧# − 𝑑|
Dist = =
∥ 𝑛˜⃗ ∥ √𝑎% + 𝑏% + 𝑐 %
Why this formula works: pick any point 𝑃& On the plane; the vector ˜˜˜˜˜˜˜⃗
𝑃& 𝑄 Points from the plane
toward 𝑄, and the distance sought is the length of the component of ˜˜˜˜˜˜˜⃗
𝑃& 𝑄 Along the normal
direction, precisely what the projection formula (Section B.6) computes, simplified algebraically
into the compact form above.
Worked example B.13. Find the distance from 𝑄 = (1,2,3) To the plane 2𝑥 − 𝑦 + 2𝑧 = 4.

Step 1: Identify 𝑎 = 2, 𝑏 = −1, 𝑐 = 2, 𝑑 = 4, and ∥ 𝑛˜⃗ ∥= s2% + (−1)% + 2% = √4 + 1 + 4 =

√9 = 3.
Step 2: Plug 𝑄 = (1,2,3) Into 𝑎𝑥 + 𝑏𝑦 + 𝑐𝑧 − 𝑑: 2(1) − 1(2) + 2(3) − 4 = 2 − 2 + 6 − 4 =
2.
|%| %
Step 3: Distance = /
= /.

B.7.4 Distance from a point to a line

For a line through 𝑃& With direction vector 𝑑⃗ , and an external point 𝑄, form the vector 𝑤 ˜˜⃗ = ˜˜˜˜˜˜˜⃗
𝑃& 𝑄.
The distance from 𝑄 to the line is the length of the component of 𝑤 ˜˜⃗ Perpendicular to 𝑑⃗,
˜˜⃗’S projection onto 𝑑⃗:
computed by subtracting off 𝑤

Dist = ∥∥𝑤 ˜˜⃗ ∥∥

˜˜⃗ − Proj5⃗ 𝑤

Worked example B.14. Find the distance from 𝑄 = (2,1,0) To the line through 𝑃& = (0,0,0)
With direction 𝑑⃗ = (1,1,1).

˜˜⃗ = ˜˜˜˜˜˜˜⃗
Step 1: 𝑤 𝑃& 𝑄 = (2,1,0) − (0,0,0) = (2,1,0).

˜˜⃗ ⋅ 𝑑⃗ = (2)(1) + (1)(1) + (0)(1) = 3, and ∥ 𝑑⃗ ∥% = 1 + 1 +

Step 2: Compute the projection: 𝑤
/
˜˜⃗ = / (1,1,1) = (1,1,1).
1 = 3, so Proj5⃗ 𝑤

Step 3: The perpendicular component: 𝑤 ˜˜⃗ = (2,1,0) − (1,1,1) = (1,0, −1).

˜˜⃗ − Proj5⃗ 𝑤

Step 4: Distance =∥ (1,0, −1) ∥= s1% + 0% + (−1)% = √2.

B.8 General Vector Spaces: 𝑃" And 𝑀""

Everything defined so far in this part has been anchored to ℝ' , tuples of real numbers. But the
whole point of stating the vector-space axioms V1–V10 abstractly in Section B.5.1 was to let
genuinely different kinds of objects, polynomials, matrices, functions, qualify as “vectors” too,
provided they satisfy the same ten rules. Two standard examples: 𝑃% Is the set of all polynomials
of degree at most 2, 𝑝(𝑥) = 𝑎& + 𝑎# 𝑥 + 𝑎% 𝑥 % ; 𝑀%% Is the set of all 2 × 2 matrices. Both come
equipped with natural addition (add corresponding coefficients, or corresponding entries) and
scalar multiplication (multiply every coefficient, or every entry, by the scalar).
B.8.1 Proving 𝑃! Is a vector space
Claim: 𝑃% , with the operations above, satisfies the vector space axioms V1–V10.

Proof (representative checks; the rest follow the identical pattern). Let 𝑝(𝑥) = 𝑎& + 𝑎# 𝑥 + 𝑎% 𝑥 % ,
𝑞(𝑥) = 𝑏& + 𝑏# 𝑥 + 𝑏% 𝑥 % , 𝑟(𝑥) = 𝑐& + 𝑐# 𝑥 + 𝑐% 𝑥 % Be arbitrary elements of 𝑃% , and 𝑘, 𝑚
arbitrary scalars.

V1 (closure under addition): 𝑝(𝑥) + 𝑞(𝑥) = (𝑎& + 𝑏& ) + (𝑎# + 𝑏# )𝑥 + (𝑎% + 𝑏% )𝑥 % , which has
degree at most 2 and real coefficients, so it is in 𝑃% . ✓

V2 (commutativity): 𝑝(𝑥) + 𝑞(𝑥) = (𝑎& + 𝑏& ) + (𝑎# + 𝑏# )𝑥 + (𝑎% + 𝑏% )𝑥 % , while 𝑞(𝑥) +

𝑝(𝑥) = (𝑏& + 𝑎& ) + (𝑏# + 𝑎# )𝑥 + (𝑏% + 𝑎% )𝑥 % . By P4 (commutativity of real-number addition),
𝑎& + 𝑏& = 𝑏& + 𝑎& , and likewise for each coefficient pair. So 𝑝(𝑥) + 𝑞(𝑥) = 𝑞(𝑥) + 𝑝(𝑥). ✓

V4 (zero vector): The zero polynomial 0(𝑥) = 0 + 0𝑥 + 0𝑥 % Satisfies 𝑝(𝑥) + 0(𝑥) = 𝑝(𝑥) For
every 𝑝, by P2 applied to each coefficient. ✓

V7 (distributivity): 𝑘•𝑝(𝑥) + 𝑞(𝑥)‚ = 𝑘[(𝑎& + 𝑏& ) + (𝑎# + 𝑏# )𝑥 + (𝑎% + 𝑏% )𝑥 % ] =

𝑘(𝑎& + 𝑏& ) + 𝑘(𝑎# + 𝑏# )𝑥 + 𝑘(𝑎% + 𝑏% )𝑥 % . By P9 applied to each coefficient, 𝑘(𝑎& + 𝑏& ) =
𝑘𝑎& + 𝑘𝑏& , and similarly for the others. Regrouping (P1, P4) gives (𝑘𝑎& + 𝑘𝑎# 𝑥 + 𝑘𝑎% 𝑥 % ) +
(𝑘𝑏& + 𝑘𝑏# 𝑥 + 𝑘𝑏% 𝑥 % ) = 𝑘𝑝(𝑥) + 𝑘𝑞(𝑥). ✓

The remaining axioms (V3, V5, V6, V8, V9, V10) follow by the exact same “reduce to the
corresponding P1–P9 axiom on the coefficients” strategy, checked coefficient-by-coefficient.

The same style of proof establishes that 𝑀%% Is a vector space, reducing each axiom to the
corresponding entrywise real-number fact, this is the same argument already given in Section
B.2.4 for matrix addition and scalar-multiplication properties, just now framed as verifying the
full vector-space axiom list rather than one property at a time.

B.8.2 Subspaces, span, independence, basis, dimension in 𝑃! And 𝑀!!

Everything from Section B.5.3 carries over verbatim, since those definitions (linear combination,
span, independence, basis, dimension) were stated for any vector space, not just ℝ' . This is
precisely the payoff of stating the axioms abstractly: no new theory is needed, only new objects
to apply the existing theory to.

Worked example B.15. Is 𝑊 = {𝑝(𝑥) ∈ 𝑃% : 𝑝(0) = 0} (polynomials whose constant term is

zero) a subspace of 𝑃% ?

Zero vector: the zero polynomial has 𝑝(0) = 0 ✓. Closure under addition: if 𝑝(0) = 0 and
𝑞(0) = 0, then (𝑝 + 𝑞)(0) = 𝑝(0) + 𝑞(0) = 0 + 0 = 0 (P2) ✓. Closure under scalars: if
𝑝(0) = 0, then (𝑘𝑝)(0) = 𝑘 ⋅ 𝑝(0) = 𝑘(0) = 0 ✓. So 𝑊 is a subspace.
A natural basis for this subspace is {𝑥, 𝑥 % } (since any element of 𝑊 has the form 𝑎# 𝑥 + 𝑎% 𝑥 % , no
constant term, and 𝑥, 𝑥 % Are linearly independent, as no scalar multiple of one equals the other).
So dim(𝑊) = 2.

Standard basis for 𝑃% : {1, 𝑥, 𝑥 % }, giving dim(𝑃% ) = 3. Standard basis for 𝑀%% :
1 0 0 1 0 0 0 0
¼¯ °,¯ °,¯ °,¯ °½, giving dim(𝑀%% ) = 4.
0 0 0 0 1 0 0 1
B.8.3 Inner product spaces: norm, angle, distance, orthogonality in 𝑃! And 𝑀!!
An inner product on a vector space 𝑉 is a rule ⟨𝑢 ˜⃗, 𝑣⃗⟩ (taking two vectors, producing a scalar)
satisfying properties analogous to the dot product (symmetry, linearity, and positivity: ⟨𝑢 ˜⃗, 𝑢
˜⃗⟩ ≥ 0,
with equality only when 𝑢 ˜⃗ = 0̃⃗). Once a vector space is equipped with an inner product, the same
formulas from Section B.6 carry over abstractly, replacing every dot product with the new inner
product:
⟨𝑢
˜⃗, 𝑣⃗⟩
˜⃗ ∥= s⟨𝑢
∥𝑢 ˜⃗, 𝑢
˜⃗⟩, cos𝛾 = , ˜⃗, 𝑣⃗) =∥ 𝑢
dist(𝑢 ˜⃗ − 𝑣⃗ ∥, 𝑢
˜⃗ ⊥ 𝑣⃗ ⇔ ⟨𝑢
˜⃗, 𝑣⃗⟩ = 0
∥𝑢
˜⃗ ∥∥ 𝑣⃗ ∥
A standard inner product on 𝑃% : for 𝑝(𝑥) = 𝑎& + 𝑎# 𝑥 + 𝑎% 𝑥 % And 𝑞(𝑥) = 𝑏& + 𝑏# 𝑥 + 𝑏% 𝑥 % ,
define ⟨𝑝, 𝑞⟩ = 𝑎& 𝑏& + 𝑎# 𝑏# + 𝑎% 𝑏% (matching coefficients component by component, exactly
like the ℝ/ Dot product applied to the coefficient triples).

Worked example B.16. With this inner product, find ∥ 𝑝 ∥ for 𝑝(𝑥) = 1 + 2𝑥 − 𝑥 % , and
determine whether 𝑝(𝑥) = 1 + 2𝑥 − 𝑥 % And 𝑞(𝑥) = 2 − 𝑥 + 0𝑥 % Are orthogonal.

Step 1: ⟨𝑝, 𝑝⟩ = 1% + 2% + (−1)% = 1 + 4 + 1 = 6, so ∥ 𝑝 ∥= √6.

Step 2: ⟨𝑝, 𝑞⟩ = (1)(2) + (2)(−1) + (−1)(0) = 2 − 2 + 0 = 0. Since the inner product is 0, 𝑝

and 𝑞 are orthogonal.

A standard inner product on 𝑀%% : for 𝐴, 𝐵 ∈ 𝑀%% , define ⟨𝐴, 𝐵⟩ = ∑(,L 𝑎(L 𝑏(L (multiply
corresponding entries, sum all four products), the direct matrix analogue of the dot product.

B.9 Linear Transformations

A linear transformation 𝑇: 𝑉 → 𝑊 (from a vector space 𝑉 to a vector space 𝑊) is a function
satisfying two properties, for all 𝑢
˜⃗, 𝑣⃗ ∈ 𝑉 and scalars 𝑘:

1. 𝑇(𝑢
˜⃗ + 𝑣⃗) = 𝑇(𝑢
˜⃗) + 𝑇(𝑣⃗) (additivity).

2. 𝑇(𝑘𝑢
˜⃗) = 𝑘𝑇(𝑢
˜⃗) (homogeneity).

Together these say that 𝑇 respects the two operations that define a vector space in the first place,
so linear transformations are precisely the functions that preserve vector-space structure; this is
why they, rather than arbitrary functions, are the central object of study once vector spaces are in
place.
B.9.1 Proving or disproving a map is linear
Worked example B.17. Is 𝑇: ℝ% → ℝ% Defined by 𝑇(𝑥, 𝑦) = (𝑥 + 𝑦, 2𝑥) A linear
transformation?

˜⃗ = (𝑥# , 𝑦# ), 𝑣⃗ = (𝑥% , 𝑦% ). Then:

Check additivity. Let 𝑢

˜⃗ + 𝑣⃗) = 𝑇(𝑥# + 𝑥% , 𝑦# + 𝑦% ) = •(𝑥# + 𝑥% ) + (𝑦# + 𝑦% ), 2(𝑥# + 𝑥% )‚

𝑇(𝑢

Regrouping using P1 and P4:

˜⃗) + 𝑇(𝑣⃗) ✓
= •(𝑥# + 𝑦# ) + (𝑥% + 𝑦% ), 2𝑥# + 2𝑥% ‚ = (𝑥# + 𝑦# , 2𝑥# ) + (𝑥% + 𝑦% , 2𝑥% ) = 𝑇(𝑢

˜⃗) = 𝑇(𝑘𝑥# , 𝑘𝑦# ) = (𝑘𝑥# + 𝑘𝑦# , 2𝑘𝑥# ). By P9, 𝑘𝑥# + 𝑘𝑦# =

Check homogeneity. 𝑇(𝑘𝑢
𝑘(𝑥# + 𝑦# ). So:

˜⃗) ✓
˜⃗) = •𝑘(𝑥# + 𝑦# ), 𝑘(2𝑥# )‚ = 𝑘(𝑥# + 𝑦# , 2𝑥# ) = 𝑘𝑇(𝑢
𝑇(𝑘𝑢

Both properties hold, so 𝑇 is a linear transformation.

Worked example B.18 (disproving linearity). Is 𝑆(𝑥, 𝑦) = (𝑥 + 1, 𝑦) Linear?

˜⃗ = (1,0), 𝑣⃗ = (0,1): 𝑆(𝑢

Check additivity with 𝑢 ˜⃗ + 𝑣⃗) = 𝑆(1,1) = (2,1). But 𝑆(𝑢 ˜⃗) + 𝑆(𝑣⃗) =
(2,0) + (1,1) = (3,1). Since (2,1) ≠ (3,1), additivity fails, so 𝑆 is not a linear transformation.
The intuitive giveaway: any transformation with a “+1” shift, unconnected to the input’s scale,
will always break linearity. Every linear transformation must send 0̃⃗ → 0̃⃗ (this follows by setting
𝑘 = 0 in the homogeneity property), but 𝑆(0,0) = (1,0) ≠ (0,0) Here, an instant red flag that
saves the trouble of checking additivity by hand.

B.9.2 The standard matrix of a linear transformation

Every linear transformation 𝑇: ℝ' → ℝ8 Can be represented by an 𝑚 × 𝑛 matrix 𝐴 (called the
standard matrix) such that 𝑇(𝑥⃗) = 𝐴𝑥⃗ For every 𝑥⃗. To build 𝐴: compute 𝑇(𝑒⃗# ), 𝑇(𝑒⃗% ), … , 𝑇(𝑒⃗' )
(apply 𝑇 to each standard basis vector), and place these results as the columns of 𝐴. This works
because any 𝑥⃗ Is a linear combination of the 𝑒⃗( , and linearity guarantees 𝑇 of that combination is
the same combination of the 𝑇(𝑒⃗( ), which is exactly what matrix-vector multiplication computes.

Worked example B.19. Find the standard matrix for 𝑇(𝑥, 𝑦) = (𝑥 + 𝑦, 2𝑥) From Worked
example B.17.

𝑇(𝑒⃗# ) = 𝑇(1,0) = (1,2); 𝑇(𝑒⃗% ) = 𝑇(0,1) = (1,0). So:

1 1
𝐴=¯ °
2 0
B.9.3 Rotation, reflection, shear, dilation matrices in ℝ!
Cos𝜃 −sin𝜃
• Rotation by angle 𝜃 (counterclockwise): ¯ °
Sin𝜃 Cos𝜃
 1 0
• Reflection across the 𝑥-axis: ¯ °
0 −1
−1 0
• Reflection across the 𝑦-axis: ¯ °
0 1
𝑘 0
• Dilation (uniform scaling) by factor 𝑘: ¯ °
0 𝑘
1 𝑘
• Shear in the 𝑥-direction by factor 𝑘: ¯ ° (slides points horizontally by an amount
0 1
proportional to their 𝑦-coordinate, leaving the 𝑦-coordinate itself unchanged)

Given a 2 × 2 matrix, its geometric meaning can be identified by matching its pattern against the
0 −1
forms above; for example, ¯ ° Matches the rotation form with cos𝜃 = 0, sin𝜃 = 1, i.e., a
1 0
90∘ Rotation.

B.9.4 Composite transformations

If 𝑇# : 𝑉 → 𝑊 and 𝑇% : 𝑊 → 𝑈 are linear transformations, the composite 𝑇% ∘ 𝑇# : 𝑉 → 𝑈 is defined
by (𝑇% ∘ 𝑇# )(𝑣⃗) = 𝑇% •𝑇# (𝑣⃗)‚: apply 𝑇# First, then feed the result into 𝑇% . If 𝐴# And 𝐴% Are the
standard matrices of 𝑇# , 𝑇% Respectively, the standard matrix of 𝑇% ∘ 𝑇# Is simply 𝐴% 𝐴# (matrix
multiplication in that order), a fact that follows directly from associativity of matrix
multiplication applied to 𝐴% (𝐴# 𝑥⃗).
0 −1
Worked example B.20. Let 𝑇# Be a 90∘ Rotation, 𝐴# = ¯ °, and 𝑇% Be reflection across the
1 0
1 0
𝑥-axis, 𝐴% = ¯ °. Find the standard matrix for 𝑇% ∘ 𝑇# (rotate first, then reflect).
0 −1
1 0 0 −1 (1)(0) + (0)(1) (1)(−1) + (0)(0) 0 −1
𝐴% 𝐴# = ¯ °¯ °=Ä Å=¯ °
0 −1 1 0 (0)(0) + (−1)(1) (0)(−1) + (−1)(0) −1 0

B.9.5 Kernel, range, rank, nullity, Rank-Nullity Theorem, one-to-one

• Kernel: ker(𝑇) = {𝑣⃗ ∈ 𝑉: 𝑇(𝑣⃗) = 0̃⃗}, every input that 𝑇 crushes down to the zero vector.
The kernel is always a subspace of 𝑉.

• Range: range(𝑇) = {𝑇(𝑣⃗): 𝑣⃗ ∈ 𝑉}, every possible output 𝑇 can produce. The range is
always a subspace of 𝑊.

• Rank: rank(𝑇) = dim•Range(𝑇)‚.

• Nullity: nullity(𝑇) = dim•Ker(𝑇)‚.

• Rank-Nullity Theorem: for 𝑇: 𝑉 → 𝑊 with 𝑉 finite-dimensional, rank(𝑇) +

nullity(𝑇) = dim(𝑉). Intuitively, every dimension of the domain either survives into the
 range or gets collapsed into the kernel, and this theorem says those two counts must add
back up to the domain’s full dimension.

• One-to-one (injective): 𝑇 is one-to-one if distinct inputs always give distinct outputs;

equivalently, 𝑇 is one-to-one exactly when ker(𝑇) = {0̃⃗} (nothing but the zero vector
gets crushed to zero).

Worked example B.21. For 𝑇(𝑥, 𝑦, 𝑧) = (𝑥 + 𝑦, 𝑦 + 𝑧) (a map ℝ/ → ℝ% ), find the kernel,

nullity, rank, and check one-to-one-ness.

Step 1: Find ker(𝑇): solve 𝑥 + 𝑦 = 0 and 𝑦 + 𝑧 = 0. From the first, 𝑥 = −𝑦; from the second,
𝑧 = −𝑦. So every kernel vector has the form (−𝑦, 𝑦, −𝑦) = 𝑦(−1,1, −1) For any 𝑦. So
ker(𝑇) = span{(−1,1, −1)}, a 1-dimensional subspace. Nullity = 1.

Step 2: Since dim(𝑉) = dim(ℝ/ ) = 3, the Rank-Nullity Theorem gives rank(𝑇) = 3 − 1 = 2.

Step 3: Since ker(𝑇) ≠ {0̃⃗} (it contains nonzero vectors like (−1,1, −1)), 𝑇 is not one-to-one.

B.10 Eigenvalues, Eigenvectors, and Diagonalization

B.10.1 Definitions
For a square matrix 𝐴, a nonzero vector 𝑣⃗ Is an eigenvector of 𝐴 with corresponding eigenvalue
𝜆 (lambda, a scalar) if:

𝐴𝑣⃗ = 𝜆𝑣⃗

In words: multiplying 𝑣⃗ By 𝐴 doesn’t change its direction (only possibly its length and sign); 𝐴
simply stretches or shrinks 𝑣⃗ By the factor 𝜆. The requirement that 𝑣⃗ Be nonzero is essential,
without it, every 𝜆 would trivially “work” for 𝑣⃗ = 0̃⃗, and the definition would carry no
information about 𝐴.

B.10.2 The characteristic polynomial

Rearranging 𝐴𝑣⃗ = 𝜆𝑣⃗ As 𝐴𝑣⃗ − 𝜆𝑣⃗ = 0̃⃗, then (𝐴 − 𝜆𝐼)𝑣⃗ = 0̃⃗ (factoring out 𝑣⃗, and inserting the
identity matrix 𝐼 so both terms are proper matrix-vector products), a nonzero solution 𝑣⃗ Is
needed, since eigenvectors are nonzero by definition. A homogeneous system (𝐴 − 𝜆𝐼)𝑣⃗ = 0̃⃗
Has a nonzero solution exactly when the coefficient matrix is singular, i.e., det(𝐴 − 𝜆𝐼) = 0.
This equation, viewed as a polynomial in 𝜆, is called the characteristic polynomial, and its roots
are exactly the eigenvalues of 𝐴.
4 1
Worked example B.22. Find the eigenvalues and eigenvectors of 𝐴 = ¯ °.
2 3
4−𝜆 1
Step 1: Form 𝐴 − 𝜆𝐼 = ¯ °.
2 3−𝜆
Step 2: Compute the determinant (characteristic polynomial):

Det(𝐴 − 𝜆𝐼) = (4 − 𝜆)(3 − 𝜆) − (1)(2)

Expand (4 − 𝜆)(3 − 𝜆) (using P9 twice, the “FOIL” expansion): 12 − 4𝜆 − 3𝜆 + 𝜆% = 𝜆% −

7𝜆 + 12. So:

Det(𝐴 − 𝜆𝐼) = 𝜆% − 7𝜆 + 12 − 2 = 𝜆% − 7𝜆 + 10

Step 3: Set equal to zero and factor: 𝜆% − 7𝜆 + 10 = (𝜆 − 5)(𝜆 − 2) = 0, giving eigenvalues

𝜆# = 5, 𝜆% = 2.

Step 4: Find the eigenvector for 𝜆# = 5: solve (𝐴 − 5𝐼)𝑣⃗ = 0̃⃗:

4−5 1 𝑥 −1 1 𝑥
¯ ° ¯𝑦° = ¯ ° ¯ ° = 0̃⃗
2 3−5 2 −2 𝑦
The first row gives −𝑥 + 𝑦 = 0, i.e., 𝑦 = 𝑥. So the eigenvector is any nonzero multiple of (1,1).

Step 5: Find the eigenvector for 𝜆% = 2: solve (𝐴 − 2𝐼)𝑣⃗ = 0̃⃗:

2 1 𝑥
¯ ° ¯ ° = 0̃⃗
2 1 𝑦
The first row gives 2𝑥 + 𝑦 = 0, i.e., 𝑦 = −2𝑥. So the eigenvector is any nonzero multiple of
(1, −2).

B.10.3 Diagonalization and 𝐴" = 𝑃𝐷 " 𝑃#$

If 𝐴 (an 𝑛 × 𝑛 matrix) has 𝑛 linearly independent eigenvectors, it is diagonalizable: it can be
written as 𝐴 = 𝑃𝐷𝑃"# , where 𝐷 is the diagonal matrix of eigenvalues (in some chosen order
along the diagonal), and 𝑃 is the matrix whose columns are the corresponding eigenvectors (in
the matching order).

Why this is useful: computing powers efficiently. Since 𝐴 = 𝑃𝐷𝑃 "# :

𝐴' = (𝑃𝐷𝑃"# )(𝑃𝐷𝑃"# ) ⋯ (𝑃𝐷𝑃"# ) (𝑛 times)

Every interior 𝑃"# 𝑃 pair cancels to 𝐼 (since 𝑃"# 𝑃 = 𝐼 by definition of inverse), leaving:

𝐴' = 𝑃𝐷' 𝑃"#

And 𝐷' Is easy to compute directly: for a diagonal matrix, raising it to a power just means
raising each diagonal entry to that power, since off-diagonal zeros stay zero no matter how many
times the matrix is multiplied by itself. This turns an otherwise expensive repeated matrix
multiplication into three cheap steps, diagonalize once, raise a diagonal matrix to a power, then
undo the change of basis.
 4 1
Worked example B.23. Using 𝐴 = ¯ ° From Worked example B.22 (eigenvalues 5,2 with
2 3
eigenvectors (1,1) And (1, −2)), compute 𝐴/ .

Step 1: Build 𝑃 (eigenvectors as columns) and 𝐷 (eigenvalues on the diagonal, matching column
order):
1 1 5 0
𝑃=¯ °, 𝐷=¯ °
1 −2 0 2
Step 2: Find 𝑃"# . Using the 2 × 2 shortcut (Section B.4.2): det(𝑃) = (1)(−2) − (1)(1) = −3.
So:
1 −2 −1 2⁄3 1⁄3
𝑃"# = ¯ °=Ä Å
−3 −1 1 1⁄3 − 1⁄3
/
Step 3: Compute 𝐷/ = ¯5 0 ° = ¯125 0
°.
0 2/ 0 8
1 1 125 0 125 8
Step 4: Compute 𝐴/ = 𝑃𝐷/ 𝑃 "# . First, 𝑃𝐷/ = ¯ °¯ °=¯ °.
1 −2 0 8 125 −16
125 8 2⁄3 1⁄3
Then (𝑃𝐷/ )𝑃"# = ¯ °Ä Å:
125 −16 1⁄3 − 1⁄3
Row 1, Col 1: 125(2⁄3) + 8(1⁄3) = 250⁄3 + 8⁄3 = 258⁄3 = 86

Row 1, Col 2: 125(1⁄3) + 8(− 1⁄3) = 125⁄3 − 8⁄3 = 117⁄3 = 39

Row 2, Col 1: 125(2⁄3) + (−16)(1⁄3) = 250⁄3 − 16⁄3 = 234⁄3 = 78

Row 2, Col 2: 125(1⁄3) + (−16)(− 1⁄3) = 125⁄3 + 16⁄3 = 141⁄3 = 47

86 39
𝐴/ = ¯ °
78 47
B.10.4 Proof: similar matrices share the same eigenvalues
Definition. Matrices 𝐴 and 𝐵 are similar if there exists an invertible matrix 𝑃 with 𝐵 = 𝑃"# 𝐴𝑃.

Claim: if 𝐴 and 𝐵 are similar, they have the same characteristic polynomial, and hence the same
eigenvalues.

Proof. Suppose 𝐵 = 𝑃 "# 𝐴𝑃 for some invertible 𝑃. Then:

Det(𝐵 − 𝜆𝐼) = det(𝑃"# 𝐴𝑃 − 𝜆𝐼)

Since 𝐼 = 𝑃"# 𝑃 (definition of inverse), insert 𝐼 = 𝑃"# 𝑃 so that 𝜆𝐼 = 𝑃"# (𝜆𝐼)𝑃. Then:

𝐵 − 𝜆𝐼 = 𝑃 "# 𝐴𝑃 − 𝑃"# (𝜆𝐼)𝑃 = 𝑃 "# (𝐴 − 𝜆𝐼)𝑃

(factoring 𝑃"# ( ⋯ )𝑃 out of both terms, a matrix-level version of the distributive law, P9). Taking
determinants, and using the general fact that det(𝑋𝑌𝑍) = det(𝑋)Det(𝑌)Det(𝑍) For square
matrices of matching size:

Det(𝐵 − 𝜆𝐼) = det(𝑃"# )Det(𝐴 − 𝜆𝐼)Det(𝑃)

#
Since det(𝑃 "# ) = fgh(?) (a standard determinant fact, following from det(𝑃"# )Det(𝑃) =
det(𝑃"# 𝑃) = det(𝐼) = 1), the factors det(𝑃"# ) And det(𝑃) Multiply to give 1 (P7: a number
times its multiplicative inverse). So:

Det(𝐵 − 𝜆𝐼) = det(𝐴 − 𝜆𝐼)

Since 𝐴 and 𝐵 have identical characteristic polynomials, their roots, the eigenvalues, are
identical as well.

B.11 Coordinate Vectors, Isomorphism, and Change of Basis

B.11.1 Coordinate vectors relative to a basis
Given a basis ℬ = {𝑏˜⃗# , … , 𝑏˜⃗' } for a vector space 𝑉, every vector 𝑣⃗ ∈ 𝑉 can be written uniquely
as a linear combination 𝑣⃗ = 𝑐# 𝑏˜⃗# + ⋯ + 𝑐' 𝑏˜⃗' (uniqueness follows from linear independence of
the basis: if two different sets of coefficients worked, subtracting the two combinations would
produce a nontrivial linear combination of the 𝑏˜⃗( Equal to 0̃⃗, contradicting independence). The
coordinate vector of 𝑣⃗ Relative to ℬ, written [𝑣⃗]ℬ , is the column vector of these coefficients:
[𝑣⃗]ℬ = (𝑐# , … , 𝑐' ).

Worked example B.24. Find the coordinate vector of 𝑝(𝑥) = 3 + 2𝑥 − 𝑥 % Relative to the basis
ℬ = {1, 𝑥, 𝑥 % } of 𝑃% .

Since 𝑝(𝑥) = 3(1) + 2(𝑥) + (−1)(𝑥 % ), the coefficients are read off directly: [𝑝]ℬ = (3,2, −1).
2 1
Worked example B.25. Find the coordinate vector of 𝐴 = ¯ ° Relative to the standard basis
0 3
of 𝑀%% From Section B.8.2.
1 0 0 1 0 0 0 0
Since 𝐴 = 2 ¯ °+1¯ °+ 0¯ ° +3¯ °, the coordinate vector is (2,1,0,3).
0 0 0 0 1 0 0 1
B.11.2 Isomorphism of vector spaces
Two vector spaces 𝑉 and 𝑊 are isomorphic if there exists a linear transformation 𝑇: 𝑉 → 𝑊 that
is both one-to-one (Section B.9.5) and onto (every element of 𝑊 is hit by some element of 𝑉,
meaning range(𝑇) = 𝑊). Such a 𝑇 is called an isomorphism. Intuitively, isomorphic spaces are
“the same vector space wearing different notation”: every algebraic fact about one transfers
directly to the other, since 𝑇 pairs up their elements in a way that respects both addition and
scalar multiplication. The coordinate-vector map from Section B.11.1 is itself an isomorphism
between any 𝑛-dimensional vector space and ℝ' , which is why 𝑃% (dimension 3) behaves
exactly like ℝ/ , and 𝑀%% (dimension 4) behaves exactly like ℝ. , once coordinates relative to a
fixed basis are in hand.

B.11.3 Transition matrix between two bases

Given two bases ℬ = {𝑏˜⃗# , 𝑏˜⃗% } and 𝒞 = {𝑐⃗# , 𝑐⃗% } for the same vector space, the transition matrix
from ℬ to 𝒞, written 𝑃ℬ→𝒞 , converts coordinate vectors: [𝑣⃗ ]𝒞 = 𝑃ℬ→𝒞 [𝑣⃗]ℬ . To build it: express
each vector of ℬ as a coordinate vector relative to 𝒞, and use these as the columns of 𝑃ℬ→𝒞 .

Worked example B.26. Let ℬ = {(1,0), (0,1)} (the standard basis) and 𝒞 = {(1,1), (1, −1)}, both
bases of ℝ% . Find the transition matrix from ℬ to 𝒞, and use it to find the coordinates of 𝑣⃗ =
(3,1) Relative to 𝒞.

Step 1: Express each vector of ℬ in terms of 𝒞. Solving (1,0) = 𝑐# (1,1) + 𝑐% (1, −1) Gives 𝑐# +
𝑐% = 1 and 𝑐# − 𝑐% = 0, so 𝑐# = 𝑐% = 1⁄2. So [(1,0)]𝒞 = (1⁄2 , 1⁄2).

Similarly, (0,1) = 𝑑# (1,1) + 𝑑% (1, −1) Gives 𝑑# + 𝑑% = 0, 𝑑# − 𝑑% = 1, so 𝑑# = 1⁄2 , 𝑑% =

− 1⁄2. So [(0,1)]𝒞 = (1⁄2 , − 1⁄2).
Step 2: Assemble these as columns:
1⁄2 1⁄2
𝑃ℬ→𝒞 = Ä Å
1⁄2 − 1⁄2
Step 3: Since ℬ is the standard basis, [𝑣⃗ ]ℬ = (3,1) Directly (coordinates relative to the standard
basis are just the vector’s own components). Compute:
1⁄2 1⁄2 3 1⁄2 (3) + 1⁄2 (1) 2
[𝑣⃗ ]𝒞 = Ä Å¯ ° = Ä Å=¯ °
1⁄2 ⁄
−1 2 1 ⁄
1 2 (3) ⁄
−1 2 (1) 1

Check: 2(1,1) + 1(1, −1) = (2,2) + (1, −1) = (3,1) = 𝑣⃗ ✓.

B.11.4 The matrix of a linear transformation relative to non-standard bases

If 𝑇: 𝑉 → 𝑊 is linear, ℬ = {𝑏˜⃗# , … , 𝑏˜⃗' } is a basis for 𝑉, and 𝒞 is a basis for 𝑊, the matrix of 𝑇
relative to ℬ and 𝒞, written [𝑇]𝒞←ℬ , is built by applying 𝑇 to each basis vector of ℬ, then
expressing each result as a coordinate vector relative to 𝒞; these coordinate vectors become the
columns. This matrix satisfies [𝑇(𝑣⃗)]𝒞 = [𝑇]𝒞←ℬ [𝑣⃗ ]ℬ , the direct generalization of the standard-
matrix construction in Section B.9.2 (which is the special case where both ℬ and 𝒞 are standard
bases).

Worked example B.27. Let 𝑇: ℝ% → ℝ% Be 𝑇(𝑥, 𝑦) = (𝑥 + 𝑦, 2𝑥) (from Worked example B.17),
and let ℬ = 𝒞 = {(1,1), (1, −1)} (the same non-standard basis for both domain and codomain).
Find [𝑇]𝒞←ℬ .
Step 1: Apply 𝑇 to each vector of ℬ: 𝑇(1,1) = •1 + 1, 2(1)‚ = (2,2); 𝑇(1, −1) =
•1 + (−1), 2(1)‚ = (0,2).

Step 2: Express each result as coordinates relative to 𝒞 = {(1,1), (1, −1)}.

For (2,2): solving (2,2) = 𝑐# (1,1) + 𝑐% (1, −1) Gives 𝑐# + 𝑐% = 2, 𝑐# − 𝑐% = 2, so 𝑐# = 2, 𝑐% =

0. So [(2,2)]𝒞 = (2,0).

For (0,2): solving (0,2) = 𝑑# (1,1) + 𝑑% (1, −1) Gives 𝑑# + 𝑑% = 0, 𝑑# − 𝑑% = 2, so 𝑑# =

1, 𝑑% = −1. So [(0,2)]𝒞 = (1, −1).
Step 3: Assemble as columns:

[𝑇]𝒞←ℬ = ¯2 1 °
0 −1

PART C: Discrete Mathematics I (MATH 1130)

C.1 Propositional Logic
A proposition (or statement) is a declarative sentence that is either true or false, but not both, and
not neither. “Paris is the capital of France” is a proposition (true). “What time is it?” Is not a
proposition, it has no truth value, since a question cannot itself be judged true or false.

Propositions are represented with propositional variables: letters like 𝑝, 𝑞, 𝑟 standing in for a
whole statement. These are combined using logical connectives:

• Negation (¬𝑝, read “not 𝑝”): true exactly when 𝑝 is false.

• Conjunction (𝑝 ∧ 𝑞, read “𝑝 and 𝑞”): true only when both 𝑝 and 𝑞 are true.

• Disjunction (𝑝 ∨ 𝑞, read “𝑝 or 𝑞”): true when at least one of 𝑝, 𝑞 is true (this is the
inclusive or, true even if both are true).

• Exclusive or (𝑝 ⊕ 𝑞): true when exactly one of 𝑝, 𝑞 is true, but not both.

• Conditional / implication (𝑝 → 𝑞, read “if 𝑝 then 𝑞”): false only in the single case where
𝑝 is true and 𝑞 is false; true in every other case. 𝑝 is called the hypothesis (or antecedent),
𝑞 the conclusion (or consequent).

• Biconditional (𝑝 ↔ 𝑞, read “𝑝 if and only if 𝑞”): true exactly when 𝑝 and 𝑞 have the
same truth value (both true, or both false).
Truth table. A truth table is a table listing every possible combination of truth values for the
propositional variables involved, together with the resulting truth value of the compound
expression. For a compound proposition with 𝑛 variables, there are 2' Rows, since each variable
independently can be True or False, and by the multiplication principle (covered formally in
Section C.11) the total number of combinations is 2 × 2 × ⋯ × 2 = 2' .

Worked example C.1. Build the truth table for 𝑝 → 𝑞 and confirm its only false row.

𝑝 𝑞 𝑝→𝑞
T T T
T F F
F T T
F F T

Notice rows 3 and 4: when the hypothesis 𝑝 is false, the implication is automatically true
regardless of 𝑞. This trips people up at first; it is called vacuous truth: “if pigs can fly, then the
moon is made of cheese” is considered a true statement, purely because the hypothesis is false.
The definition is not claiming any causal connection; it is a bookkeeping convention that makes
the rest of logic, and later, proof by contradiction, work consistently.

C.1.1 Translating English to symbolic form

Worked example C.2. Translate “If it is raining and there is no umbrella at hand, then someone
will get wet” into symbolic form.

Let 𝑝 = “it is raining,” 𝑞 = “an umbrella is at hand,” 𝑟 = “someone will get wet.” The sentence
becomes:
(𝑝 ∧ ¬𝑞) → 𝑟

C.1.2 Tautology, contradiction, contingency

• A tautology is a compound proposition that is true in every row of its truth table,
regardless of the truth values of its variables, e.g., 𝑝 ∨ ¬𝑝 (always true: either 𝑝 holds, or
it doesn’t, there is no third option).

• A contradiction is false in every row, e.g., 𝑝 ∧ ¬𝑝 (can never both hold and not hold at
once).

• A contingency is neither: it is true in some rows and false in others (most ordinary
compound propositions, like 𝑝 → 𝑞 above, are contingencies).

Worked example C.3. Show that (𝑝 ∧ 𝑞) → 𝑝 is a tautology.

𝑝 𝑞 𝑝 ∧ 𝑞 (𝑝 ∧ 𝑞) → 𝑝
T T T T
 𝑝 𝑞 𝑝 ∧ 𝑞 (𝑝 ∧ 𝑞) → 𝑝
T F F T
F T F T
F F F T

Every row in the final column is T, so (𝑝 ∧ 𝑞) → 𝑝 is a tautology.

C.1.3 Logical equivalence

Two propositions 𝑃 and 𝑄 are logically equivalent, written 𝑃 ≡ 𝑄, if 𝑃 ↔ 𝑄 is a tautology;
equivalently, if 𝑃 and 𝑄 have identical truth tables (matching output in every row).

The standard laws of logical equivalence function as foundational, pre-proven identities that can
be cited by name, exactly the way P1–P9 function for algebra:

• Identity laws: 𝑝 ∧ 𝑇 ≡ 𝑝; 𝑝 ∨ 𝐹 ≡ 𝑝

• Domination laws: 𝑝 ∨ 𝑇 ≡ 𝑇; 𝑝 ∧ 𝐹 ≡ 𝐹

• Idempotent laws: 𝑝 ∨ 𝑝 ≡ 𝑝; 𝑝 ∧ 𝑝 ≡ 𝑝

• Double negation law: ¬(¬𝑝) ≡ 𝑝

• Commutative laws: 𝑝 ∨ 𝑞 ≡ 𝑞 ∨ 𝑝; 𝑝 ∧ 𝑞 ≡ 𝑞 ∧ 𝑝

• Associative laws: (𝑝 ∨ 𝑞) ∨ 𝑟 ≡ 𝑝 ∨ (𝑞 ∨ 𝑟); likewise for ∧

• Distributive laws: 𝑝 ∨ (𝑞 ∧ 𝑟) ≡ (𝑝 ∨ 𝑞) ∧ (𝑝 ∨ 𝑟); 𝑝 ∧ (𝑞 ∨ 𝑟) ≡ (𝑝 ∧ 𝑞) ∨ (𝑝 ∧ 𝑟)

• De Morgan’s laws: ¬(𝑝 ∧ 𝑞) ≡ ¬𝑝 ∨ ¬𝑞; ¬(𝑝 ∨ 𝑞) ≡ ¬𝑝 ∧ ¬𝑞

• Absorption laws: 𝑝 ∨ (𝑝 ∧ 𝑞) ≡ 𝑝; 𝑝 ∧ (𝑝 ∨ 𝑞) ≡ 𝑝

• Negation laws: 𝑝 ∨ ¬𝑝 ≡ 𝑇; 𝑝 ∧ ¬𝑝 ≡ 𝐹

• Conditional as disjunction: 𝑝 → 𝑞 ≡ ¬𝑝 ∨ 𝑞. This identity is the master key for

manipulating implications, since it converts them into ∧/∨/¬, where all the laws above
apply directly.

• Biconditional identity: 𝑝 ↔ 𝑞 ≡ (𝑝 → 𝑞) ∧ (𝑞 → 𝑝)

Worked example C.4 (proving equivalence by algebraic derivation, not a truth table). Show
¬(𝑝 → 𝑞) ≡ 𝑝 ∧ ¬𝑞.

Step 1: Rewrite the implication using the conditional-as-disjunction identity: 𝑝 → 𝑞 ≡ ¬𝑝 ∨ 𝑞.

Step 2: So ¬(𝑝 → 𝑞) ≡ ¬(¬𝑝 ∨ 𝑞).

Step 3: Apply De Morgan’s law to ¬(¬𝑝 ∨ 𝑞): ≡ ¬(¬𝑝) ∧ ¬𝑞.

Step 4: Apply the double negation law to ¬(¬𝑝): ≡ 𝑝 ∧ ¬𝑞.

So ¬(𝑝 → 𝑞) ≡ 𝑝 ∧ ¬𝑞. This matches intuition directly: “it’s not true that 𝑝 implies 𝑞” should
mean exactly “𝑝 happened, and yet 𝑞 didn’t”, that is the only scenario that disproves an
implication.

C.1.4 Converse, inverse, contrapositive

For an implication 𝑝 → 𝑞:

• The converse is 𝑞 → 𝑝 (swap the hypothesis and conclusion).

• The inverse is ¬𝑝 → ¬𝑞 (negate both).

• The contrapositive is ¬𝑞 → ¬𝑝 (swap and negate both).

Key fact: the original implication and its contrapositive are always logically equivalent: 𝑝 → 𝑞 ≡
¬𝑞 → ¬𝑝 (verifiable directly by truth table, or algebraically: ¬𝑞 → ¬𝑝 ≡ ¬(¬𝑞) ∨ ¬𝑝 ≡ 𝑞 ∨
¬𝑝 ≡ ¬𝑝 ∨ 𝑞 ≡ 𝑝 → 𝑞, using conditional-as-disjunction, double negation, and commutativity in
sequence). The converse and inverse are, in general, not equivalent to the original (they are,
however, equivalent to each other, since the inverse of 𝑝 → 𝑞 is exactly the contrapositive of the
converse 𝑞 → 𝑝).

Worked example C.5. For “If 𝑛 is divisible by 4, then 𝑛 is even,” state the converse, inverse, and
contrapositive, and note which are true.

Original (𝑝 → 𝑞, true): if 𝑛 divisible by 4, then 𝑛 even.

Converse (𝑞 → 𝑝): if 𝑛 is even, then 𝑛 is divisible by 4. False (e.g., 𝑛 = 6 is even but not
divisible by 4).

Inverse (¬𝑝 → ¬𝑞): if 𝑛 is not divisible by 4, then 𝑛 is not even. False (same counterexample:
𝑛 = 6 is not divisible by 4, but is even).

Contrapositive (¬𝑞 → ¬𝑝): if 𝑛 is not even, then 𝑛 is not divisible by 4. True (matches the
original, as guaranteed by the equivalence above).

C.1.5 Duals
The dual of a proposition built from ∧, ∨, 𝑇, 𝐹 (no negations required, no implications) is formed
by swapping every ∧↔∨ and every 𝑇 ↔ 𝐹. Duality is why the laws above come in matched
pairs; each law’s dual is also a valid law, so proving one half of a pair automatically certifies the
other.
Worked example C.6. Find the dual of (𝑝 ∧ 𝑇) ∨ (𝑞 ∧ 𝐹).
Swap ∧↔∨ and 𝑇 ↔ 𝐹: (𝑝 ∨ 𝐹) ∧ (𝑞 ∨ 𝑇).

C.2 Predicates and Quantifiers

A predicate is a statement whose truth value depends on one or more variables, e.g., 𝑃(𝑥): “𝑥 >
3” is not a proposition by itself, it has no fixed truth value until 𝑥 is specified, but becomes one
once 𝑥 is assigned a value from some domain (the set of allowed values for 𝑥).

• Universal quantifier (∀𝑥 𝑃(𝑥), “for all 𝑥, 𝑃(𝑥)”): true when 𝑃(𝑥) Holds for every
element 𝑥 in the domain.

• Existential quantifier (∃𝑥 𝑃(𝑥), “there exists 𝑥 such that 𝑃(𝑥)”): true when 𝑃(𝑥) Holds
for at least one element 𝑥 in the domain.

C.2.1 Negating quantified statements

¬•∀𝑥 𝑃(𝑥)‚ ≡ ∃𝑥 ¬𝑃(𝑥), ¬•∃𝑥 𝑃(𝑥)‚ ≡ ∀𝑥 ¬𝑃(𝑥)

These are the quantifier analogues of De Morgan’s laws (Section C.1.3): negating “all” turns it
into “there exists one that fails,” and negating “there exists” turns it into “all fail.”

Worked example C.7. Negate “For every integer 𝑛, there exists an integer 𝑚 such that 𝑚 > 𝑛”
(symbolically ∀𝑛 ∃𝑚 (𝑚 > 𝑛)).

Step 1: Push the negation past ∀𝑛: ¬•∀𝑛 ∃𝑚 (𝑚 > 𝑛)‚ ≡ ∃𝑛 ¬•∃𝑚 (𝑚 > 𝑛)‚.

Step 2: Push the negation past ∃𝑚: ≡ ∃𝑛 ∀𝑚 ¬(𝑚 > 𝑛).

Step 3: Negate the innermost predicate: ¬(𝑚 > 𝑛) ≡ 𝑚 ≤ 𝑛.

Final negation: ∃𝑛 ∀𝑚 (𝑚 ≤ 𝑛), “there exists an integer 𝑛 such that every integer 𝑚 satisfies
𝑚 ≤ 𝑛” (i.e., there is a largest integer). This final statement is false among the integers (there is
no largest integer), which correctly reflects that the original statement was true, a proposition and
its negation must always have opposite truth values.

C.3 Rules of Inference and Argument Validity

A rule of inference is a logically valid pattern for deriving a new true conclusion from given true
premises. These function as an additional layer of “axioms” for building formal proofs, on top of
the equivalence laws of Section C.1.3.

• Modus ponens: from 𝑝 → 𝑞 and 𝑝, conclude 𝑞.

• Modus tollens: from 𝑝 → 𝑞 and ¬𝑞, conclude ¬𝑝 (this is exactly why the contrapositive
equivalence of Section C.1.4 works as a proof strategy).

• Hypothetical syllogism: from 𝑝 → 𝑞 and 𝑞 → 𝑟, conclude 𝑝 → 𝑟.

 • Disjunctive syllogism: from 𝑝 ∨ 𝑞 and ¬𝑝, conclude 𝑞.

• Addition: from 𝑝, conclude 𝑝 ∨ 𝑞 (for any 𝑞).

• Simplification: from 𝑝 ∧ 𝑞, conclude 𝑝.

• Conjunction: from 𝑝 and 𝑞 separately, conclude 𝑝 ∧ 𝑞.

• Resolution: from 𝑝 ∨ 𝑞 and ¬𝑝 ∨ 𝑟, conclude 𝑞 ∨ 𝑟.

An argument is a sequence of premises followed by a conclusion; it is valid if the conclusion is
guaranteed true whenever all the premises are true, equivalently, if the conclusion follows from
the premises via a chain of rules of inference.
Worked example C.8. Determine whether the following argument is valid: “If the assignment is
finished early, it will be reviewed carefully. If it is reviewed carefully, it will be submitted with
confidence. The assignment was finished early. Therefore, it will be submitted with confidence.”

Let 𝑝 = “the assignment is finished early,” 𝑞 = “it is reviewed carefully,” 𝑟 = “it is submitted
with confidence.” Premises: 𝑝 → 𝑞, 𝑞 → 𝑟, 𝑝.

Step 1: From 𝑝 → 𝑞 and 𝑞 → 𝑟, apply hypothetical syllogism to derive 𝑝 → 𝑟.

Step 2: From 𝑝 → 𝑟 and 𝑝, apply modus ponens to derive 𝑟.

Since the conclusion 𝑟 follows via valid inference steps from the premises, the argument is valid.

C.4 Methods of Proof

• Direct proof: to prove 𝑝 → 𝑞, assume 𝑝 is true, and use a chain of logically valid
deductions to arrive at 𝑞.

• Proof by contrapositive (indirect proof): to prove 𝑝 → 𝑞, instead prove the equivalent

statement ¬𝑞 → ¬𝑝 (assume 𝑞 is false, deduce 𝑝 is false), valid because 𝑝 → 𝑞 ≡ ¬𝑞 →
¬𝑝 (Section C.1.4).

• Proof by contradiction: to prove a proposition 𝑝, assume ¬𝑝 is true, and derive a logical

contradiction (something of the form 𝑟 ∧ ¬𝑟). Since a contradiction can never actually be
true, the assumption ¬𝑝 must have been false, so 𝑝 is true.

Worked example C.9 (direct proof). Prove: if 𝑛 is an even integer, then 𝑛% Is even.

Proof. Assume 𝑛 is even. By definition of “even,” this means 𝑛 = 2𝑘 for some integer 𝑘. Then:

𝑛% = (2𝑘)% = 4𝑘 % = 2(2𝑘 % )

Using P5 (associativity) and P9 (distributivity) to expand and regroup. Since 2𝑘 % Is itself an

integer, 𝑛% Has the form 2 × (Some integer), which is exactly the definition of “even.” So 𝑛% Is
even.
Worked example C.10 (proof by contrapositive). Prove: if 𝑛% Is odd, then 𝑛 is odd.

The contrapositive of this statement is: if 𝑛 is even, then 𝑛% Is even, which was already proved
directly in Worked example C.9. Since the contrapositive is proven true, and 𝑝 → 𝑞 ≡ ¬𝑞 → ¬𝑝,
the original statement is proven true as well. This is exactly why the contrapositive method is
useful here: “if 𝑛% Is odd, then 𝑛 is odd” is awkward to attack head-on (there is no obvious
algebraic move that starts from “𝑛% Odd”), but its contrapositive starts from the much more
workable assumption “𝑛 even.”

Worked example C.11 (proof by contradiction). Prove that √2 Is irrational.

$
Proof. Assume, for contradiction, that √2 Is rational. By definition of rational, this means √2 = )
$
For some integers 𝑎, 𝑏 with 𝑏 ≠ 0, and, crucially, assume ) Is in lowest terms (i.e., 𝑎 and 𝑏 share
no common factor greater than 1; every rational number can be written this way, by dividing out
any common factor).
$#
Step 1: Square both sides: 2 = )# , so 𝑎 % = 2𝑏% .

Step 2: Since 𝑎% = 2𝑏% , 𝑎% Is even (it is 2 times an integer). This forces 𝑎 itself to be even: an
odd number squared is always odd (if 𝑎 = 2𝑚 + 1, then 𝑎% = 4𝑚% + 4𝑚 + 1 =
2(2𝑚% + 2𝑚) + 1, which has the form 2(Integer) + 1 and so is odd), so by the contrapositive of
that fact, an even square forces an even root. Hence 𝑎 = 2𝑐 for some integer 𝑐.

Step 3: Substitute back: (2𝑐)% = 2𝑏 % ⇒ 4𝑐 % = 2𝑏% ⇒ 𝑏 % = 2𝑐 % (dividing both sides by 2, using

P7). So 𝑏% Is even, and by the identical reasoning used on 𝑎 in Step 2, 𝑏 is even too.

Step 4: But now both 𝑎 and 𝑏 are even, meaning they share a common factor of 2. This
$
contradicts the assumption that ) Was in lowest terms.

Since assuming √2 Is rational leads to a contradiction, √2 Must be irrational.

C.5 Set Theory

A set is an unordered collection of distinct objects, called elements or members. The notation 𝑥 ∈
𝐴 means “𝑥 is an element of 𝐴,” and 𝑥 ∉ 𝐴 its negation. Sets can be described by roster notation
(listing elements, e.g., {1,2,3}) or set-builder notation ({𝑥: 𝑃(𝑥)}, “the set of all 𝑥 such that 𝑃(𝑥)
Holds”).

• Subset: 𝐴 ⊆ 𝐵 means every element of 𝐴 is also an element of 𝐵 (∀𝑥 (𝑥 ∈ 𝐴 → 𝑥 ∈ 𝐵)).

• Proper subset: 𝐴 ⊊ 𝐵 means 𝐴 ⊆ 𝐵 and 𝐴 ≠ 𝐵.

 • Empty set (⌀): the unique set with no elements. ⌀ ⊆ 𝐴 for every set 𝐴 (vacuously true, per
Section C.1: the implication “𝑥 ∈ ⌀ → 𝑥 ∈ 𝐴” has a hypothesis that is never true, so it is
automatically true for every 𝑥).

• Cardinality: |𝐴| Denotes the number of elements in a finite set 𝐴.

• Power set: 𝒫(𝐴), the set of all subsets of 𝐴 (including ⌀ and 𝐴 itself). If |𝐴| = 𝑛, then
|𝒫(𝐴)| = 2' (each element independently is either “in” or “out” of a given subset, the
same “each choice doubles the count” reasoning as the 2' Rows of a truth table in
Section C.1).

• Cartesian product: 𝐴 × 𝐵 = {(𝑎, 𝑏): 𝑎 ∈ 𝐴, 𝑏 ∈ 𝐵}, the set of all ordered pairs with first
coordinate from 𝐴 and second from 𝐵. |𝐴 × 𝐵| = |𝐴| ⋅ |𝐵|.

C.5.1 Set operations

• Union: 𝐴 ∪ 𝐵 = {𝑥: 𝑥 ∈ 𝐴 ∨ 𝑥 ∈ 𝐵}.

• Intersection: 𝐴 ∩ 𝐵 = {𝑥: 𝑥 ∈ 𝐴 ∧ 𝑥 ∈ 𝐵}.

• Difference: 𝐴 − 𝐵 (or 𝐴 ∖ 𝐵) = {𝑥: 𝑥 ∈ 𝐴 ∧ 𝑥 ∉ 𝐵}.

• Complement: 𝐴 (or 𝐴H ), relative to some universal set 𝑈, = {𝑥 ∈ 𝑈: 𝑥 ∉ 𝐴}.

C.5.2 Proving set identities

Method 1, element/membership (subset) argument. Prove 𝐴 = 𝐵 by proving 𝐴 ⊆ 𝐵 and 𝐵 ⊆ 𝐴
separately, each via a direct argument tracking an arbitrary element.

Worked example C.12. Prove 𝐴 ∩ (𝐵 ∪ 𝐶) = (𝐴 ∩ 𝐵) ∪ (𝐴 ∩ 𝐶) (the distributive law for sets)

using a membership argument.

Proof. Let 𝑥 be an arbitrary element.

(⊆) Suppose 𝑥 ∈ 𝐴 ∩ (𝐵 ∪ 𝐶). By definition of intersection, 𝑥 ∈ 𝐴 and 𝑥 ∈ 𝐵 ∪ 𝐶. By definition
of union, 𝑥 ∈ 𝐵 or 𝑥 ∈ 𝐶. So 𝑥 ∈ 𝐴 ∧ (𝑥 ∈ 𝐵 ∨ 𝑥 ∈ 𝐶), which, by the distributive law of logic
(Section C.1.3, applied here to the predicates “𝑥 ∈ 𝐴,” “𝑥 ∈ 𝐵,” “𝑥 ∈ 𝐶”), is logically equivalent
to (𝑥 ∈ 𝐴 ∧ 𝑥 ∈ 𝐵) ∨ (𝑥 ∈ 𝐴 ∧ 𝑥 ∈ 𝐶). This says 𝑥 ∈ (𝐴 ∩ 𝐵) Or 𝑥 ∈ (𝐴 ∩ 𝐶), i.e., 𝑥 ∈
(𝐴 ∩ 𝐵) ∪ (𝐴 ∩ 𝐶).

(⊇) Suppose 𝑥 ∈ (𝐴 ∩ 𝐵) ∪ (𝐴 ∩ 𝐶). Then 𝑥 ∈ 𝐴 ∩ 𝐵 or 𝑥 ∈ 𝐴 ∩ 𝐶, i.e., (𝑥 ∈ 𝐴 ∧ 𝑥 ∈ 𝐵) ∨

(𝑥 ∈ 𝐴 ∧ 𝑥 ∈ 𝐶). By the same distributive law run in reverse, this is equivalent to 𝑥 ∈ 𝐴 ∧
(𝑥 ∈ 𝐵 ∨ 𝑥 ∈ 𝐶), i.e., 𝑥 ∈ 𝐴 ∩ (𝐵 ∪ 𝐶).

Since each set is a subset of the other, 𝐴 ∩ (𝐵 ∪ 𝐶) = (𝐴 ∩ 𝐵) ∪ (𝐴 ∩ 𝐶).

Set identities are literally logical equivalences in disguise: every set-theoretic law (De Morgan’s
laws for sets, distributive laws, and so on) is the direct translation of the corresponding logical
equivalence from Section C.1.3, via the substitution “𝑥 ∈ (Set)” ↔ “predicate.” This is why set
identities can also be proven by:

Method 2, membership table. Analogous to a truth table: list every combination of “𝑥 is in / not
in” each of the sets involved, and compute whether 𝑥 ends up in the left-hand-side expression
versus the right-hand-side expression for every row (using 1 for “in,” 0 for “not in”).

Worked example C.13 (membership table for De Morgan’s law for sets). Prove 𝐴 ∪ 𝐵 = 𝐴 ∩ 𝐵.

𝐴 𝐵 𝐴∪𝐵 𝐴∪𝐵 𝐴 𝐵 𝐴∩𝐵

1 1 1 0 0 0 0
1 0 1 0 0 1 0
0 1 1 0 1 0 0
0 0 0 1 1 1 1

The columns 𝐴 ∪ 𝐵 And 𝐴 ∩ 𝐵 Match in every row, so the identity holds.

Method 3, derivation from known identities, exactly parallel to Worked example C.4’s algebraic
style: chain together already-established set laws (which mirror the logical equivalence laws one
for one) to transform one side into the other.

C.6 Functions
A function 𝑓: 𝐴 → 𝐵 assigns to each element 𝑎 of 𝐴 exactly one element 𝑓(𝑎) Of 𝐵. 𝐴 is the
domain (allowed inputs), 𝐵 is the codomain (the set the outputs are declared to live in), and the
range (or image) is {𝑓(𝑎): 𝑎 ∈ 𝐴} ⊆ 𝐵, the set of outputs actually achieved, the range can be a
proper subset of the codomain, when some elements of 𝐵 are never hit.

• Image of a set: for 𝑆 ⊆ 𝐴, 𝑓(𝑆) = {𝑓(𝑎): 𝑎 ∈ 𝑆}.

• Preimage of a set: for 𝑇 ⊆ 𝐵, 𝑓 "# (𝑇) = {𝑎 ∈ 𝐴: 𝑓(𝑎) ∈ 𝑇}.

• Injective (one-to-one): 𝑓 is injective if distinct inputs always give distinct outputs:

∀𝑎# , 𝑎% ∈ 𝐴 (𝑓(𝑎# ) = 𝑓(𝑎% ) → 𝑎# = 𝑎% ).

• Surjective (onto): 𝑓 is surjective if every element of the codomain is hit: ∀𝑏 ∈ 𝐵 ∃𝑎 ∈

𝐴 (𝑓(𝑎) = 𝑏), equivalently, range = codomain.

• Bijective: both injective and surjective, a perfect pairing between 𝐴 and 𝐵.

Worked example C.14. Let 𝑓: ℤ → ℤ be 𝑓(𝑛) = 2𝑛 + 1. Determine if 𝑓 is injective, surjective,

bijective.
Injective: suppose 𝑓(𝑛# ) = 𝑓(𝑛% ), i.e., 2𝑛# + 1 = 2𝑛% + 1. Subtracting 1 from both sides (P3)
gives 2𝑛# = 2𝑛% ; dividing by 2 (P7) gives 𝑛# = 𝑛% . So 𝑓 is injective.
8"#
Surjective: is every integer 𝑚 achieved as 2𝑛 + 1 for some integer 𝑛? Solving, 𝑛 = %
, but this
is only an integer when 𝑚 − 1 is even, i.e., 𝑚 is odd. Since 𝑚 = 2 (an even integer) has no
integer preimage, 𝑓 is not surjective.

Since 𝑓 fails surjectivity, 𝑓 is not bijective.

Composition. For 𝑓: 𝐴 → 𝐵 and 𝑔: 𝐵 → 𝐶, the composite (𝑔 ∘ 𝑓): 𝐴 → 𝐶 is defined by

(𝑔 ∘ 𝑓)(𝑎) = 𝑔•𝑓(𝑎)‚: apply 𝑓 first, then 𝑔.

Inverse of a bijection. If 𝑓: 𝐴 → 𝐵 is bijective, its inverse 𝑓 "# : 𝐵 → 𝐴 satisfies 𝑓 "# •𝑓(𝑎)‚ = 𝑎

for all 𝑎 ∈ 𝐴, and 𝑓•𝑓 "# (𝑏)‚ = 𝑏 for all 𝑏 ∈ 𝐵. Inverses exist precisely for bijections: injectivity
guarantees 𝑓 "# (𝑏) Is well-defined (only one candidate 𝑎 maps to any given 𝑏, so there is no
ambiguity in which value to assign), and surjectivity guarantees 𝑓 "# (𝑏) Is defined for every 𝑏 ∈
𝐵 (nothing is left without a preimage).

Floor and ceiling functions. ⌊𝑥⌋ (floor) is the largest integer ≤ 𝑥. ⌈𝑥⌉ (ceiling) is the smallest
integer ≥ 𝑥. Example: ⌊3.7⌋ = 3, ⌈3.7⌉ = 4, ⌊−3.2⌋ = −4 (careful with negatives: floor always
rounds down, toward more-negative, not toward zero).

Worked example C.15 (a floor property). Prove that ⌊𝑥 + 𝑛⌋ = ⌊𝑥⌋ + 𝑛 for any real 𝑥 and integer
𝑛.

Proof. By definition of floor, ⌊𝑥⌋ ≤ 𝑥 < ⌊𝑥⌋ + 1. Adding 𝑛 to all three parts of this inequality (a
valid step, since adding the same quantity to all parts of an inequality preserves the ordering, an
order property of the reals sitting alongside P1–P9):

⌊𝑥⌋ + 𝑛 ≤ 𝑥 + 𝑛 < ⌊𝑥⌋ + 𝑛 + 1

Since ⌊𝑥⌋ + 𝑛 is an integer (a sum of two integers), and 𝑥 + 𝑛 is sandwiched between this integer
and the next one up, by the definition of floor, ⌊𝑥 + 𝑛⌋ = ⌊𝑥⌋ + 𝑛.

C.7 Sequences and Summation

A sequence is an ordered list 𝑎# , 𝑎% , 𝑎/ , … (as defined more fully in Section A.1 of the earlier
guide). Here, the focus is on two different ways to specify one:

• Closed form: an explicit formula giving 𝑎' Directly in terms of 𝑛, e.g., 𝑎' = 3𝑛 + 1.

• Recursive form: a formula giving 𝑎' In terms of earlier terms, together with one or more
initial conditions (starting values), e.g., 𝑎# = 1, 𝑎' = 𝑎'"# + 3 for 𝑛 ≥ 2.

Worked example C.16. Convert the recursive sequence 𝑎# = 1, 𝑎' = 𝑎'"# + 3 to closed form.
Step 1: Compute a few terms: 𝑎# = 1, 𝑎% = 4, 𝑎/ = 7, 𝑎. = 10, …, each term is 3 more than
the last (an arithmetic sequence, with common difference 3).

Step 2: General pattern: 𝑎' = 𝑎# + 3(𝑛 − 1) = 1 + 3𝑛 − 3 = 3𝑛 − 2 (distributing via P9 and

combining via P1/P4).

Step 3: Verify: 𝑎# = 3(1) − 2 = 1 ✓, 𝑎% = 3(2) − 2 = 4 ✓.

C.7.1 Evaluating finite sums

Sigma notation ∑'(+# 𝑎( Was introduced in Part 1 of the earlier guide (Section 1.2). Several
standard closed-form sums are worth having on hand, since they show up constantly:
' ' '
𝑛(𝑛 + 1) 𝑛(𝑛 + 1)(2𝑛 + 1)
%
𝑟 '2# − 1
=𝑖 = , =𝑖 = , = 𝑟( = (𝑟 ≠ 1)
2 6 𝑟−1
(+# (+# (+&

Worked example C.17. Evaluate ∑#&&

(+# 𝑖 (the sum of the first 100 positive integers).

#&&(#&#) #&#&&
Using the formula: ∑#&&
(+# 𝑖 = %
= %
= 5050.

Worked example C.18. Evaluate ∑#&

(+#(2𝑖 + 3).

Step 1: Split the sum using linearity (justified by repeated use of P1 and P4 to regroup the sum,
and P9 to factor constants out): ∑#& #& #&
(+#(2𝑖 + 3) = 2 ∑(+# 𝑖 + ∑(+# 3.

#&(##)
Step 2: ∑#&
(+# 𝑖 = %
= 55, so 2∑𝑖 = 110. And ∑#&
(+# 3 = 3 × 10 = 30 (adding the constant 3
to itself 10 times).

Step 3: Total: 110 + 30 = 140.

C.8 Algorithms and Growth of Functions (Big-O)

An algorithm is a finite, well-defined sequence of steps for solving a problem or computation.
Big-O notation describes an upper bound on how an algorithm’s running time (or a function’s
size) grows as the input size 𝑛 grows, ignoring constant factors and lower-order terms, capturing
the “shape” of growth rather than exact values.

Definition. 𝑓(𝑛) Is 𝑂•𝑔(𝑛)‚ (“𝑓 is big-O of 𝑔”) if there exist positive constants 𝐶 and 𝑘 such
that |𝑓(𝑛)| ≤ 𝐶|𝑔(𝑛)| For all 𝑛 > 𝑘. In words: eventually (past some threshold 𝑘), 𝑓 never
exceeds a constant multiple of 𝑔.

Worked example C.19. Show that 𝑓(𝑛) = 3𝑛% + 5𝑛 + 2 is 𝑂(𝑛% ).

Step 1: Constants 𝐶, 𝑘 are needed such that 3𝑛% + 5𝑛 + 2 ≤ 𝐶𝑛% For all 𝑛 > 𝑘.
Step 2: For 𝑛 ≥ 1: since 𝑛 ≥ 1 means 𝑛 ≤ 𝑛% And 1 ≤ 𝑛% , each term can be bounded: 5𝑛 ≤ 5𝑛%
And 2 ≤ 2𝑛% (for 𝑛 ≥ 1). So:

3𝑛% + 5𝑛 + 2 ≤ 3𝑛% + 5𝑛% + 2𝑛% = 10𝑛%

Step 3: This holds for all 𝑛 ≥ 1, so taking 𝐶 = 10, 𝑘 = 1 satisfies the definition. Hence 𝑓(𝑛) =
𝑂(𝑛% ).

Common growth-rate hierarchy (from slowest to fastest growing, each strictly smaller order than
the next): 𝑂(1) < 𝑂(Log𝑛) < 𝑂(𝑛) < 𝑂(𝑛log𝑛) < 𝑂(𝑛% ) < 𝑂(𝑛/ ) < 𝑂(2' ) < 𝑂(𝑛!).

C.9 Divisibility and Modular Arithmetic

Divisibility. For integers 𝑎, 𝑏 with 𝑎 ≠ 0, 𝑎 divides 𝑏 (written 𝑎 ∣ 𝑏) if there exists an integer 𝑘
with 𝑏 = 𝑎𝑘.

The Division Algorithm. For any integer 𝑎 and positive integer 𝑑, there exist unique integers 𝑞
(the quotient) and 𝑟 (the remainder) such that 𝑎 = 𝑑𝑞 + 𝑟, with 0 ≤ 𝑟 < 𝑑.

Modular arithmetic. 𝑎 mod 𝑑 denotes the remainder 𝑟 from the division algorithm. Two integers
𝑎, 𝑏 are congruent modulo 𝑛, written 𝑎 ≡ 𝑏 (Mod 𝑛), if 𝑛 ∣ (𝑎 − 𝑏), equivalently, 𝑎 and 𝑏 leave
the same remainder when divided by 𝑛.

Worked example C.20 (proving a congruence property). Prove: if 𝑎 ≡ 𝑏 (Mod 𝑛) And 𝑐 ≡

𝑑 (Mod 𝑛), then 𝑎 + 𝑐 ≡ 𝑏 + 𝑑 (Mod 𝑛).

Proof. Since 𝑎 ≡ 𝑏 (Mod 𝑛), 𝑛 ∣ (𝑎 − 𝑏), meaning 𝑎 − 𝑏 = 𝑛𝑘# For some integer 𝑘# . Since 𝑐 ≡
𝑑 (Mod 𝑛), similarly 𝑐 − 𝑑 = 𝑛𝑘% For some integer 𝑘% . Adding these two equations (P1, P4):
(𝑎 − 𝑏) + (𝑐 − 𝑑) = 𝑛𝑘# + 𝑛𝑘%

Regroup the left side (P1, P4 again) as (𝑎 + 𝑐) − (𝑏 + 𝑑), and factor the right side (P9) as
𝑛(𝑘# + 𝑘% ):
(𝑎 + 𝑐) − (𝑏 + 𝑑) = 𝑛(𝑘# + 𝑘% )

Since 𝑘# + 𝑘% Is an integer, this says 𝑛 ∣ •(𝑎 + 𝑐) − (𝑏 + 𝑑)‚, i.e., 𝑎 + 𝑐 ≡ 𝑏 + 𝑑 (Mod 𝑛).

C.9.1 The Euclidean Algorithm

The greatest common divisor gcd(𝑎, 𝑏) Is the largest positive integer dividing both 𝑎 and 𝑏. The
Euclidean algorithm computes it efficiently using the key fact gcd(𝑎, 𝑏) = gcd(𝑏, 𝑎 mod 𝑏):
repeatedly replace the pair with (smaller number, remainder), until the remainder hits 0; the last
nonzero remainder is the gcd.

Worked example C.21. Compute gcd(252,105).

Step 1: 252 = 2(105) + 42 → new pair: (105,42).

Step 2: 105 = 2(42) + 21 → new pair: (42,21).

Step 3: 42 = 2(21) + 0 → remainder is 0, so the last nonzero remainder was 21.

Gcd(252,105) = 21

C.9.2 Base conversion

To convert a base-10 integer into base 𝑏: repeatedly divide by 𝑏, recording the remainders, then
read the remainders bottom to top.

Worked example C.22. Convert 77#& To binary (base 2).

77 = 2(38) + 1; 38 = 2(19) + 0; 19 = 2(9) + 1; 9 = 2(4) + 1; 4 = 2(2) + 0; 2 = 2(1) + 0;

1 = 2(0) + 1.

Reading remainders bottom-to-top: 1001101. So 77#& = 1001101% .

Check: 1001101% = 1(64) + 0(32) + 0(16) + 1(8) + 1(4) + 0(2) + 1(1) = 64 + 8 + 4 +

1 = 77 ✓.

C.10 Mathematical Induction and Recursion

The Principle of Mathematical Induction (weak induction). To prove a statement 𝑃(𝑛) Holds for
all integers 𝑛 ≥ 𝑛& (some starting point, often 1 or 0):

1. Base case: prove 𝑃(𝑛& ) Is true.

2. Inductive step: assume 𝑃(𝑘) Is true for some arbitrary 𝑘 ≥ 𝑛& (this assumption is called
the inductive hypothesis), and use it to prove 𝑃(𝑘 + 1) Is true.

If both hold, 𝑃(𝑛) Is true for every 𝑛 ≥ 𝑛& . Intuition: the base case establishes that the very first
domino falls; the inductive step establishes that every falling domino knocks over the next one;
together, every domino falls, no matter how far down the line.
'('2#)
Worked example C.23. Prove ∑'(+# 𝑖 = %
For all 𝑛 ≥ 1.

#(%)
Base case (𝑛 = 1): Left side: ∑#(+# 𝑖 = 1. Right side: %
= 1. They match. ✓

C(C2#)
Inductive step: Assume (inductive hypothesis) ∑C(+# 𝑖 = %
Holds for some arbitrary 𝑘 ≥ 1. It
(C2#)(C2%)
must be shown that ∑C2#
(+# 𝑖 = %
.
C2# C

= 𝑖 = ì= 𝑖í + (𝑘 + 1)
(+# (+#
Splitting off the last term, valid by P1/P4 regrouping the sum. By the inductive hypothesis,
substitute:
𝑘(𝑘 + 1)
= + (𝑘 + 1)
2
C(C2#)
Factor out (𝑘 + 1) (P9 in reverse, treating (𝑘 + 1) As a common factor of %
And (𝑘 + 1) =
%(C2#)
%
):

𝑘 𝑘 + 2 (𝑘 + 1)(𝑘 + 2)
= (𝑘 + 1) z + 1{ = (𝑘 + 1) ⋅ =
2 2 2
This matches exactly the target expression for 𝑛 = 𝑘 + 1.
'('2#)
By the Principle of Mathematical Induction, ∑'(+# 𝑖 = %
For all 𝑛 ≥ 1.

Strong induction differs only in the inductive step: instead of assuming just 𝑃(𝑘), assume
𝑃(𝑛& ), 𝑃(𝑛& + 1), … , 𝑃(𝑘) All hold (every case up through 𝑘), and use any or all of them to
prove 𝑃(𝑘 + 1). This is essential when 𝑃(𝑘 + 1)’S proof needs to reach further back than just
the immediately preceding case.

Worked example C.24 (strong induction). Prove every integer 𝑛 ≥ 2 can be written as a product
of primes.

Base case (𝑛 = 2): 2 is itself prime, hence trivially “a product of primes” (a product of one
prime). ✓

Inductive step: Assume every integer 𝑗 with 2 ≤ 𝑗 ≤ 𝑘 can be written as a product of primes
(strong inductive hypothesis). Consider 𝑛 = 𝑘 + 1. Either:

• 𝑘 + 1 is prime, in which case it is trivially a product of primes (itself), done; or

• 𝑘 + 1 is not prime, meaning 𝑘 + 1 = 𝑎𝑏 for integers 𝑎, 𝑏 with 2 ≤ 𝑎, 𝑏 ≤ 𝑘 (neither

factor can be 1 or 𝑘 + 1 itself, by definition of “not prime”). Since both 𝑎 and 𝑏 fall in
the range 2 through 𝑘, the strong inductive hypothesis applies to both of them: each is a
product of primes. So 𝑘 + 1 = 𝑎𝑏 is also a product of primes (the combined product of
𝑎’s primes and 𝑏’s primes).

Either way, 𝑘 + 1 is a product of primes. By strong induction, every integer 𝑛 ≥ 2 is a product of

primes. Notice that weak induction genuinely could not handle this proof: knowing 𝑃(𝑘)
Alone tells nothing about a possible factor 𝑎 that might be much smaller than 𝑘; the whole range
of prior cases needs to be available, which only strong induction supplies.
Recursion, structurally identical to a recursively-defined sequence (Section C.7), defines an
object in terms of smaller instances of itself, plus a base case that terminates the self-reference. A
recursive algorithm is a procedure that calls itself on a smaller input, e.g., computing 𝑛! Via 0! =
1 (base case), 𝑛! = 𝑛 ⋅ (𝑛 − 1)! For 𝑛 ≥ 1 (recursive case).

C.11 Counting
• Sum Rule: if a task can be done in 𝑛# Ways or 𝑛% Ways (and these ways don’t overlap), it
can be done in 𝑛# + 𝑛% Ways.

• Product Rule: if a task consists of a first step done in 𝑛# Ways, followed by a second step
(independent of the first) done in 𝑛% Ways, the whole task can be done in 𝑛# × 𝑛% Ways.

Worked example C.25. A password consists of 3 letters followed by 2 digits. How many possible
passwords are there?

By the Product Rule (choosing each of the 5 positions independently): 26 × 26 × 26 × 10 ×

10 = 26/ × 10% = 17576 × 100 = 1,757,600.

C.11.1 Permutations and combinations

• Permutation: an ordered arrangement of 𝑟 objects chosen from 𝑛 distinct objects, counted
'!
by 𝑃(𝑛, 𝑟) = ('"E)! (order matters).

• Combination: an unordered selection of 𝑟 objects from 𝑛 distinct objects, counted by

'!
𝐶(𝑛, 𝑟) = •'E‚ = E!('"E)! (order does not matter; the factor 𝑟! In the denominator accounts
for and removes the 𝑟! Different orderings of any one selected group, which the
permutation count would otherwise distinguish).

Worked example C.26. In how many ways can a committee of 3 people be chosen from a group
of 8?
0! 0×O×7
Since committee membership has no internal order, use combinations: •0/‚ = /!4! = /×%×# =
//7
7
= 56.

Distinguishable vs. Indistinguishable, with/without replacement. When objects are

indistinguishable (identical copies) or selections are made with replacement (an item can be
picked more than once), different formulas apply. For instance, the number of ways to choose 𝑟
items with repetition allowed from 𝑛 types is •'2E"#
E
‚ (a “stars and bars” style count), distinct
from the ordinary •'E‚ Used when each item can be picked at most once.

C.11.2 The Binomial Theorem

'
𝑛
(𝑥 + 𝑦) = = i j 𝑥 '"C 𝑦 C
'
𝑘
C+&
Worked example C.27. Expand (𝑥 + 𝑦). Using the Binomial Theorem.
4 4 4 4 4
z { 𝑥 .𝑦 & + z { 𝑥 /𝑦 # + z { 𝑥 %𝑦 % + z { 𝑥# 𝑦 / + z { 𝑥 & 𝑦 .
0 1 2 3 4
= 1 ⋅ 𝑥 . + 4𝑥 / 𝑦 + 6𝑥 % 𝑦 % + 4𝑥𝑦 / + 1 ⋅ 𝑦 . = 𝑥 . + 4𝑥 / 𝑦 + 6𝑥 % 𝑦 % + 4𝑥𝑦 / + 𝑦 .

C.11.3 Inclusion-Exclusion (up to three sets) and the Pigeonhole Principle

Inclusion-Exclusion (two sets): |𝐴 ∪ 𝐵| = |𝐴| + |𝐵| − |𝐴 ∩ 𝐵| (the overlap is subtracted once,
since adding |𝐴| + |𝐵| Double-counts every element in both).

Inclusion-Exclusion (three sets): |𝐴 ∪ 𝐵 ∪ 𝐶| = |𝐴| + |𝐵| + |𝐶| − |𝐴 ∩ 𝐵| − |𝐴 ∩ 𝐶| −

|𝐵 ∩ 𝐶| + |𝐴 ∩ 𝐵 ∩ 𝐶|. The triple-overlap term gets added back because it was subtracted out
three times by the pairwise terms, but only added in three times by the singles; the alternating
add/subtract pattern precisely restores each element to being counted exactly once.
Worked example C.28. In a class of 50 students, 30 take Math, 25 take Physics, 15 take
Chemistry, 12 take both Math and Physics, 8 take both Math and Chemistry, 5 take both Physics
and Chemistry, and 3 take all three. How many students take at least one of the three subjects?
|𝑀 ∪ 𝑃 ∪ 𝐶| = 30 + 25 + 15 − 12 − 8 − 5 + 3 = 70 − 25 + 3 = 48

Pigeonhole Principle. If 𝑛 items are placed into 𝑚 containers, and 𝑛 > 𝑚, then at least one
container holds more than one item. More generally, the generalized pigeonhole principle states
that at least one container holds at least ⌈𝑛/𝑚⌉ items.

Worked example C.29. Show that among any 13 people, at least two share a birth month.

There are 12 months (containers) and 13 people (items). Since 13 > 12, by the Pigeonhole
Principle, at least one month must contain at least two people, i.e., at least two people share a
birth month.

C.12 Basic Probability

For an equiprobable sample space 𝑆 (a finite set of equally-likely outcomes), the probability of
an event 𝐸 (a subset of 𝑆) is:
|𝐸|
𝑃(𝐸) =
|𝑆|

Worked example C.30. A standard deck has 52 cards. What is the probability of drawing a face
card (Jack, Queen, or King)?

There are 3 face-card ranks × 4 suits = 12 face cards (Product Rule, Section C.11). So
#% /
𝑃(Face card) = 4% = #/, simplified by dividing numerator and denominator by their gcd, 4, per
the Euclidean-algorithm logic of Section C.9.1.
C.13 Relations
A (binary) relation 𝑅 from a set 𝐴 to a set 𝐵 is a subset of 𝐴 × 𝐵 (Section C.5). When 𝐴 = 𝐵, 𝑅
is called a relation on 𝐴. The notation 𝑎 𝑅 𝑏 (or (𝑎, 𝑏) ∈ 𝑅) means 𝑎 is related to 𝑏.

• Reflexive: ∀𝑎 ∈ 𝐴 (𝑎 𝑅 𝑎), every element is related to itself.

• Irreflexive: ∀𝑎 ∈ 𝐴 (𝑎, 𝑎) ∉ 𝑅, no element is related to itself.

• Symmetric: ∀𝑎, 𝑏 •(𝑎 𝑅 𝑏) → (𝑏 𝑅 𝑎)‚, the relation is “two-way.”

• Antisymmetric: ∀𝑎, 𝑏 •(𝑎 𝑅 𝑏) ∧ (𝑏 𝑅 𝑎) → 𝑎 = 𝑏‚, the only way the relation can go both
directions is if it is the same element.

• Transitive: ∀𝑎, 𝑏, 𝑐 •(𝑎 𝑅 𝑏) ∧ (𝑏 𝑅 𝑐) → (𝑎 𝑅 𝑐)‚, relations “chain together.”

Worked example C.31. Let 𝑅 on {1,2,3} be 𝑅 = {(1,1), (1,2), (2,1), (2,2), (3,3)}. Classify 𝑅.

Reflexive? Need (1,1), (2,2), (3,3) All present; yes, all three are in 𝑅. Reflexive.

Symmetric? Check every pair: (1,2) ∈ 𝑅 requires (2,1) ∈ 𝑅; yes, present. All other pairs are self-
paired or already checked. Symmetric.

Antisymmetric? Both (1,2) And (2,1) Are in 𝑅, but 1 ≠ 2; this violates antisymmetry. Not
antisymmetric.

Transitive? Check: (1,2) ∈ 𝑅 and (2,1) ∈ 𝑅 requires (1,1) ∈ 𝑅; yes. (2,1) ∈ 𝑅 and (1,2) ∈ 𝑅
requires (2,2) ∈ 𝑅; yes. No other chains to check. Transitive.

Matrix representation. A relation 𝑅 on a finite set 𝐴 = {𝑎# , … , 𝑎' } can be represented by an

𝑛 × 𝑛 zero-one matrix 𝑀M , where the entry in row 𝑖, column 𝑗 is 1 if 𝑎( 𝑅 𝑎L , and 0 otherwise.

Digraph representation. A directed graph (digraph) representing 𝑅 has one vertex per element of
𝐴, with a directed edge (arrow) from 𝑎( To 𝑎L Whenever 𝑎( 𝑅 𝑎L .

PART D: Discrete Mathematics II (MATH 2230)

D.1 Cardinality of Infinite Sets
Two sets 𝐴 and 𝐵 have the same cardinality, written |𝐴| = |𝐵|, if there exists a bijection 𝑓: 𝐴 →
𝐵 (Section C.6): a way to pair up every element of 𝐴 with exactly one element of 𝐵, with none
left over on either side.

• A set is countably infinite if it has the same cardinality as ℕ (the natural numbers
{0,1,2,3, … }), meaning its elements can be listed in a single infinite sequence 𝑎# , 𝑎% , 𝑎/ , …
that eventually reaches (the “position of”) every element.
 • A set is countable if it is finite or countably infinite. A set that is not countable is
uncountable.

Worked example D.1. Show that the set of even integers 𝐸 = {0,2,4,6, … } has the same
cardinality as ℕ, even though 𝐸 is a proper subset of ℕ, a genuinely strange phenomenon with no
finite-set analogue: a proper subset of a finite set always has strictly fewer elements, but here a
proper subset matches the whole set exactly, in the cardinality sense.

Define 𝑓: ℕ → 𝐸 by 𝑓(𝑛) = 2𝑛.

Injective: if 𝑓(𝑛# ) = 𝑓(𝑛% ), then 2𝑛# = 2𝑛% , so 𝑛# = 𝑛% (dividing by 2, P7). ✓

Surjective: every even number 2𝑘 (for 𝑘 ∈ ℕ) is hit, since 𝑓(𝑘) = 2𝑘. ✓

Since 𝑓 is a bijection, |ℕ| = |𝐸|: the even integers are countably infinite, “just as many” as all
the naturals, in the cardinality sense.

D.1.1 Cantor’s Diagonalization Argument

Theorem. The set of real numbers between 0 and 1 is uncountable.

Proof (Cantor’s diagonalization). Suppose, for contradiction, that the reals in (0,1) Were
countable. Then they could all be listed in some sequence 𝑟# , 𝑟% , 𝑟/ , …, each written in its infinite
decimal expansion:

𝑟# = 0. 𝑑## 𝑑#% 𝑑#/ … 𝑟% = 0. 𝑑%# 𝑑%% 𝑑%/ … 𝑟/ = 0. 𝑑/# 𝑑/% 𝑑// … ⋮

Where 𝑑(L Is the 𝑗-th digit of 𝑟( .

Step 1: Construct a new number 𝑥 = 0. 𝑒# 𝑒% 𝑒/ … by choosing each digit 𝑒( To differ from the 𝑖-th
digit of 𝑟( (i.e., differ from 𝑑(( , the diagonal entry); for concreteness, say 𝑒( = 5 if 𝑑(( ≠ 5, and
𝑒( = 6 if 𝑑(( = 5 (avoiding the digits 0 and 9 sidesteps a technical ambiguity where some
decimals have two representations).

Step 2: This number 𝑥 is a real number in (0,1) (its digits are well-defined, and it is strictly
between 0 and 1). But 𝑥 cannot equal any 𝑟( In the supposedly-complete list: 𝑥 differs from 𝑟# In
the 1st digit, from 𝑟% In the 2nd digit, from 𝑟/ In the 3rd digit, and so on, 𝑥 differs from every 𝑟(
In at least the 𝑖-th decimal place.

Step 3: But 𝑥 ∈ (0,1), and the list 𝑟# , 𝑟% , … was assumed to contain every real number in (0,1).
This is a contradiction: 𝑥 is a real number in (0,1) That is not on the list.

Since the assumption that the reals in (0,1) Are countable leads to a contradiction, they must be
uncountable.
D.2 Advanced Counting: Recurrence Relations
A recurrence relation expresses each term of a sequence as a function of one or more previous
terms, together with initial conditions, already introduced informally in Section C.7; here actual
solution methods are developed.

D.2.1 Solving recurrence relations iteratively

Worked example D.2. Solve 𝑎' = 𝑎'"# + 2𝑛, with 𝑎& = 1, using iteration (repeatedly
substituting the recurrence into itself, tracking the pattern).

Step 1: Unroll a few steps: 𝑎# = 𝑎& + 2(1); 𝑎% = 𝑎# + 2(2) = 𝑎& + 2(1) + 2(2); 𝑎/ = 𝑎% +
2(3) = 𝑎& + 2(1) + 2(2) + 2(3).

Step 2: Spot the pattern: 𝑎' = 𝑎& + 2(1 + 2 + ⋯ + 𝑛) = 𝑎& + 2 ∑'(+# 𝑖 .

'('2#)
Step 3: Use the known closed form for ∑'(+# 𝑖 (Section C.7.1): 𝑎' = 1 + 2 ⋅ %
=1+
𝑛(𝑛 + 1) = 𝑛% + 𝑛 + 1.

Step 4: Verify: 𝑎& = 0 + 0 + 1 = 1 ✓; 𝑎# = 1 + 1 + 1 = 3, and directly 𝑎# = 𝑎& + 2(1) = 1 +

2 = 3 ✓.

D.2.2 Linear homogeneous recurrence relations with constant coefficients

A linear homogeneous recurrence relation of degree 𝑘 with constant coefficients has the form:

𝑎' = 𝑐# 𝑎'"# + 𝑐% 𝑎'"% + ⋯ + 𝑐C 𝑎'"C

Where 𝑐# , … , 𝑐C Are fixed constants (with 𝑐C ≠ 0). “Homogeneous” means there is no extra
standalone term added on (contrast with Section D.2.3 below).

Method: the characteristic equation. Guess a solution of the form 𝑎' = 𝑟 ' (for some constant 𝑟
to be determined) and substitute into the recurrence:

𝑟 ' = 𝑐# 𝑟 '"# + 𝑐% 𝑟 '"% + ⋯ + 𝑐C 𝑟 '"C

Dividing every term by 𝑟 '"C (P7, valid since 𝑟 ≠ 0 for a nontrivial solution) yields the
characteristic equation, a plain polynomial equation in 𝑟:

𝑟 C − 𝑐# 𝑟 C"# − 𝑐% 𝑟 C"% − ⋯ − 𝑐C = 0

Its roots are called characteristic roots. If the roots 𝑟# , … , 𝑟C Are all distinct, the general solution
is:

𝑎' = 𝛼# 𝑟#' + 𝛼% 𝑟%' + ⋯ + 𝛼C 𝑟C'

Where 𝛼# , … , 𝛼C Are constants determined by plugging in the initial conditions. If a root 𝑟

repeats with multiplicity 𝑚, its contribution to the general solution becomes (𝛽& + 𝛽# 𝑛 + ⋯ +
𝛽8"# 𝑛8"# )𝑟 ' Instead of a single term; extra terms with polynomial-in-𝑛 coefficients are needed
to keep the solutions linearly independent, directly analogous to how repeated roots in a
differential equation’s characteristic equation require an extra factor of 𝑡.

Worked example D.3. Solve the Fibonacci-style recurrence 𝑎' = 𝑎'"# + 𝑎'"% , with 𝑎& =
0, 𝑎# = 1 (this is, in fact, the Fibonacci sequence).

Step 1: Set up the characteristic equation. Substituting 𝑎' = 𝑟 ' : 𝑟 ' = 𝑟 '"# + 𝑟 '"% . Dividing by
𝑟 '"% : 𝑟 % = 𝑟 + 1, i.e., 𝑟 % − 𝑟 − 1 = 0.
#±√#2. #±√4
Step 2: Solve via the quadratic formula: 𝑟 = %
= %
. Two distinct roots:

1 + √5 1 − √5
𝑟# = (The golden ratio, 𝜙), 𝑟% =
2 2
Step 3: General solution: 𝑎' = 𝛼# 𝑟#' + 𝛼% 𝑟%' .

Step 4: Apply initial conditions. At 𝑛 = 0: 𝑎& = 𝛼# + 𝛼% = 0, so 𝛼% = −𝛼# . At 𝑛 = 1: 𝑎# =

𝛼# 𝑟# + 𝛼% 𝑟% = 1. Substituting 𝛼% = −𝛼# :

𝛼# 𝑟# − 𝛼# 𝑟% = 1 ⟹ 𝛼# (𝑟# − 𝑟% ) = 1
#2√4 #"√4 %√4 # #
Since 𝑟# − 𝑟% = %
− %
= %
= √5, this gives 𝛼# = , and so 𝛼% = − .
√4 √4

Step 5: Final closed form (Binet’s formula):

' '
1
1 + √5 1 1 − √5
𝑎' = q r − q r
√5 2 √5 2

Worked example D.4 (repeated root case). Solve 𝑎' = 4𝑎'"# − 4𝑎'"% , with 𝑎& = 1, 𝑎# = 4.

Step 1: Characteristic equation: 𝑟 % = 4𝑟 − 4 ⇒ 𝑟 % − 4𝑟 + 4 = 0 ⇒ (𝑟 − 2)% = 0. Repeated

root 𝑟 = 2 with multiplicity 2.

Step 2: General solution for a repeated root: 𝑎' = (𝛽& + 𝛽# 𝑛)(2)' .

Step 3: Apply initial conditions. At 𝑛 = 0: 𝑎& = 𝛽& ⋅ 1 = 1 ⇒ 𝛽& = 1. At 𝑛 = 1: 𝑎# =

(𝛽& + 𝛽# )(2) = 4 ⇒ (1 + 𝛽# )(2) = 4 ⇒ 1 + 𝛽# = 2 ⇒ 𝛽# = 1.

Step 4: Final solution: 𝑎' = (1 + 𝑛)2' . Check: 𝑎& = (1)(1) = 1 ✓; 𝑎# = (2)(2) = 4 ✓;

recurrence check at 𝑛 = 2: predicted 𝑎% = (3)(4) = 12, and directly 𝑎% = 4𝑎# − 4𝑎& = 16 −
4 = 12 ✓.
D.2.3 Nonhomogeneous recurrence relations
A linear nonhomogeneous recurrence relation has the form 𝑎' = 𝑐# 𝑎'"# + ⋯ + 𝑐C 𝑎'"C + 𝐹(𝑛),
where 𝐹(𝑛) Is a nonzero function of 𝑛 (the extra “forcing term”). The general solution is 𝑎' =
(Q) (X) (Q)
𝑎' + 𝑎' , where 𝑎' Is the general solution to the associated homogeneous recurrence (setting
(X)
𝐹(𝑛) = 0, solved as in Section D.2.2), and 𝑎' Is any one particular solution satisfying the full
nonhomogeneous equation.

Finding a particular solution. Guess a solution matching the “shape” of 𝐹(𝑛): if 𝐹(𝑛) Is a
polynomial of degree 𝑡, try a general polynomial of degree 𝑡 (or that polynomial times 𝑛 n , if the
pure polynomial guess collides with a homogeneous solution, where 𝑠 is the multiplicity needed
(X)
to avoid the collision); if 𝐹(𝑛) Is 𝑑 ⋅ 𝑟&' (exponential), try 𝑎' = 𝑐 ⋅ 𝑟&' (or 𝑐𝑛 ⋅ 𝑟&' If 𝑟& Is
already a characteristic root).

Worked example D.5. Solve 𝑎' = 2𝑎'"# + 3, with 𝑎& = 1.

Step 1: Solve the associated homogeneous equation 𝑎' = 2𝑎'"# : characteristic equation 𝑟 − 2 =
(Q)
0 ⇒ 𝑟 = 2, giving 𝑎' = 𝛼 ⋅ 2' .

Step 2: Guess a particular solution. Since 𝐹(𝑛) = 3 is a constant (a degree-0 polynomial), try the
(X)
constant guess 𝑎' = 𝐶. Substituting into the full recurrence: 𝐶 = 2𝐶 + 3 ⇒ −𝐶 = 3 ⇒ 𝐶 =
−3.

Step 3: General solution: 𝑎' = 𝛼 ⋅ 2' + (−3) = 𝛼 ⋅ 2' − 3.

Step 4: Apply the initial condition: 𝑎& = 1 ⇒ 𝛼 ⋅ 1 − 3 = 1 ⇒ 𝛼 = 4.

Step 5: Final solution: 𝑎' = 4 ⋅ 2' − 3 = 2'2% − 3. Check: 𝑎& = 4 − 3 = 1 ✓; 𝑎# Should be

2(1) + 3 = 5, and directly 2/ − 3 = 8 − 3 = 5 ✓.

D.3 Generating Functions

The (ordinary) generating function for a sequence 𝑎& , 𝑎# , 𝑎% , … is the formal power series,
structurally the same object as Section A.13’s power series, but here treated as a bookkeeping
device rather than something numbers are plugged into:
-

𝐺(𝑥) = = 𝑎' 𝑥 ' = 𝑎& + 𝑎# 𝑥 + 𝑎% 𝑥 % + ⋯

'+&

The core idea: a sequence’s entire infinite information content gets encoded into one single
algebraic expression, so that operations on sequences (shifting indices, adding sequences,
convolving them) correspond to ordinary algebraic operations on the generating functions
(multiplying by 𝑥, adding functions, multiplying functions).
Key building-block generating function. The geometric series identity (Section A.5) gives:
-
1
= 1 + 𝑥 + 𝑥% + 𝑥/ + ⋯ = = 𝑥'
1−𝑥
'+&

#
So #"3 Is the generating function for the constant sequence 𝑎' = 1 for all 𝑛.
#
Worked example D.6. Find the sequence represented by the generating function 𝐺(𝑥) = #"%3.

Substituting 2𝑥 in place of 𝑥 in the geometric series identity:

- -
1
= =(2𝑥)' = = 2' 𝑥 '
1 − (2𝑥)
'+& '+&

Reading off the coefficients, the sequence is 𝑎' = 2' .

Worked example D.7 (deriving the generating function determined by a given sequence). Find
the generating function for 𝑎' = 𝑛 + 1 (the sequence 1,2,3,4, …).
#
Step 1: Recall the generating function for the all-ones sequence is #"3 = ∑𝑥 ' .

Step 2: Differentiate both sides term by term with respect to 𝑥 (a legitimate operation on power
# #
series within their interval of convergence, Section A.13): the derivative of #"3 Is (#"3)# (via the
chain rule and power rule from Calc 1), and the derivative of ∑- ' -
'+& 𝑥 Is ∑'+# 𝑛 𝑥
'"#
.

Step 3: So:
- -
1
= = 𝑛 𝑥 '"# = =(𝑛 + 1) 𝑥 '
(1 − 𝑥)%
'+# '+&

Re-indexing by letting the new index be the old one minus 1. This is exactly the generating
function for 𝑎' = 𝑛 + 1:
1
𝐺(𝑥) =
(1 − 𝑥)%

D.3.1 Using generating functions to solve a recurrence relation

Worked example D.8. Use generating functions to solve 𝑎' = 3𝑎'"# , with 𝑎& = 2 (a recurrence
simple enough to double-check against the characteristic-equation method).

Step 1: Let 𝐺(𝑥) = ∑- '

'+& 𝑎' 𝑥 . Multiply the recurrence 𝑎' = 3𝑎'"# (valid for 𝑛 ≥ 1) by 𝑥
'

And sum over 𝑛 ≥ 1:

 - -

= 𝑎' 𝑥 = 3 = 𝑎'"# 𝑥 '

'

'+# '+#

Step 2: The left side is 𝐺(𝑥) − 𝑎& (the full series minus its 𝑛 = 0 term). The right side, re-
indexing with 𝑚 = 𝑛 − 1, is 3𝑥 ∑- 8
8+& 𝑎8 𝑥 = 3𝑥𝐺(𝑥).

Step 3: So 𝐺(𝑥) − 𝑎& = 3𝑥𝐺(𝑥), giving 𝐺(𝑥) − 3𝑥𝐺(𝑥) = 𝑎& , i.e., 𝐺(𝑥)(1 − 3𝑥) = 2 (using
𝑎& = 2), so:
2
𝐺(𝑥) =
1 − 3𝑥
#
Step 4: Match this against the known form #"E3 = ∑𝑟 ' 𝑥 ' (the same geometric-series building
block, with 𝑟 = 3 here): 𝐺(𝑥) = 2 ∑- ' ' '
'+& 3 𝑥 , so 𝑎' = 2 ⋅ 3 .

Step 5: Verify directly: 𝑎& = 2 ⋅ 1 = 2 ✓; recurrence check, 𝑎# Should be 3𝑎& = 6, and 2 ⋅ 3# =

6 ✓.

D.4 Advanced Inclusion-Exclusion

D.4.1 Counting onto functions
The number of onto (surjective) functions from a set of size 𝑛 to a set of size 𝑚 (with 𝑛 ≥ 𝑚) is
given by inclusion-exclusion applied to the complementary idea of “functions that miss at least
one element of the codomain”:
8
𝑚
(Number of onto functions) = =(−1)C i j (𝑚 − 𝑘)'
𝑘
C+&

Why: the total number of functions is 𝑚' (each of the 𝑛 domain elements independently picks 1
of 𝑚 codomain targets, by the Product Rule). Subtracting off functions that miss at least one
specific target (there are •8
#
‚(𝑚 − 1)' Such “miss-at-least-this-one” counts, summed over each
choice of target), then adding back the double-subtracted “miss at least two” cases, and so on,
reproduces precisely the alternating-sign inclusion-exclusion pattern from Section C.11.3, just
generalized past three sets to 𝑚 sets.

Worked example D.9. How many onto functions are there from a set of 4 elements to a set of 3
elements?
/
3 3 3 3 3
=(−1)C z { (3 − 𝑘). = z { (3). − z { (2). + z { (1). − z { (0).
𝑘 0 1 2 3
C+&

= 1(81) − 3(16) + 3(1) − 1(0) = 81 − 48 + 3 − 0 = 36

D.4.2 Derangements
A derangement of 𝑛 objects is a permutation in which no object ends up in its original position.
The number of derangements 𝐷' Is derived via inclusion-exclusion (treating “object 𝑖 is in its
own spot” as a “bad event” to be excluded), giving:
'
(−1)C
𝐷' = 𝑛! =
𝑘!
C+&

Worked example D.10. Compute 𝐷. (the number of derangements of 4 objects).

1 1 1 1 1 1 1 1
𝐷. = 4! z − + − + { = 24 z1 − 1 + − + {
0! 1! 2! 3! 4! 2 6 24
%. %. #% . # >
Combining using a common denominator of 24: i%. − %. + %. − %. + %.j = %.. So 𝐷. =
>
24 × %. = 9.

D.5 Equivalence Relations, Partitions, and Stirling Numbers

An equivalence relation on a set 𝐴 is a relation that is reflexive, symmetric, and transitive (all
three properties from Section C.13 simultaneously).

Equivalence class. For 𝑎 ∈ 𝐴, the equivalence class of 𝑎, written [𝑎], is {𝑥 ∈ 𝐴: 𝑥 𝑅 𝑎}, all
elements related to 𝑎.

Key theorem (relations to partitions). The equivalence classes of any equivalence relation on 𝐴
form a partition of 𝐴: a collection of nonempty, pairwise-disjoint subsets whose union is all of 𝐴.
Conversely, any partition of 𝐴 defines an equivalence relation (declare 𝑎 𝑅 𝑏 whenever 𝑎, 𝑏 land
in the same block of the partition). This is a genuine two-way correspondence: equivalence
relations and partitions are, structurally, the same idea viewed two ways.

Worked example D.11. Let 𝑅 on ℤ be 𝑎 𝑅 𝑏 ⇔ 𝑎 ≡ 𝑏 (Mod 3). Verify 𝑅 is an equivalence

relation, and describe its equivalence classes.

Reflexive: 𝑎 ≡ 𝑎 (Mod 3) Since 3 ∣ (𝑎 − 𝑎) = 3 ∣ 0, true for every integer. ✓

Symmetric: if 𝑎 ≡ 𝑏 (Mod 3), then 3 ∣ (𝑎 − 𝑏), so 𝑎 − 𝑏 = 3𝑘 for some integer 𝑘; then 𝑏 − 𝑎 =

−3𝑘 = 3(−𝑘), so 3 ∣ (𝑏 − 𝑎), i.e., 𝑏 ≡ 𝑎 (Mod 3) ✓ (using P3, the additive inverse axiom, to
negate both sides).

Transitive: if 𝑎 ≡ 𝑏 (Mod 3) And 𝑏 ≡ 𝑐 (Mod 3), then 𝑎 − 𝑏 = 3𝑘# And 𝑏 − 𝑐 = 3𝑘% For
integers 𝑘# , 𝑘% . Adding (P1, P4): (𝑎 − 𝑏) + (𝑏 − 𝑐) = 𝑎 − 𝑐 = 3𝑘# + 3𝑘% = 3(𝑘# + 𝑘% ) (P9),
so 3 ∣ (𝑎 − 𝑐), i.e., 𝑎 ≡ 𝑐 (Mod 3). ✓
All three hold, so 𝑅 is an equivalence relation. Its equivalence classes are [0] =
{… , −3,0,3,6, … }, [1] = {… , −2,1,4,7, … }, [2] = {… , −1,2,5,8, … }, exactly the three “remainder
classes” mod 3, which do partition all of ℤ.

Stirling numbers of the second kind. 𝑆(𝑛, 𝑘) Counts the number of ways to partition a set of 𝑛
elements into exactly 𝑘 nonempty, unlabeled subsets. (Contrast with onto functions, Section
D.4.1: onto functions count partitions into 𝑘 labeled groups, so 𝑆(𝑛, 𝑘) Relates to the onto-
#
function count by 𝑆(𝑛, 𝑘) = C! × (Number of onto functions from an 𝑛-set to a 𝑘-set), dividing
out the 𝑘! Ways to label the 𝑘 groups.)

Worked example D.12. Using the onto-function count from Worked example D.9 (which found
36 onto functions from a 4-set to a 3-set), find 𝑆(4,3).
36 36
𝑆(4,3) = = =6
3! 6
This counts the ways to partition a set of 4 elements into exactly 3 nonempty, unlabeled groups,
necessarily one group of size 2 and two groups of size 1; there are •.%‚ = 6 ways to choose which
pair goes together, matching.

D.6 Partial Orders

A relation 𝑅 on a set 𝐴 is a partial order if it is reflexive, antisymmetric, and transitive (contrast
with an equivalence relation, which swaps antisymmetric for symmetric). A set 𝐴 together with a
partial order is called a poset, written (𝐴, ≼).

• Total order: a partial order where, additionally, every pair of elements is comparable:
∀𝑎, 𝑏 ∈ 𝐴 (𝑎 ≼ 𝑏 ∨ 𝑏 ≼ 𝑎).

• Lexicographic order: the standard “dictionary” way of extending a total order on

individual symbols to a total order on strings or tuples of symbols, comparing the first
differing position.
• Lattice: a poset in which every pair of elements has both a unique least upper bound
(supremum) and a unique greatest lower bound (infimum) within the poset.
Comparability-related terms:

• Maximal element: an element 𝑎 with no element strictly above it (∄𝑏 (𝑎 ≺ 𝑏)); there can
be several maximal elements in a general poset.
• Minimal element: symmetric definition, no element strictly below it.

• Greatest element: a single element 𝑎 that is ≽ every other element (stronger than
maximal, since it must be comparable to, and dominate, everything).
 • Least element: symmetric definition.
• Bounded poset: one that has both a greatest and a least element.
Hasse diagram. A simplified visual representation of a finite poset: draw a vertex for each
element, positioned so that 𝑎 ≺ 𝑏 implies 𝑎 is drawn lower than 𝑏; connect 𝑎 to 𝑏 only when 𝑏
covers 𝑎 (meaning 𝑎 ≺ 𝑏 with nothing strictly in between); and omit all edges implied by
transitivity, since they would be redundant clutter, transitivity being assumed automatically.

Worked example D.13. Let 𝐴 = {1,2,3,4,6,12} (divisors of 12), with the partial order “divides”
(𝑎 ≼ 𝑏 ⇔ 𝑎 ∣ 𝑏). Identify the covering relations (the edges of the Hasse diagram) and the
greatest/least elements.

Step 1: Check divisibility pairs, skipping any implied purely by transitivity: 1 ∣ 2 (and nothing
strictly between them), 1 ∣ 3, 2 ∣ 4, 2 ∣ 6, 3 ∣ 6, 4 ∣ 12, 6 ∣ 12. Note 1 ∣ 4 is technically true but
is not a covering relation, since 1 ∣ 2 ∣ 4 already connects them transitively, so it is omitted from
the diagram.

Step 2: This produces a diamond-like structure: 1 at the bottom, connected up to 2 and 3; 2

connects up to 4 and 6; 3 connects up to 6; 4 and 6 both connect up to 12 at the top.

Step 3: Least element: 1 (divides everything). Greatest element: 12 (everything divides it). Since
both exist, this poset is bounded.

D.7 Graph Theory

A graph 𝐺 = (𝑉, 𝐸) Consists of a set 𝑉 of vertices (or nodes) and a set 𝐸 of edges, where each
edge connects a pair of vertices. In a simple graph, edges are unordered pairs (no direction), with
no repeated edges and no self-loops (an edge from a vertex to itself).
Terminology:

• Degree of a vertex 𝑣, written deg(𝑣): the number of edges incident to (touching) 𝑣.

• Handshaking Theorem: ∑`∈p deg (𝑣) = 2|𝐸| (every edge contributes exactly 2 to the
total degree count, once for each endpoint). This immediately implies the number of odd-
degree vertices in any graph must be even, since the total degree sum must be even, and
an odd number of odd terms would make the sum odd, a contradiction.

• Complete graph 𝐾' : every pair of the 𝑛 vertices is connected by an edge.

• Bipartite graph: vertices split into two groups, with edges only running between the
groups, never within one.
• Subgraph: a graph formed from a subset of a larger graph’s vertices and edges.
D.7.1 Adjacency and incidence matrices
Adjacency matrix 𝐴 of a graph with vertices 𝑣# , … , 𝑣' : an 𝑛 × 𝑛 matrix where entry (𝑖, 𝑗) Is the
number of edges between 𝑣( And 𝑣L (typically 0 or 1 for a simple graph).

Incidence matrix: for a graph with 𝑛 vertices and 𝑚 edges, an 𝑛 × 𝑚 matrix where entry (𝑖, 𝑗) Is
1 if vertex 𝑣( Is an endpoint of edge 𝑒L , and 0 otherwise.

D.7.2 Isomorphism
Two graphs 𝐺# = (𝑉# , 𝐸# ) And 𝐺% = (𝑉% , 𝐸% ) Are isomorphic if there is a bijection 𝑓: 𝑉# → 𝑉%
That preserves adjacency: {𝑢, 𝑣} ∈ 𝐸# ⇔ {𝑓(𝑢), 𝑓(𝑣)} ∈ 𝐸% . Necessary (but not sufficient)
conditions for isomorphism: same number of vertices, same number of edges, and matching
degree sequences (the sorted list of vertex degrees).

Worked example D.14. Determine whether the two graphs with edge sets 𝐸# =
{{1,2}, {2,3}, {3,4}, {4,1}} (a 4-cycle on vertices {1,2,3,4}) and 𝐸% = {{𝑎, 𝑏}, {𝑏, 𝑐}, {𝑐, 𝑑}, {𝑑, 𝑎}}
(a 4-cycle on vertices {𝑎, 𝑏, 𝑐, 𝑑}) are isomorphic.

Step 1: Both have 4 vertices and 4 edges. Degree sequences: every vertex in 𝐺# Has degree 2
(each appears in exactly 2 edges); same for 𝐺% . Matches so far.

Step 2: Try the bijection 𝑓(1) = 𝑎, 𝑓(2) = 𝑏, 𝑓(3) = 𝑐, 𝑓(4) = 𝑑. Check every edge of 𝐺#
Maps to an edge of 𝐺% : {1,2} → {𝑎, 𝑏} ✓ (in 𝐸% ); {2,3} → {𝑏, 𝑐} ✓; {3,4} → {𝑐, 𝑑} ✓; {4,1} →
{𝑑, 𝑎} ✓.

Since a bijection preserving adjacency exists, the graphs are isomorphic.

D.7.3 Connectivity, paths, circuits

A path is a sequence of vertices where consecutive vertices are connected by edges, with no
repeated edges. A circuit (or cycle) is a path that starts and ends at the same vertex. A graph is
connected if there is a path between every pair of vertices.
• Euler path: a path that uses every edge of the graph exactly once. Euler circuit: an Euler
path that starts and ends at the same vertex.
• Theorem (Euler circuits): a connected graph has an Euler circuit if and only if every
vertex has even degree.
• Theorem (Euler paths): a connected graph has an Euler path (but not necessarily a circuit)
if and only if it has exactly two vertices of odd degree (the path must start at one and end
at the other).
• Hamilton path/circuit: a path/circuit that visits every vertex exactly once. No simple
degree criterion exists for this in general; unlike Euler paths, Hamilton paths and circuits
are computationally hard to detect in general.
Worked example D.15. Does the graph with vertices {𝐴, 𝐵, 𝐶, 𝐷} and edges
{𝐴, 𝐵}, {𝐵, 𝐶}, {𝐶, 𝐷}, {𝐷, 𝐴}, {𝐴, 𝐶} have an Euler circuit or path?

Step 1: Compute degrees. Deg(𝐴): edges {𝐴, 𝐵}, {𝐷, 𝐴}, {𝐴, 𝐶} → degree 3. Deg(𝐵): edges
{𝐴, 𝐵}, {𝐵, 𝐶} → degree 2. Deg(𝐶): edges {𝐵, 𝐶}, {𝐶, 𝐷}, {𝐴, 𝐶} → degree 3. Deg(𝐷): edges
{𝐶, 𝐷}, {𝐷, 𝐴} → degree 2.

Step 2: Two vertices (𝐴, 𝐶) have odd degree (3), and two (𝐵, 𝐷) have even degree (2).

Step 3: Since exactly two vertices have odd degree, the graph has an Euler path (starting at 𝐴,
ending at 𝐶, or vice versa), but no Euler circuit (that requires all vertices to have even degree).

D.7.4 Dijkstra’s Algorithm

Dijkstra’s algorithm finds the shortest path (minimum total edge weight) from a single starting
vertex to every other vertex in a weighted graph (all edge weights non-negative). The core
procedure: maintain a running “best known distance” to every vertex (starting at 0 for the source,
∞ for everything else); repeatedly select the unvisited vertex with the smallest known distance,
mark it visited, and relax every edge out of it, updating a neighbor’s distance if going through the
current vertex would be shorter than its currently recorded distance. Repeat until every vertex is
visited.

Worked example D.16. Find the shortest path from 𝐴 to every other vertex in the graph with
edges (and weights) 𝐴-𝐵:4, 𝐴-𝐶:1, 𝐶-𝐵:2, 𝐵-𝐷:5, 𝐶-𝐷:8.

Step 1 (initialize): dist(𝐴) = 0, dist(𝐵) = ∞, dist(𝐶) = ∞, dist(𝐷) = ∞. Visit 𝐴 first (smallest

known distance).

Step 2 (relax edges from 𝐴): update dist(𝐵) = min(∞, 0 + 4) = 4; update dist(𝐶) =
min(∞, 0 + 1) = 1.

Step 3 (select next smallest unvisited): 𝐶 has distance 1, the smallest among unvisited {𝐵, 𝐶, 𝐷}.
Visit 𝐶.

Step 4 (relax edges from 𝐶): update dist(𝐵) = min(4, 1 + 2) = min(4,3) = 3 (improved!);
update dist(𝐷) = min(∞, 1 + 8) = 9.

Step 5 (select next smallest unvisited): 𝐵 has distance 3, smallest among {𝐵, 𝐷}. Visit 𝐵.

Step 6 (relax edges from 𝐵): update dist(𝐷) = min(9, 3 + 5) = min(9,8) = 8 (improved!).

Step 7 (select next): only 𝐷 remains, distance 8. Visit 𝐷. Done.

Final shortest distances from 𝐴: 𝐵: 3 (via 𝐴 → 𝐶 → 𝐵), 𝐶: 1 (direct), 𝐷: 8 (via 𝐴 → 𝐶 → 𝐵 →

𝐷).
D.7.5 Planarity, Euler’s Formula, Kuratowski’s Theorem
A graph is planar if it can be drawn in the plane with no edges crossing. For a connected planar
graph drawn with no crossings, Euler’s Formula relates the number of vertices 𝑣, edges 𝑒, and
faces 𝑓 (regions the drawing divides the plane into, including the unbounded outer region):

𝑣−𝑒+𝑓 =2

Worked example D.17. A connected planar graph has 6 vertices and 10 edges. How many faces
does it have?

From Euler’s formula: 6 − 10 + 𝑓 = 2 ⇒ 𝑓 = 2 − 6 + 10 = 6.

Consequence: an edge bound for planar graphs. For a connected simple planar graph with 𝑣 ≥ 3
vertices, 𝑒 ≤ 3𝑣 − 6. This is derived by combining Euler’s formula with the fact that each face is
bordered by at least 3 edges, and each edge borders at most 2 faces, giving 2𝑒 ≥ 3𝑓, then
substituting 𝑓 = 2 − 𝑣 + 𝑒 from Euler’s formula and solving the resulting inequality for 𝑒 using
P1–P9-style rearrangement. This gives a quick planarity test (a necessary, not sufficient,
condition): if 𝑒 > 3𝑣 − 6, the graph cannot be planar.
Kuratowski’s Theorem. A graph is planar if and only if it contains no subgraph that is a
“subdivision” of 𝐾4 (the complete graph on 5 vertices) or 𝐾/,/ (the complete bipartite graph with
two groups of 3). These two graphs are the fundamental “obstructions” to planarity; every non-
planar graph secretly contains one of them in disguise.

D.7.6 Graph Coloring

A proper coloring of a graph assigns colors to vertices such that no two adjacent vertices share a
color. The chromatic number 𝜒(𝐺) Is the minimum number of colors needed for a proper
coloring.
Worked example D.18 (scheduling via graph coloring). Five committees need meeting time slots.
Committees 1,2 share a member (can’t meet simultaneously); 2,3 share a member; 3,4 share a
member; 4,5 share a member; 5,1 share a member (a 5-cycle of conflicts). Find the minimum
number of time slots needed.
Step 1: Model this as a graph: vertices are committees, edges are shared-member conflicts,
forming the cycle 1-2-3-4-5-1.
Step 2: The chromatic number of a 5-cycle is needed. A cycle with an even number of vertices
needs only 2 colors (alternate around the cycle). But a cycle with an odd number of vertices (like
this 5-cycle) cannot be 2-colored: trying to alternate, by the time the cycle wraps back around,
the last vertex ends up adjacent to a same-colored neighbor, an odd number of alternations can
never return to the opposite color it started from.
Step 3: A 3-coloring works: color 1,2,3,4,5 as 𝑅, 𝐺, 𝑅, 𝐺, 𝐵; check: 1-2 (𝑅-𝐺) ✓ different, 2-3
(𝐺-𝑅) ✓, 3-4 (𝑅-𝐺) ✓, 4-5 (𝐺-𝐵) ✓, 5-1 (𝐵-𝑅) ✓ different.

So 𝜒(𝐺) = 3: three time slots are needed.

D.8 Trees
A tree is a connected graph with no circuits (equivalently, a connected graph with exactly 𝑣 − 1
edges for 𝑣 vertices, the minimum possible to stay connected). A rooted tree designates one
vertex as the root, giving every other vertex a well-defined parent (the neighbor one step closer
to the root) and children (neighbors one step farther). A vertex with no children is a leaf.

Binary tree: a rooted tree where every vertex has at most 2 children, typically distinguished as
“left child” and “right child.”

D.8.1 Tree traversals

Given a binary tree, three standard orders for visiting every vertex, defined recursively:
• Preorder: visit the root, then traverse the left subtree (preorder), then the right subtree
(preorder).
• Inorder: traverse the left subtree (inorder), then visit the root, then the right subtree
(inorder).
• Postorder: traverse the left subtree (postorder), then the right subtree (postorder), then
visit the root.

Worked example D.19. For the binary tree with root +, left child × (which itself has children 2
and 3), and right child 5, representing the expression (2 × 3) + 5, list the preorder, inorder, and
postorder traversals.

Preorder (root, left, right): +, ×, 2, 3, 5; this is exactly prefix notation: + × 235.

Inorder (left, root, right): 2, ×, 3, +, 5; this reconstructs (up to needing parentheses for clarity)
the infix notation started with: 2 × 3 + 5.

Postorder (left, right, root): 2, 3, ×, 5, +; this is exactly postfix (Reverse Polish) notation:
23 × 5 +, the form used internally by stack-based calculators, since it requires no parentheses
and can be evaluated left to right using a stack.

D.8.2 Huffman Coding

Huffman coding builds an optimal prefix code (a code where no codeword is a prefix of another,
guaranteeing unambiguous decoding) for a set of symbols with known frequencies, by repeatedly
combining the two least frequent items into a new combined node (whose frequency is their
sum), building a binary tree from the bottom up, until only one root node remains. Each symbol’s
final code is the sequence of left/right branches (typically 0/1) from the root down to that
symbol’s leaf.
Worked example D.20. Build a Huffman code for symbols with frequencies
𝐴: 5, 𝐵: 9, 𝐶: 12, 𝐷: 13, 𝐸: 16, 𝐹: 45.

Step 1: Combine the two smallest, 𝐴(5) And 𝐵(9), into a new node of frequency 14. Remaining:
𝐶(12), 𝐷(13), [𝐴𝐵](14), 𝐸(16), 𝐹(45).

Step 2: Combine the two smallest, 𝐶(12) And 𝐷(13), into a node of frequency 25. Remaining:
[𝐴𝐵](14), 𝐸(16), [𝐶𝐷](25), 𝐹(45).

Step 3: Combine the two smallest, [𝐴𝐵](14) And 𝐸(16), into a node of frequency 30.
Remaining: [𝐶𝐷](25), [𝐴𝐵𝐸 ](30), 𝐹(45).

Step 4: Combine the two smallest, [𝐶𝐷](25) And [𝐴𝐵𝐸 ](30), into a node of frequency 55.
Remaining: 𝐹(45), [𝐶𝐷𝐴𝐵𝐸 ](55).

Step 5: Combine the final two into the root, frequency 100.

Step 6: Reading branch directions (say, 0 for the smaller-frequency child at each merge, 1 for the
larger) from root to leaf gives each symbol’s Huffman code. Frequently-used symbols like 𝐹
(which merges in last, closest to the root) get short codes, while rare symbols like 𝐴, 𝐵 (merged
earliest, buried deepest) get longer codes. This is exactly why Huffman coding achieves
compression: it assigns fewer bits to the most common symbols.

D.8.3 Spanning Trees: DFS, BFS, Prim’s, and Kruskal’s Algorithms

A spanning tree of a connected graph 𝐺 is a subgraph that includes every vertex of 𝐺, uses only
edges from 𝐺, and is itself a tree (connected, no circuits).
Depth-first search (DFS) builds a spanning tree by exploring as far as possible along each branch
before backtracking: from the current vertex, move to an unvisited neighbor and recurse; only
backtrack when every neighbor has already been visited.
Breadth-first search (BFS) builds a spanning tree by exploring level by level: visit all neighbors
of the starting vertex first, then all of their unvisited neighbors, and so on, expanding outward in
“waves.”
For a weighted graph, a minimum spanning tree (MST) is a spanning tree whose total edge
weight is as small as possible.
Prim’s Algorithm builds an MST by growing a single connected tree: start with any one vertex,
and repeatedly add the cheapest edge that connects the current tree to a vertex not yet in the tree,
until all vertices are included.
Kruskal’s Algorithm builds an MST differently: sort all edges of the graph by weight, then
repeatedly add the next-cheapest edge overall, skipping any edge that would create a circuit
(connect two vertices already in the same growing component), until 𝑣 − 1 edges have been
added.

Worked example D.21. Find a minimum spanning tree for the graph with vertices {𝐴, 𝐵, 𝐶, 𝐷}
and weighted edges: 𝐴-𝐵:1, 𝐴-𝐶:4, 𝐵-𝐶:2, 𝐵-𝐷:5, 𝐶-𝐷:3, using Kruskal’s algorithm.

Step 1: Sort all edges by weight: 𝐴-𝐵(1), 𝐵-𝐶(2), 𝐶-𝐷(3), 𝐴-𝐶(4), 𝐵-𝐷(5).

Step 2: Add 𝐴-𝐵 (weight 1), no circuit created (connects two previously-separate vertices).
Components so far: {𝐴, 𝐵}, {𝐶}, {𝐷}.

Step 3: Add 𝐵-𝐶 (weight 2), connects {𝐴, 𝐵} with {𝐶}, no circuit. Components: {𝐴, 𝐵, 𝐶}, {𝐷}.

Step 4: Add 𝐶-𝐷 (weight 3), connects {𝐴, 𝐵, 𝐶} with {𝐷}, no circuit. Components: {𝐴, 𝐵, 𝐶, 𝐷},
all vertices now in one component, and there are 3 = 𝑣 − 1 edges (since 𝑣 = 4), so the
algorithm is done.

Step 5: Skip the remaining edges (𝐴-𝐶, 𝐵-𝐷): not needed, and adding either would create a
circuit anyway.

Minimum spanning tree: edges 𝐴-𝐵, 𝐵-𝐶, 𝐶-𝐷, with total weight 1 + 2 + 3 = 6.