References: Rosen 8e §§1.7–1.8, §5.1–5.3; Velleman 3e ch. 3, ch. 6; Spivak ch. 2; Halmos, Naive Set Theory; Hardy & Wright, An Introduction to the Theory of Numbers.
A mathematical statement is either a proposition (a truth-bearer, true or false) or a predicate (a function of free variables that becomes a proposition once they are instantiated). A proof of a statement $\varphi$ is a finite chain of valid inferences, starting from accepted facts, that establishes $\varphi$.
Axiom — a statement accepted without proof, taken as a starting point of a theory.
Definition — an agreement to use a name for an object characterised by a precise condition.
Theorem — a statement that has been proved from axioms, definitions and previously established theorems.
Lemma — an auxiliary theorem proved en route to a bigger result.
Corollary — an easy consequence of an already-proved theorem.
Conjecture — a statement believed to be true but not yet proved.
Most theorems have the form $\forall x\,(\,P(x) \to Q(x)\,)$ — a universally quantified implication. The proof technique chosen typically depends on the shape of $P$ and $Q$.
Rosen 8e §1.7, p. 81; Velleman 3e §1.5.
4 / 38
2.1 Direct proof
A direct proof of $\;p \to q\;$ proceeds as follows: assume $p$ is true, then through a chain of valid inferences (definitions, axioms, theorems, rules of inference) derive $q$.
The sum of two even integers is even.
Let $a, b$ be even integers. By definition there exist integers $k, \ell$ with $a = 2k$ and $b = 2\ell$. Then
$$a + b = 2k + 2\ell = 2(k + \ell).$$
Since $k + \ell \in \mathbb{Z}$, this exhibits $a+b$ as twice an integer — even. $\square$
Let $n \in \mathbb{Z}$. If $n$ is odd, then $n^2$ is odd.
Assume $n$ is odd, so $n = 2k+1$ for some $k \in \mathbb{Z}$. Then
$$n^2 = (2k+1)^2 = 4k^2 + 4k + 1 = 2(2k^2 + 2k) + 1.$$
Letting $m := 2k^2 + 2k \in \mathbb{Z}$, $n^2 = 2m + 1$, which is odd. $\square$
Rosen 8e §1.7 Theorem 1; Velleman 3e §3.1.
5 / 38
3.1 Proof by contraposition
For any propositions $p, q$: $\;p \to q \;\equiv\; \neg q \to \neg p\;$ (contrapositive law).
By truth-table verification (see Lesson 2): in every valuation the columns of $p \to q$ and $\neg q \to \neg p$ agree. Algebraically, $p \to q \equiv \neg p \vee q \equiv q \vee \neg p \equiv \neg\neg q \vee \neg p \equiv \neg q \to \neg p$. $\square$
A proof by contraposition of $\;p \to q\;$ is a direct proof of $\;\neg q \to \neg p\;$. Useful when $\neg q$ gives more leverage than $p$ does.
Let $n \in \mathbb{Z}$. If $n^2$ is even, then $n$ is even.
By contraposition. We prove "$n$ odd $\Rightarrow$ $n^2$ odd". This is exactly the second theorem of slide 5, where we showed $n = 2k+1$ gives $n^2 = 2(2k^2 + 2k) + 1$. Hence by contraposition, $n^2$ even $\Rightarrow$ $n$ even. $\square$
Rosen 8e §1.7 Theorem 3; Velleman 3e §3.1.
6 / 38
4.1 Proof by contradiction — reductio ad absurdum
A proof by contradiction of $\varphi$ proceeds by assuming $\neg \varphi$ and deriving a contradiction (a statement $\psi \wedge \neg \psi$). By the law $\neg \varphi \to \bot \;\equiv\; \varphi$, this establishes $\varphi$.
To prove $p \to q$ by contradiction, assume $p \wedge \neg q$ and derive a contradiction. This is logically equivalent to contraposition but reaches the contradiction by combining $p$ and $\neg q$ rather than starting from $\neg q$ alone.
Contradiction is more flexible: it can prove statements that are not naturally implications, e.g. "$\sqrt 2$ is irrational", "there are infinitely many primes", or "no rational number squared equals $2$".
Template
State the goal $\varphi$.
"Suppose, for contradiction, that $\neg \varphi$ …"
Derive a chain of consequences until reaching some $\psi$ and $\neg \psi$.
There is no rational number $r$ with $r^2 = 2$. Equivalently, $\sqrt 2 \notin \mathbb{Q}$.
Suppose, for contradiction, that $r := p/q \in \mathbb{Q}$ satisfies $r^2 = 2$, where $p, q \in \mathbb{Z}$, $q \neq 0$, and the fraction is in lowest terms — i.e. $\gcd(p, q) = 1$. Then
$$\frac{p^2}{q^2} = 2 \;\Rightarrow\; p^2 = 2 q^2.$$
So $p^2$ is even. By the theorem of slide 6 (contraposition), $p$ is also even. Write $p = 2k$, $k \in \mathbb{Z}$. Substituting:
$$(2k)^2 = 2 q^2 \;\Rightarrow\; 4k^2 = 2q^2 \;\Rightarrow\; q^2 = 2k^2.$$
So $q^2$ is even, hence (again by slide 6) $q$ is even. But then both $p$ and $q$ are divisible by $2$, contradicting $\gcd(p, q) = 1$. $\square$
Rosen 8e §1.7 Theorem 4; classical, attributed to the Pythagoreans.
8 / 38
4.3 Euclid — infinitely many primes
Euclid (c. 300 BC). There are infinitely many primes.
Suppose, for contradiction, that there are only finitely many primes: $p_1, p_2, \dots, p_n$. Consider the integer
$$N := p_1 \cdot p_2 \cdots p_n + 1.$$
By the fundamental theorem of arithmetic (slide 31), $N$ has at least one prime divisor $q$. By our assumption, $q$ is one of $p_1, \dots, p_n$. Hence $q$ divides the product $p_1 \cdots p_n$. But $q$ also divides $N$. So $q$ divides the difference $N - p_1 \cdots p_n = 1$. The only positive divisor of $1$ is $1$, which is not prime. Contradiction. Hence the set of primes is infinite. $\square$
Note that $N = p_1 p_2 \cdots p_n + 1$ need not itself be prime — e.g. $2\cdot 3\cdot 5\cdot 7\cdot 11\cdot 13 + 1 = 30031 = 59 \cdot 509$. The argument only needs that $N$ has some prime divisor, which cannot be in our list.
Euclid, Elements, Book IX Prop. 20; Hardy & Wright §2.1.
9 / 38
5.1 Proof by cases (exhaustion)
A proof by cases of $\varphi$ partitions the assumption into a finite list of mutually exhaustive cases $C_1, C_2, \dots, C_k$ — i.e. $C_1 \vee C_2 \vee \dots \vee C_k$ is known to hold — and proves $\varphi$ under each case. The validity rests on the rule "Disjunction Elimination" (proved in Lesson 5).
For all $x, y \in \mathbb{R}$, $|xy| = |x| \cdot |y|$.
By the trichotomy of $\mathbb{R}$, each of $x$ and $y$ is positive, zero, or negative — giving four meaningful cases (zeros collapse trivially). Case 1: $x \geq 0,\; y \geq 0$. Then $xy \geq 0$, so $|xy| = xy = |x|\,|y|$. ✓ Case 2: $x \geq 0,\; y < 0$. Then $xy \leq 0$, so $|xy| = -xy = x\,(-y) = |x|\,|y|$. ✓ Case 3: $x < 0,\; y \geq 0$. By symmetry of Case 2, $|xy| = (-x)\,y = |x|\,|y|$. ✓ Case 4: $x < 0,\; y < 0$. Then $xy > 0$, so $|xy| = xy = (-x)(-y) = |x|\,|y|$. ✓
All cases give the same conclusion. Hence $|xy| = |x||y|$ for all $x, y \in \mathbb{R}$. $\square$
A proof by cases is only valid if the cases are exhaustive — i.e. their disjunction covers all possibilities. Forgetting a case is the commonest error.
Velleman 3e §3.4; Rosen 8e §1.8.
10 / 38
6.1 Existence proofs — constructive vs non-constructive
To prove $\exists x\,P(x)$ we may proceed:
Constructively — exhibit an explicit witness $c$ and verify $P(c)$.
Non-constructively — prove $\exists x\,P(x)$ without naming any witness (often by contradiction, by case analysis, or by an averaging argument).
There exist integers $x, y, z$ with $x^2 + y^2 = z^2$ (a Pythagorean triple).
Constructive: take $x = 3, y = 4, z = 5$. Then $3^2 + 4^2 = 9 + 16 = 25 = 5^2$. By EG, the existential follows. $\square$
There exist irrational numbers $a, b$ such that $a^b$ is rational.
Non-constructive. Consider $r := \sqrt 2^{\sqrt 2}$. Either $r$ is rational or $r$ is irrational. Case 1. If $r$ is rational, take $a := \sqrt 2$ and $b := \sqrt 2$. Both are irrational (slide 8), and $a^b = r$ is rational. ✓ Case 2. If $r$ is irrational, take $a := r$ and $b := \sqrt 2$. Both are irrational. Then
$a^b = \bigl(\sqrt 2^{\sqrt 2}\bigr)^{\sqrt 2} = \sqrt 2^{\sqrt 2 \cdot \sqrt 2} = \sqrt 2^{\,2} = 2$, which is rational. ✓
Either way, irrational $a, b$ exist with $a^b$ rational. We have not said which case actually obtains. $\square$
Rosen 8e §1.8, p. 92; Hardy & Wright §11.7.
11 / 38
7. Uniqueness proofs
To prove $\exists!\,x\,P(x)$ ("there exists a unique $x$ such that $P(x)$"), recall (Lesson 4):
$$\exists!\,x\,P(x) \;\Longleftrightarrow\; \exists x\,\Bigl(P(x) \wedge \forall y\bigl(P(y) \to y = x\bigr)\Bigr).$$
The standard schema is: (i) exhibit a witness $a$ with $P(a)$ — existence; (ii) suppose $P(b)$ holds — show $b = a$ — uniqueness.
Every real number $x$ has a unique additive inverse — a unique $y \in \mathbb{R}$ with $x + y = 0$.
Existence. Take $y := -x$. Then $x + y = x + (-x) = 0$ by the field axiom. Uniqueness. Suppose $x + y_1 = 0$ and $x + y_2 = 0$. Then $x + y_1 = x + y_2$. Adding $-x$ to both sides: $y_1 = y_2$. $\square$
The same schema shows uniqueness in any group $(G, \cdot, e)$: each $x$ has a unique inverse $x^{-1}$.
Rosen 8e §1.8 Theorem 3; Velleman 3e §3.6.
12 / 38
8. Disproof by counter-example
To disprove a universal statement $\forall x\,P(x)$, it suffices to exhibit a single $x_0$ with $\neg P(x_0)$. The reason is the De Morgan law $\neg \forall x\,P(x) \equiv \exists x\,\neg P(x)$ — once one counter-example is found, the universal statement is refuted.
Claim (false). Every odd integer can be written as the sum of two squares.
Counter-example: $3$. Suppose $3 = a^2 + b^2$ with $a, b \in \mathbb{Z}$. Then $|a|, |b| \leq 1$, so the only candidates are $a^2 + b^2 \in \{0, 1, 2\}$, none of which equals $3$. So the claim fails at $n = 3$.
Claim (false). Every positive integer $n$ satisfies $n^2 + n + 41$ is prime.
Counter-example: $n = 40$ gives $40^2 + 40 + 41 = 1681 = 41^2$, which is not prime.
Disproof by counter-example only refutes universal claims. To disprove an existential statement $\exists x\,P(x)$, one must prove $\forall x\,\neg P(x)$ — a universal claim, which generally requires a full proof, not just one example.
Rosen 8e §1.8 Example 9; Velleman 3e §3.5.
13 / 38
9. Common errors and pitfalls
Affirming the consequent. From $p \to q$ and $q$ one cannot infer $p$. (Lesson 5 §6.) The valid step is Modus Ponens, which requires $p$ in the premises.
Circular reasoning (petitio principii). Using the conclusion (or an equivalent of it) as a step in its own proof. Always check that each justification cites earlier established facts only.
Non-exhaustive case split. Proving the result in cases $C_1, C_2$ when $C_1 \vee C_2$ does not cover all possibilities. E.g. on $\mathbb{R}$, splitting "$x > 0$ or $x < 0$" forgets $x = 0$.
Existence ≠ uniqueness. Producing one witness for $\exists x\,P(x)$ does not show $\exists!\,x\,P(x)$. Uniqueness requires the extra step "for any $y$ with $P(y)$, $y = x$".
Division by zero / ill-defined operation. Manipulations like $a^2 = b^2 \Rightarrow a = b$ silently drop $a = -b$; dividing by $(x - y)$ requires $x \neq y$.
Velleman 3e §1.5, §3.7.
14 / 38
Part II
Mathematical induction
Well-ordering, weak induction, strong induction — all proved equivalent.
15 / 38
10.1 Well-ordering principle
Well-ordering principle (WOP). Every non-empty subset $S \subseteq \mathbb{N}$ has a least element — i.e. $\exists m \in S,\;\forall n \in S,\; m \leq n$.
WOP is an axiom of the natural numbers; equivalently it is one of the Peano axioms in disguise. In the development below we will prove that it is equivalent to weak induction (slide 18) and to strong induction (slide 22), so any one of the three could be taken as the basic axiom and the other two proved as theorems.
The set $S = \{n \in \mathbb{N} : n^2 \geq 10\}$ is non-empty (contains $4$). By WOP it has a least element. We can determine it: $3^2 = 9 < 10$ but $4^2 = 16 \geq 10$, so $\min S = 4$.
WOP fails on $\mathbb{Z}$: the non-empty set $\mathbb{Z}$ itself has no least element. It also fails on $\mathbb{Q}_{\geq 0}$ and on $\mathbb{R}_{\geq 0}$: the open interval $(0, 1)$ is non-empty and has no minimum (only an infimum, $0$). Hence WOP is a special property of $\mathbb{N}$ — it is precisely what distinguishes the natural numbers from other ordered sets.
Rosen 8e §5.2, p. 339; Halmos §17.
16 / 38
10.2 Principle of (weak) induction
Principle of weak induction (PWI). Let $P(n)$ be a predicate on the natural numbers. If
Base case: $P(0)$ holds, and
Inductive step: for every $k \in \mathbb{N}$, $P(k) \to P(k+1)$,
then $\forall n \in \mathbb{N},\, P(n)$.
The base case can be shifted: if $P(n_0)$ holds and $\forall k \geq n_0,\,P(k) \to P(k+1)$, then $\forall n \geq n_0,\,P(n)$. We will use this generalisation freely.
Intuitively: $P(0)$ holds (base); $P(0) \to P(1)$ gives $P(1)$; $P(1) \to P(2)$ gives $P(2)$; … the dominoes fall. PWI is the statement that this informal chain reaches every $n$.
Rosen 8e §5.1 Theorem 1; Velleman 3e §6.1.
17 / 38
10.3 WOP $\Rightarrow$ PWI (proved)
The well-ordering principle implies the principle of weak induction.
Suppose WOP holds. Let $P(n)$ be a predicate satisfying $P(0)$ and $\forall k\,(P(k) \to P(k+1))$. We must show $\forall n,\,P(n)$.
Suppose, for contradiction, that the "failure set"
$$S \;:=\; \{\,n \in \mathbb{N} \;:\; \neg P(n)\,\}$$
is non-empty. By WOP, $S$ has a least element $m$. Since $P(0)$ holds, $m \neq 0$, so $m \geq 1$ and $m - 1 \in \mathbb{N}$. By minimality of $m$ in $S$, the smaller number $m - 1 \notin S$, i.e. $P(m - 1)$ holds. By the inductive step at $k = m - 1$: $P(m - 1) \to P(m)$, so $P(m)$ holds. But this contradicts $m \in S$. Hence $S = \varnothing$, i.e. $\forall n,\,P(n)$. $\square$
Rosen 8e §5.2 Theorem 1; Velleman 3e §6.4.
18 / 38
10.4 PWI $\Rightarrow$ WOP (proved)
The principle of weak induction implies the well-ordering principle.
Suppose PWI holds. Let $S \subseteq \mathbb{N}$ be non-empty; we must produce $\min S$.
Suppose, for contradiction, $S$ has no minimum. Define the predicate
$$P(n) \;:\equiv\; \forall k \leq n,\; k \notin S.$$
Base. $P(0)$: if $0 \in S$ then $0$ would be the minimum of $S$ (since $0$ is already the smallest natural number), contradicting "no minimum". So $0 \notin S$, hence $P(0)$. Step. Suppose $P(n)$ holds: no $k \leq n$ is in $S$. If $n + 1 \in S$, then $n + 1$ would be the minimum of $S$ (every smaller element is excluded), contradicting "no minimum". So $n + 1 \notin S$, hence $P(n + 1)$.
By PWI, $\forall n,\,P(n)$. In particular, no natural number is in $S$, so $S = \varnothing$ — contradicting non-emptiness. Hence $S$ has a minimum. $\square$
WOP, PWI and PSI (slide 22) are logically equivalent. Any one can serve as the foundational axiom; the other two then become theorems.
Velleman 3e §6.4 Theorem 6.4.1.
19 / 38
11.1 Method — the standard template
To prove $\forall n \geq n_0,\,P(n)$ by induction, follow exactly three steps:
Base case. Verify $P(n_0)$ explicitly.
Inductive hypothesis (IH). Assume $P(k)$ holds for an arbitrary fixed $k \geq n_0$.
Inductive step. Using IH, prove $P(k + 1)$.
Conclude: "by induction, $\forall n \geq n_0,\,P(n)$. $\square$"
Skipping the base case is fatal. Without it the inductive step proves only "if $P(n_0)$ then $\forall n \geq n_0,\,P(n)$", an empty statement when $P(n_0)$ is false. See the "all horses are the same colour" pitfall on slide 35.
Each of the next six slides applies this template to a different kind of statement: sum, set count, inequality, log estimate, geometry, divisibility.
Rosen 8e §5.1; Velleman 3e §6.1.
20 / 38
11.2 Example — $\sum_{i=1}^{n} i = n(n+1)/2$
For every $n \geq 1$, $\;\displaystyle \sum_{i=1}^{n} i = \frac{n(n+1)}{2}.$
Let $P(n) :\equiv \bigl(\sum_{i=1}^{n} i = n(n+1)/2\bigr)$. Base ($n = 1$). LHS $= 1$. RHS $= 1 \cdot 2 / 2 = 1$. ✓ Inductive step. Assume $P(k)$: $\sum_{i=1}^{k} i = k(k+1)/2$. Then
$$\sum_{i=1}^{k+1} i = \underbrace{\sum_{i=1}^{k} i}_{\text{IH}} + (k+1) = \frac{k(k+1)}{2} + (k+1) = \frac{k(k+1) + 2(k+1)}{2} = \frac{(k+1)(k+2)}{2},$$
which is the RHS at $n = k + 1$. Hence $P(k+1)$.
By induction, $\forall n \geq 1,\,P(n)$. $\square$
Rosen 8e §5.1 Example 1.
21 / 38
11.3 Example — a set of $n$ elements has $2^n$ subsets
For every $n \geq 0$, if $|A| = n$ then $|\mathcal{P}(A)| = 2^n$.
Base ($n = 0$). The only set of size $0$ is $\varnothing$, with $\mathcal{P}(\varnothing) = \{\varnothing\}$, so $|\mathcal{P}(\varnothing)| = 1 = 2^0$. ✓ Inductive step. Suppose every set of size $k$ has $2^k$ subsets (IH). Let $|A| = k + 1$. Pick an element $a \in A$ and let $B := A \setminus \{a\}$, so $|B| = k$.
Every subset of $A$ either contains $a$ or does not. The subsets not containing $a$ are exactly the subsets of $B$, of which there are $2^k$ by IH. The subsets containing $a$ are exactly the sets of the form $S \cup \{a\}$ with $S \subseteq B$, again $2^k$ such sets. These two families are disjoint, so
$|\mathcal{P}(A)| = 2^k + 2^k = 2 \cdot 2^k = 2^{k+1}.$
Hence $P(k+1)$. By induction, $\forall n \geq 0,\,P(n)$. $\square$
Rosen 8e §5.1 Example 10; Halmos §16.
22 / 38
11.4 Example — $2^n > n^2$ for $n \geq 5$
For every integer $n \geq 5$, $\;2^n > n^2$.
Base ($n = 5$). $2^5 = 32$ and $5^2 = 25$; $32 > 25$. ✓ Inductive step. Assume $2^k > k^2$ for some $k \geq 5$ (IH). We must show $2^{k+1} > (k+1)^2$.
$2^{k+1} = 2 \cdot 2^k \;>\; 2 k^2 \;=\; k^2 + k^2.$ It suffices to show $k^2 > (k+1)^2 - k^2 = 2k + 1$, i.e. $k^2 - 2k - 1 > 0$.
Since $k \geq 5$, $k^2 - 2k - 1 \geq 25 - 10 - 1 = 14 > 0$ ✓.
Hence $2^{k+1} > k^2 + (2k + 1) = (k+1)^2$. By induction, $\forall n \geq 5,\;2^n > n^2$. $\square$
The bound is tight: $2^4 = 16 = 4^2$, equality at $n = 4$; $2^3 = 8 < 9 = 3^2$, the inequality fails for $n = 3$. Choosing the right $n_0$ matters.
Rosen 8e §5.1 Example 4.
23 / 38
11.5 Example — divisibility: $3 \mid (n^3 + 2n)$
For every $n \geq 0$, $\;3 \mid (n^3 + 2n)$.
Let $P(n) :\equiv \bigl(3 \mid (n^3 + 2n)\bigr)$. Base ($n = 0$). $0^3 + 2 \cdot 0 = 0$, and $3 \mid 0$. ✓ Inductive step. Assume $3 \mid (k^3 + 2k)$, say $k^3 + 2k = 3m$ for some $m \in \mathbb{Z}$. Compute
$$(k+1)^3 + 2(k+1) = k^3 + 3k^2 + 3k + 1 + 2k + 2 = (k^3 + 2k) + 3k^2 + 3k + 3 = 3m + 3(k^2 + k + 1).$$
This is $3 \cdot (m + k^2 + k + 1)$, divisible by $3$. Hence $P(k+1)$.
By induction, $\forall n \geq 0,\,P(n)$. $\square$
Rosen 8e §5.1 Example 5; Velleman 3e §6.1.
24 / 38
11.6 Example — $\ln(n+1) \leq H_n$ where $H_n = \sum_{i=1}^n 1/i$
For every $n \geq 1$, $\;\ln(n+1) \leq \displaystyle\sum_{i=1}^{n} \frac{1}{i}$.
Base ($n = 1$). $\ln 2 \approx 0.693 \leq 1 = H_1$. ✓ Inductive step. Assume $\ln(k+1) \leq H_k$. We must show $\ln(k+2) \leq H_{k+1} = H_k + \tfrac{1}{k+1}$.
By the concavity inequality $\ln(k+2) - \ln(k+1) = \int_{k+1}^{k+2} \tfrac{dx}{x} \leq \tfrac{1}{k+1}$ (the rectangle over $[k+1, k+2]$ at height $1/(k+1)$ overestimates the area under $1/x$). Hence
$\ln(k+2) \leq \ln(k+1) + \tfrac{1}{k+1} \leq H_k + \tfrac{1}{k+1} = H_{k+1}.$ $\square$
Since $\ln(n+1) \to \infty$, the harmonic series $\sum 1/n$ diverges — a second proof, complementing Oresme's grouping (Sequences & Series §4.2).
11.7 Example — every convex $n$-gon has a triangulation into $n - 2$ triangles
Every convex polygon with $n \geq 3$ vertices admits a triangulation by non-crossing diagonals, and any such triangulation uses exactly $n - 2$ triangles.
Base ($n = 3$). A triangle is already triangulated into $3 - 2 = 1$ triangle. ✓ Inductive step. Let $P$ be a convex polygon with $k + 1$ vertices. Draw any diagonal $d$ joining two non-adjacent vertices. (Such a diagonal exists since $k + 1 \geq 4$.) The diagonal $d$ splits $P$ into two convex polygons $P_1$ and $P_2$ sharing the edge $d$. If $P_1$ has $j_1$ vertices and $P_2$ has $j_2$ vertices, then each endpoint of $d$ is shared, so
$j_1 + j_2 = (k + 1) + 2.$
Both $j_1, j_2 \leq k$, so by IH, $P_1$ admits a triangulation into $j_1 - 2$ triangles and $P_2$ into $j_2 - 2$. Together: $(j_1 - 2) + (j_2 - 2) = (k+1) + 2 - 4 = k - 1 = (k+1) - 2$. ✓
By induction, the result holds for all $n \geq 3$. $\square$
Rosen 8e §5.2 Example 12; classical combinatorial geometry.
Principle of strong induction (PSI). Let $P(n)$ be a predicate on $\mathbb{N}$. If
Base: $P(n_0)$ holds, and
Strong step: for every $k \geq n_0$, $\bigl(\forall j,\; n_0 \leq j \leq k \Rightarrow P(j)\bigr) \to P(k+1)$,
then $\forall n \geq n_0,\, P(n)$.
The strong-step inductive hypothesis is more generous: instead of assuming only $P(k)$, we may use $P(n_0), P(n_0+1), \dots, P(k)$ — every previously proved instance.
PWI and PSI are logically equivalent.
(PSI ⇒ PWI.) Suppose PSI holds. The weak step $P(k) \to P(k+1)$ is a special case of the strong step (using only the latest $j = k$). So PWI follows. (PWI ⇒ PSI.) Suppose PWI holds. Given the strong step for $P$, define the auxiliary predicate $Q(n) :\equiv \bigl(\forall j,\;n_0 \leq j \leq n \Rightarrow P(j)\bigr)$. Then $Q(n_0)$ is just $P(n_0)$ — true by base. And $Q(k) \to Q(k+1)$ is exactly the strong step applied at $k$ together with $Q(k)$ giving $P(k+1)$. By PWI, $\forall n \geq n_0,\,Q(n)$. In particular $P(n)$ for every such $n$. $\square$
Rosen 8e §5.2 Theorem 1; Velleman 3e §6.4.
27 / 38
12.2 Strong induction example — existence of prime factorisation
Every integer $n \geq 2$ can be written as a product of primes (factorisation into primes exists).
Let $P(n) :\equiv$ "$n$ is a product of primes" (a single prime counts as a product of length $1$). We prove $\forall n \geq 2,\,P(n)$ by strong induction. Base ($n = 2$). $2$ is prime, hence a product of primes. ✓ Strong step. Let $k + 1 \geq 3$ and assume $P(j)$ for every $2 \leq j \leq k$. Two cases. (i) $k+1$ is prime. Then $P(k+1)$ trivially. (ii) $k+1$ is composite. By definition, $k+1 = a \cdot b$ with $2 \leq a, b \leq k$. By IH, $a$ and $b$ are products of primes, say $a = p_1 \cdots p_s$ and $b = q_1 \cdots q_t$. Concatenating, $k + 1 = p_1 \cdots p_s \cdot q_1 \cdots q_t$, a product of primes. ✓
By PSI, $\forall n \geq 2,\,P(n)$. $\square$
Uniqueness of the factorisation (up to order) is the second half of the fundamental theorem of arithmetic and requires Euclid's lemma; we omit it here.
Rosen 8e §5.2 Theorem 2; Hardy & Wright §1.3.
28 / 38
12.3 Strong induction example — Fibonacci bound
Let $\varphi = (1 + \sqrt 5)/2$ (golden ratio). Then for every $n \geq 1$, $\;F_n \leq \varphi^{n-1}$.
This bound is asymptotically sharp: Binet's formula (Sequences & Series §5.3) gives $F_n \sim \varphi^n / \sqrt 5$, so $F_n \approx \varphi^{n-1} / (\sqrt 5 / \varphi) \approx \varphi^{n-1} \cdot \varphi/\sqrt 5 \approx 0.724\,\varphi^{n-1}$.
Rosen 8e §5.2 Theorem 4.
29 / 38
12.4 Strong induction example — postage stamps
Every postage of $n \geq 12$ cents can be formed using only $4$-cent and $5$-cent stamps.
Let $P(n) :\equiv $ "$\exists a, b \in \mathbb{N},\;n = 4a + 5b$". Bases ($n = 12, 13, 14, 15$).
$12 = 4 \cdot 3 + 5 \cdot 0$; $\;13 = 4 \cdot 2 + 5 \cdot 1$; $\;14 = 4 \cdot 1 + 5 \cdot 2$; $\;15 = 4 \cdot 0 + 5 \cdot 3$. ✓ Strong step ($k \geq 15$). Assume $P(j)$ for all $12 \leq j \leq k$ (IH). We show $P(k+1)$.
Since $k + 1 \geq 16$, $k - 3 \geq 12$, so by IH $P(k - 3)$: $k - 3 = 4a + 5b$. Then $k + 1 = (k - 3) + 4 = 4(a + 1) + 5b$. Hence $P(k+1)$. ✓
By PSI, $\forall n \geq 12,\,P(n)$. $\square$
The four bases are needed because the strong step depends on the value $n - 4$ being already covered; rebasing requires four consecutive base cases. This is the Frobenius / Chicken McNugget phenomenon: with coprime denominations $a$ and $b$, every sufficiently large integer is representable, the largest non-representable being $ab - a - b$.
Rosen 8e §5.2 Example 7.
30 / 38
13. Structural induction
Structural induction generalises induction from $\mathbb{N}$ to any inductively defined set $X$. To prove $\forall x \in X,\,P(x)$:
Show $P(b)$ for every basis element $b$ in the inductive definition.
For each constructor $f$ taking arguments $x_1, \dots, x_k$ and producing $f(x_1, \dots, x_k) \in X$, show
$$\bigl(P(x_1) \wedge \dots \wedge P(x_k)\bigr) \;\to\; P\bigl(f(x_1, \dots, x_k)\bigr).$$
Then $\forall x \in X,\,P(x)$.
Binary trees. Define $\mathsf{Tree}$ inductively: a leaf is a tree (base); given trees $L$ and $R$, the constructor $\mathsf{node}(L, R)$ is a tree. Define recursively the number of leaves, $\ell(t)$, and the number of internal nodes, $i(t)$: $\ell(\mathsf{leaf}) = 1$, $i(\mathsf{leaf}) = 0$, and for $t = \mathsf{node}(L, R)$: $\ell(t) = \ell(L) + \ell(R)$, $i(t) = i(L) + i(R) + 1$. Claim. For every binary tree $t$, $\ell(t) = i(t) + 1$.
Wrong claim. All horses in any non-empty set of $n$ horses have the same colour. "Proof". Base $n = 1$: trivially the one horse has its own colour. Inductive step: take a set of $k+1$ horses, remove one to get a set of $k$ (same colour by IH), then put it back and remove a different one (same colour by IH); hence all $k+1$ horses are the same colour.
What went wrong. The inductive step silently assumes $k \geq 2$, so the two $k$-subsets overlap. At $k + 1 = 2$, removing the first horse gives a $1$-element subset, removing the second gives a disjoint $1$-element subset; the two singletons share no common horse, so the chain of "same colour" cannot be transmitted. The induction is broken at $n = 2$.
Moral: the inductive step must be valid for every $k \geq n_0$, including the smallest values. A proof that works only for $k$ large enough is not a proof.
G. Pólya, classical pedagogical example.
32 / 38
14.2 Pitfall — missing or false base case
Wrong claim. $n = n + 1$ for all $n \in \mathbb{N}$. "Proof". Inductive step: if $k = k + 1$, then adding $1$ to both sides gives $k + 1 = k + 2$ ✓.
What went wrong. The induction has no base case — and indeed $0 \neq 1$, so the base would fail. Without it, the step can only chain together conditional "if $k = k+1$ then $k+1 = k+2$" statements; nowhere does the chain become unconditional.
Bound creep. Suppose you prove $P(n) \to P(n+1)$ for $n \geq 3$, with base $P(3)$. Then the conclusion is $\forall n \geq 3$, not $\forall n \geq 1$. Always state the lower bound that matches your proof. Inequalities (slide 23) typically need the smallest base where the bound starts holding.
A recursive function is structured exactly like an inductive proof: a base case handles the smallest inputs; a recursive case reduces the problem to smaller inputs and combines the result. Proving correctness of a recursive function is doing induction on its argument.
Python — factorial via recursiondef fact(n):
if n == 0: # base case ↔ P(0)
return 1
return n * fact(n - 1) # step ↔ P(k+1) follows from P(k)
# Correctness claim: fact(n) returns n! for every n >= 0.
# Proof: induction on n.
# Base n=0: fact(0) returns 1 = 0!. ✓
# Step: assume fact(k) = k!. Then fact(k+1) = (k+1) * fact(k)
# = (k+1) * k! = (k+1)!. ✓
Python — Fibonacci via recursiondef fib(n):
if n <= 1: # two base cases
return n
return fib(n - 1) + fib(n - 2) # strong step: needs F_k AND F_{k-1}
The Fibonacci recursion mirrors strong induction — it depends on both $F_{n-1}$ and $F_{n-2}$, so the correctness proof needs two base cases.
Rosen 8e §5.4; Velleman 3e §6.5.
34 / 38
16. Strategy — picking the right method
Goal looks like
Try first
Fall back
$p \to q$
Direct proof
Contraposition, then contradiction
$\neg \varphi$
Contradiction (assume $\varphi$, derive $\bot$)
Direct on the negation
$p \leftrightarrow q$
Two direct proofs: $p \to q$ and $q \to p$
Chain of equivalences
$\exists x\,P(x)$
Constructive — exhibit a witness
Non-constructive — case analysis
$\exists!\,x\,P(x)$
Existence + uniqueness
—
$\forall x\,P(x)$
UG: "let $x$ be arbitrary"
Cases on shape of $x$, or contradiction
$\forall n \in \mathbb{N},\,P(n)$
Weak induction
Strong induction, well-ordering
Statement involves $n - k$ for small $k$
Strong induction with $k$ base cases
—
Statement over an inductive type
Structural induction
—
Disprove $\forall x\,P(x)$
Counter-example
—
Velleman 3e ch. 3 + ch. 6 (Strategy boxes throughout).
35 / 38
17. Summary — what we proved
Part I — Proofs
Direct proof, contraposition, contradiction, cases, existence (constructive + non-constructive), uniqueness, counter-example — each with at least one fully worked example.
$\sqrt 2 \notin \mathbb{Q}$ (Pythagoras) and "infinitely many primes" (Euclid) — both proved by contradiction.
$|xy| = |x|\,|y|$ proved by cases; $\exists$ irrational $a, b$ with $a^b$ rational — proved non-constructively using $\sqrt 2^{\sqrt 2}$.
Part II — Induction
Well-ordering principle ⇔ weak induction ⇔ strong induction: all three proved equivalent (slides 18–19, 27).
Strong-induction proofs: existence of prime factorisation; $F_n \leq \varphi^{n-1}$; postage-stamp / Frobenius example.
Structural induction: example on binary trees (leaves = internal nodes + 1).
Classical pitfalls — "all horses", missing base case, bound creep.
Programming bridge: recursion mirrors induction; correctness proofs are induction on the recursive parameter.
36 / 38
18. Wolfram → Python quick reference
Task
Wolfram
Python / SymPy
Verify a sum identity
Sum[i, {i, 1, n}] // FullSimplify
Sum(i, (i, 1, n)).doit()
Test an inequality at sample $n$
Table[2^n > n^2, {n, 5, 20}]
[2**n > n**2 for n in range(5, 21)]
Symbolic induction step
FullSimplify[k(k+1)/2 + (k+1) == (k+1)(k+2)/2]
simplify(Eq(k*(k+1)/2 + (k+1), (k+1)*(k+2)/2))
Factorial / Fibonacci
n! · Fibonacci[n]
factorial(n) · fibonacci(n)
Is $n$ prime?
PrimeQ[n]
isprime(n) (from sympy import isprime)
Find a counter-example
FindInstance[P[n] && n > 0, n, Integers]
next((n for n in range(1, 10**6) if not P(n)), None)
Python — induction-step checkerfrom sympy import symbols, simplify, Eq, Rational
k = symbols('k', integer=True, positive=True)
# Check the inductive step for sum_{i=1}^n i = n(n+1)/2
lhs_k1 = k*(k+1)/2 + (k+1) # IH + extra term
rhs_k1 = (k+1)*(k+2)/2 # formula at k+1
print(simplify(lhs_k1 - rhs_k1) == 0) # True → the step holds
37 / 38
Bibliography
K. H. Rosen. Discrete Mathematics and Its Applications, 8th ed., McGraw-Hill, 2019 — §1.7–1.8 (proof methods), §5.1–5.4 (induction, strong induction, structural induction, recursion).
D. J. Velleman. How To Prove It, 3rd ed., Cambridge UP, 2019 — ch. 3 (proof strategies), ch. 6 (mathematical induction).
M. Spivak. Calculus, 4th ed., Publish or Perish, 2008 — ch. 2 (induction, well-ordering).
P. R. Halmos. Naive Set Theory, Springer-Verlag, 1974 — §§16–17 (Peano axioms, well-ordering).
G. H. Hardy & E. M. Wright. An Introduction to the Theory of Numbers, 6th ed., Oxford UP, 2008 — §§1.3, 2.1, 11.7 (prime factorisation, infinitely many primes, irrationality).
G. Pólya. How to Solve It, Princeton UP, 1945 — proof heuristics; the "all horses" example.
Euclid. Elements (c. 300 BC), Book IX Prop. 20 — infinitely many primes.