Lecture 7. Proofing (methods of proof) #

Overview #

Lecture 6 gave us the semantics of propositional logic: truth tables, satisfiability, and the notion of a tautology (a formula true under every truth assignment). This lecture turns to the syntax and practice of proof — how we move from statements we accept (premises, or hypotheses) to statements we thereby establish (conclusions), and how we prove mathematical theorems.

Two closely related ideas run through the whole lecture:

• A proof is a finite sequence of statements, each of which is either an accepted premise, an axiom, or follows from earlier statements by a rule of inference.
• Every legitimate rule of inference is nothing more than a tautology in disguise: the rule “from $A_1, A_2, \dots, A_n$ infer $B$” is valid exactly when the implication

$$A_1 \wedge A_2 \wedge \dots \wedge A_n \to B$$

is a tautology.

We first make that connection precise, catalogue the standard rules of inference, build several formal derivations, and then study the informal-but-rigorous techniques used to prove ordinary mathematical statements: direct proof, contraposition, contradiction, cases/exhaustion, existence and uniqueness, counterexamples, and mathematical induction (both weak and strong). We close with the classic fallacies that look like valid rules but are not, a short history, exercises, and hints.

This is the craft at the heart of every later lecture. Number theory, combinatorics, graph theory, the analysis of algorithms — all of it is stated as theorems and believed only once proved. Learning the methods here is learning the language in which the rest of the subject is written.

7.1 What is a proof, and why rigor? #

Mathematics is unusual among human activities: its claims are not merely supported by evidence, they are settled. Once a theorem is correctly proved it is true forever, with no exceptions, in every model of its hypotheses. A proof is what produces that certainty.

Definition (proof, informal). A proof of a statement $S$ is a finite chain of reasoning that establishes $S$ beyond any doubt, in which every step is either a definition, a previously established result (axiom, theorem, lemma), a hypothesis, or a consequence of earlier steps by a valid rule of inference. A rigorous proof is one in which every such step could, in principle, be expanded into the fully formal derivations of §7.4.

The vocabulary of mathematical results:

• A theorem is a statement that has been proved true.
• A proposition is a theorem of lesser importance.
• A lemma is an auxiliary theorem proved mainly as a stepping stone to a bigger one.
• A corollary is a theorem that follows almost immediately from another.
• A conjecture is a statement believed true but not yet proved (e.g. the Goldbach conjecture: every even integer $> 2$ is a sum of two primes).
• An axiom (or postulate) is a statement accepted without proof, a starting point.
• A definition fixes the exact meaning of a term. Proofs live or die on definitions: to prove “$n$ is odd,” you must know that odd means “$n = 2k+1$ for some integer $k$.”

Why rigor matters: patterns lie. Empirical evidence — “it worked for the first thousand cases” — is not proof. Mathematics is full of patterns that hold for a long time and then break.

• The polynomial $f(n) = n^2 + n + 41$ (studied by Euler) is prime for every $n = 0, 1, 2, \dots, 39$. It is tempting to conjecture it is always prime. But $f(40) = 40^2 + 40 + 41 = 1681 = 41^2$ is composite.
• Pierre de Fermat conjectured that every Fermat number $F_n = 2^{2^n} + 1$ is prime. Indeed $F_0=3,\,F_1=5,\,F_2=17,\,F_3=257,\,F_4=65537$ are all prime. In 1732 Euler showed $F_5 = 2^{32}+1 = 4294967297 = 641 \times 6700417$ is composite. No further Fermat prime has ever been found.
• Euler conjectured (1769) that a fifth power is never the sum of four positive fifth powers. In 1966 Lander and Parkin found, by computer search,

$$27^5 + 84^5 + 110^5 + 133^5 = 144^5,$$

demolishing the conjecture (both sides equal $61\,917\,364\,224$).

Common pitfall. Verifying finitely many cases proves nothing about the infinitely many you did not check — unless the statement itself only concerns finitely many cases (proof by exhaustion, §7.10). A universally quantified claim “$\forall n\, P(n)$” over an infinite domain requires a general argument, typically induction (§7.11–7.12) or a direct/indirect proof.

Remark (proofs versus discovery). The polished proof you read is rarely the messy path by which it was found. Experiment, examples, and pattern-spotting are indispensable for discovering what is true; proof is how you confirm it. This lecture is about confirmation.

7.2 From semantics to syntax: tautological implication #

Recall from Lecture 6 that a tautology is a formula true under every truth assignment. We now connect this semantic notion to the act of inferring.

Definition (tautological implication / logical consequence). A formula $B$ is a tautological consequence of formulas $A_1, \dots, A_n$, written $A_1, \dots, A_n \models B$, when every truth assignment that makes all of $A_1, \dots, A_n$ true also makes $B$ true.

The central theorem linking semantics to proof is the following equivalence — the semantic deduction theorem already proved in Lecture 6 (Theorem 6.15), restated here as a licence to infer.

Justification theorem. $A_1, \dots, A_n \models B$ if and only if the single formula $A_1 \wedge A_2 \wedge \dots \wedge A_n \to B$ is a tautology.

Proof. ($\Leftarrow$) Suppose $A_1 \wedge \dots \wedge A_n \to B$ is a tautology, and take any assignment making all $A_i$ true. Then the antecedent $A_1 \wedge \dots \wedge A_n$ is true. An implication with a true antecedent can be true only if its consequent is true; since the whole implication is true (being a tautology), $B$ is true. Hence every assignment satisfying all premises satisfies $B$, i.e. $A_1,\dots,A_n \models B$.

($\Rightarrow$) Conversely suppose $A_1,\dots,A_n \models B$. Consider any assignment. If it makes all $A_i$ true, then by hypothesis it makes $B$ true, so the implication reads $\text{T}\to\text{T}=\text{T}$. If it makes some $A_i$ false, the antecedent is false and the implication reads $\text{F}\to(\cdot)=\text{T}$. Either way the implication is true, so it is a tautology. ∎

This is exactly the schema on the slides: $A \to B$ and, more generally, $A_1 \wedge A_2 \wedge \dots \wedge A_n \to B$. It is what makes deductive proof trustworthy: certify once (by a truth table, or algebraically) that a given implication is a tautology, and you may use it forever as a licence to write $B$ beneath any premises matching $A_1, \dots, A_n$ — regardless of what the letters concretely mean. Truth is transmitted from premises to conclusion.

Definition (deductive / truth-preserving reasoning). Reasoning in which the conclusion is guaranteed true whenever the premises are true. It contrasts with inductive/empirical reasoning (a physicist generalizing from experiments), where true premises make a conclusion only probable. Everything in this lecture is deductive.

Remark (soundness in one sentence). A rule of inference is called sound precisely when its guaranteeing implication is a tautology. Soundness is the whole game: an unsound “rule” can lead from true premises to a false conclusion, and a single such rule would let us “prove” anything. This is why §7.16’s fallacies are dangerous — they are unsound rules dressed up to look sound.

7.3 Rules of inference #

Definition (rule of inference). A rule of inference is a fixed pattern “premises $\Rightarrow$ conclusion” whose associated implication is a tautology. We write a rule as a fraction: premises above the line, conclusion below.

$$\frac{A_1 \quad A_2 \quad \dots \quad A_n}{\therefore\; B}$$

The table below lists the standard propositional rules. The middle column gives the “introduction/elimination” names used on the slides (Ukrainian axiomatic tradition), the last column the guaranteeing tautology — you can verify any of them with a truth table.

A few remarks on the most important rules:

• Modus ponens ($A,\ A\to B \therefore B$) is the workhorse rule; in the axiomatic tradition it is called the separation rule because it “separates” $B$ off the implication. Almost every direct proof is a chain of modus ponens steps.
• Modus tollens propagates falsity backwards: knowing the consequent fails, the antecedent must fail too. It is the engine of proof by contraposition (§7.8).
• Disjunctive syllogism is elimination by ruling out alternatives (“it is $A$ or $B$; it is not $A$; therefore $B$”). It powers proof by cases when one case is excluded.
• Resolution is the single rule on which automated theorem provers and SAT solvers are built (see §7.5). From $A \vee B$ and $\neg A \vee C$, the complementary pair $A / \neg A$ “cancels,” leaving $B \vee C$. Disjunctive syllogism is the special case where $C$ is empty.

Verifying a rule (worked example). Let us confirm modus tollens is sound by truth table, i.e. that $\big((A\to B)\wedge \neg B\big)\to \neg A$ is a tautology.

The last column is all T, so the rule is sound. Notice the only row where the antecedent $(A\to B)\wedge\neg B$ is true is the first, and there $\neg A$ is also true — exactly as the Justification theorem predicts.

3.1 Rules of inference for quantified statements #

Ordinary mathematics quantifies over infinite domains (“for all integers $n$…”, “there exists a real $x$…”), so we also need rules that strip and attach quantifiers. These are used silently in every proof below.

Common pitfall (universal generalization). To prove “$\forall x\, P(x)$” by taking an arbitrary $c$ and proving $P(c)$, you may assume nothing about $c$ beyond membership in the domain. If your argument secretly uses “let $c$ be even” or “let $c=0$”, you have proved only a special case, not the universal statement.

7.4 Formal derivations from premises #

Definition (formal derivation). A formal derivation (proof) of $B$ from premises $\Gamma = \{A_1, \dots, A_n\}$, written $\Gamma \vdash B$, is a finite numbered list of formulas ending in $B$, where each line is either a premise or is obtained from earlier lines by a rule of inference. Every line carries a justification naming the rule and the line numbers used.

The turnstile $\vdash$ (“yields”, provability, a syntactic notion) mirrors $\models$ (“entails”, a semantic notion). Because our rules are exactly the tautological ones, the two agree: $\Gamma \vdash B$ precisely when $\Gamma \models B$. That two-way agreement is the soundness ($\vdash \Rightarrow \models$) and completeness ($\models \Rightarrow \vdash$) of propositional calculus.

Example 7.1 (a complete derivation). Show that $\{\,p \to q,\ \ q \to r,\ \ \neg r,\ \ p \vee s\,\} \vdash s$.

Each step is licensed by a rule from the table, so line 7 is established: $s$ follows from the four premises. ∎

Example 7.2 (a derivation using conjunction and simplification). Show $\{\,p \wedge q,\ \ p \to r,\ \ q \to t\,\} \vdash r \wedge t$.

∎

Example 7.3 (a derivation with quantifiers — the Socrates syllogism). From “All humans are mortal” and “Socrates is human,” derive “Socrates is mortal.” Let $H(x)$ mean “$x$ is human” and $M(x)$ “$x$ is mortal.”

∎

Common pitfall (order and scope). A line may cite only lines above it. You cannot justify line 5 using line 7. And a rule must match its pattern exactly: to apply modus ponens you need both $A$ and the whole implication $A \to B$ present on earlier lines — having $A$ and $B\to A$ does not license anything.

7.5 The resolution rule and refutation #

Resolution deserves its own section because it is the basis of practical automated reasoning. It operates on formulas in conjunctive normal form (CNF) — a conjunction of clauses, where each clause is a disjunction of literals (variables or negated variables).

Definition (resolution rule). From two clauses that contain a complementary pair of literals,

$$\frac{(A \vee B) \qquad (\neg A \vee C)}{\therefore\; B \vee C},$$

infer the resolvent $B \vee C$, obtained by deleting the complementary pair $A, \neg A$ and disjoining what remains. Resolving $A$ with $\neg A$ alone yields the empty clause $\square$, which represents $\bot$ (falsehood).

Refutation. To prove $\Gamma \vdash B$ by resolution, one shows that $\Gamma \cup \{\neg B\}$ is unsatisfiable: convert everything to CNF and derive the empty clause $\square$. Reaching $\square$ means the premises together with the negation of the goal are contradictory, so the goal follows. This is proof by refutation, the contradiction method (§7.9) mechanized.

Example 7.4 (resolution refutation). Prove $\{\,p \to q,\ q \to r,\ p\,\} \vdash r$.

Negate the goal and convert to clauses. Using $p \to q \equiv \neg p \vee q$:

$$\{\ \neg p \vee q,\quad \neg q \vee r,\quad p,\quad \neg r\ \}.$$

Now resolve:

The empty clause appears, so $\{p\to q,\ q\to r,\ p,\ \neg r\}$ is unsatisfiable; therefore $r$ follows from the three premises. ∎

Remark (why CS cares). A SAT solver decides whether a CNF formula is satisfiable; modern solvers use conflict-driven clause learning, a refined resolution. Resolution refutation underlies logic programming (Prolog’s execution model is a restricted resolution called SLD-resolution) and many verification tools. That an entire industry rests on one tautology is a striking illustration of §7.2.

7.6 The substitution rule and propositional calculus #

Beyond rules that combine whole formulas, we need a rule that lets us instantiate a proven schema.

Definition (substitution rule). Let $F_1$ be a propositional formula and $A$ an atomic formula (a single propositional variable). If $F_1$ is a tautology (or theorem) containing $A$, then the formula obtained by replacing every occurrence of $A$ in $F_1$ by an arbitrary formula $F_2$ is again a tautology (theorem). The replacement must be uniform: all occurrences of $A$, and only $A$, are replaced. (This is distinct from the replacement rule of Lecture 6, Theorem 6.6, which swaps a subformula for a logically equivalent one; here an atom is replaced by an arbitrary formula.)

For example, from the tautology $A \vee \neg A$ we may substitute $A := (p \wedge q)$ to obtain the tautology $(p\wedge q)\vee \neg(p\wedge q)$.

Common pitfall. Non-uniform substitution destroys validity. From the tautology $A \to A$, replacing only the first $A$ by $p\wedge q$ gives $(p \wedge q) \to A$, which is not a tautology (false when $p, q$ true and $A$ false).

These ideas let us define an axiomatic propositional calculus as a triple:

• Language — the set of well-formed formulas built from propositional variables and connectives, e.g. over connective set $\{\to, \neg\}$.
• Postulates (axiom schemas) — a chosen set of universally valid formulas taken as starting points. A classic three-schema (Hilbert-style) system is

$$\textbf{A1: } A \to (B \to A),$$

$$\textbf{A2: } \big(A \to (B \to C)\big) \to \big((A \to B) \to (A \to C)\big),$$

$$\textbf{A3: } (\neg B \to \neg A) \to (A \to B).$$

• Rules — laws for producing new theorems from old, here just the separation rule (modus ponens) and the substitution rule.

A theorem of the calculus is any formula obtainable from the postulates by finitely many applications of the rules. This is the purely syntactic face of logic: theorems are generated by symbol manipulation, and the completeness theorem guarantees that the theorems are exactly the tautologies.

We now leave the formal calculus and study the informal but rigorous proofs of everyday mathematics. Every technique below is ultimately justified by the rules above; we simply stop writing out each line.

7.7 Direct proof #

Definition (direct proof). To prove an implication $p \to q$, assume $p$ is true and, through a chain of valid inferences and definitions, derive that $q$ is true. (An unconditional statement is proved the same way, with no antecedent to assume.)

We use two standard definitions throughout: an integer $n$ is even if $n = 2k$ for some integer $k$, and odd if $n = 2k+1$ for some integer $k$. An integer $a$ divides $b$ (written $a \mid b$) if $b = ac$ for some integer $c$.

Example 7.5. If $n$ is an odd integer, then $n^2$ is odd.

Proof. Assume $n$ is odd, so $n = 2k + 1$ for some integer $k$. Then

$$n^2 = (2k+1)^2 = 4k^2 + 4k + 1 = 2\,(2k^2 + 2k) + 1.$$

Put $t = 2k^2 + 2k$, an integer. Then $n^2 = 2t + 1$, which is by definition odd. ∎

Example 7.6. The sum of two even integers is even.

Proof. Let $a, b$ be even, say $a = 2s$ and $b = 2t$ for integers $s, t$. Then $a + b = 2s + 2t = 2(s+t)$, and $s+t$ is an integer, so $a+b$ is even. ∎

Example 7.7 (transitivity of divisibility). For all integers $a, b, c$: if $a \mid b$ and $b \mid c$, then $a \mid c$.

Proof. Assume $a \mid b$ and $b \mid c$. Then $b = a s$ and $c = b t$ for some integers $s, t$. Substituting, $c = b t = (a s) t = a (s t)$. Since $st$ is an integer, $a \mid c$. ∎

Example 7.8. If $n$ is even, then $(-1)^n = 1$.

Proof. Assume $n$ is even, so $n = 2k$. Then $(-1)^n = (-1)^{2k} = \big((-1)^2\big)^k = 1^k = 1.$ ∎

Example 7.9 (a sharper fact needing a lemma). If $n$ is odd, then $n^2 \equiv 1 \pmod 8$ — that is, $8 \mid (n^2 - 1)$.

Proof. First a lemma: the product of two consecutive integers $m(m+1)$ is always even. Indeed, one of $m, m+1$ is even; if $m = 2j$ then $m(m+1) = 2j(m+1)$, and if $m+1 = 2j$ then $m(m+1) = 2jm$ — either way the product is $2\times(\text{integer})$.

Now assume $n$ is odd, $n = 2k+1$. Then

$$n^2 = 4k^2 + 4k + 1 = 4k(k+1) + 1.$$

By the lemma $k(k+1)$ is even, say $k(k+1) = 2m$. Hence $n^2 = 4(2m) + 1 = 8m + 1$, so $n^2 - 1 = 8m$ and $8 \mid (n^2-1)$. ∎

Remark (trivial and vacuous proofs). Two degenerate but legitimate direct proofs of $p \to q$ deserve names. A trivial proof establishes $q$ outright, without using $p$ at all (then $p\to q$ is automatically true). A vacuous proof shows $p$ is false, so $p \to q$ is true “by default.” Example (vacuous): “If $n$ is both even and odd, then $n = n+1$” is true because no integer is both even and odd — the hypothesis is never satisfied.

7.1 Biconditionals and equivalences (iff, TFAE) #

To prove a biconditional $P\iff Q$, prove the two implications separately: $P\Rightarrow Q$ and $Q\Rightarrow P$ (each by whatever method fits — direct, contrapositive, or contradiction). Both directions are required; proving only one is the single most common gap. Example: “$n$ is even $\iff n^2$ is even” needs $n\text{ even}\Rightarrow n^2\text{ even}$ (direct) and $n^2\text{ even}\Rightarrow n\text{ even}$ (contrapositive: $n$ odd $\Rightarrow n^2$ odd).

To prove several statements all equivalent — “TFAE: $P_1,\dots,P_k$” — it suffices to prove one cycle of implications $P_1\Rightarrow P_2\Rightarrow\cdots \Rightarrow P_k\Rightarrow P_1$: any statement then implies any other by following the cycle. That is $k$ implications instead of the $k(k-1)$ ordered pairs.

7.8 Proof by contraposition #

Definition (proof by contraposition). Instead of proving $p \to q$ directly, prove its contrapositive $\neg q \to \neg p$. The two are logically equivalent, so a proof of one is a proof of the other.

The equivalence is itself a tautology, confirmed by the truth table:

Columns 3 and 4 are identical, so $p \to q \equiv \neg q \to \neg p$. Contraposition is the method of choice when the negated statements are easier to compute with than the originals — typically when $q$ is a negative or existential claim.

Common pitfall (contrapositive vs. converse). The contrapositive of $p \to q$ is $\neg q \to \neg p$ (equivalent). The converse is $q \to p$ and the inverse is $\neg p \to \neg q$ (both not equivalent to the original). Proving the converse proves a different statement. Confusing “if” with “only if” is one of the most common errors in student proofs.

Example 7.10. For integers, if $n^2$ is even then $n$ is even.

Proof (contraposition). The contrapositive is: if $n$ is odd then $n^2$ is odd, which is Example 7.5. Since the contrapositive is true, so is the original. ∎

Example 7.11. For integers, if $3n + 2$ is odd then $n$ is odd.

Proof (contraposition). Contrapositive: if $n$ is even then $3n+2$ is even. Assume $n = 2k$. Then $3n + 2 = 6k + 2 = 2(3k+1)$, which is even. The contrapositive holds, hence so does the original. ∎

Example 7.12. For all positive real numbers $n, m$: if $nm > 100$, then $n > 10$ or $m > 10$.

Proof (contraposition). The contrapositive is if $n \le 10$ and $m \le 10$, then $nm \le 100$. (Here $\neg(n>10 \vee m>10)$ becomes $n\le 10 \wedge m \le 10$ by De Morgan, and $\neg(nm>100)$ becomes $nm \le 100$.) Assume $0 < n \le 10$ and $0 < m \le 10$. Multiplying the inequalities by positive quantities,

$$n \le 10 \ \Rightarrow\ nm \le 10m, \qquad m \le 10 \ \Rightarrow\ 10m \le 100.$$

Chaining, $nm \le 10m \le 100$. Having proved the contrapositive, the original implication holds. ∎

Remark. Example 7.12 shows why contraposition helps: the original conclusion is a disjunction (“$n>10$ or $m>10$”), awkward to prove directly, whereas its negation is a conjunction of two clean inequalities we can just multiply.

7.9 Proof by contradiction (reductio ad absurdum) #

Definition (proof by contradiction). To prove a statement $p$, assume its negation $\neg p$ and derive a contradiction — a formula of the form $r \wedge \neg r$, i.e. $\bot$. Since $(\neg p \to \bot)$ forces $p$ to be true, $p$ is established.

The engine is the tautology $\big(\neg p \to (r \wedge \neg r)\big) \to p$. To prove an implication $p \to q$ by contradiction, assume $p \wedge \neg q$ and derive $\bot$; the only row where $p \to q$ is false is $p$ true, $q$ false, and that is exactly what we rule out:

Example 7.13 (a classic). $\sqrt{2}$ is irrational.

Proof. Suppose, for contradiction, that $\sqrt{2}$ is rational. Then it can be written in lowest terms as

$$\sqrt{2} = \frac{m}{n}, \qquad m, n \in \mathbb{Z},\ \ n \neq 0,\ \ \gcd(m, n) = 1.$$

Squaring, $2 = m^2/n^2$, hence $m^2 = 2n^2$. So $m^2$ is even, and therefore $m$ is even (Example 7.10). Write $m = 2k$. Substituting,

$$(2k)^2 = 2n^2 \ \Rightarrow\ 4k^2 = 2n^2 \ \Rightarrow\ n^2 = 2k^2,$$

so $n^2$ is even and hence $n$ is even. But then $2$ divides both $m$ and $n$, contradicting $\gcd(m, n) = 1$. The assumption is untenable, so $\sqrt{2}$ is irrational. ∎

Example 7.14 (Euclid’s theorem, ca. 300 BCE). There are infinitely many primes.

Proof. Suppose, for contradiction, that there are only finitely many primes, listed as $p_1, p_2, \dots, p_n$. Consider the number

$$N = p_1 p_2 \cdots p_n + 1.$$

Since $N > 1$, it has at least one prime divisor $p$ (this fact is proved in Example 7.26). That $p$ must be one of $p_1, \dots, p_n$, since those are supposedly all the primes. But then $p \mid N$ and $p \mid p_1 p_2 \cdots p_n = N - 1$, so $p \mid \big(N - (N-1)\big) = 1$. No prime divides $1$ — contradiction. Hence there are infinitely many primes. ∎

Common pitfall. Euclid’s argument does not claim $N = p_1\cdots p_n + 1$ is itself prime. It only needs $N$ to have some prime factor outside the list. Indeed $N$ can be composite: $2\cdot3\cdot5\cdot7\cdot11\cdot13 + 1 = 30031 = 59 \times 509$. Students often misremember this as “the product of the first $k$ primes plus one is prime,” which is false.

Example 7.15. There is no smallest positive rational number.

Proof. Suppose, for contradiction, that $r$ is the smallest positive rational. Then $r/2$ is also rational (a quotient of rationals) and positive, yet $r/2 < r$. This contradicts the minimality of $r$. Hence no smallest positive rational exists. ∎

Example 7.16. $\log_2 3$ is irrational.

Proof. Suppose $\log_2 3$ is rational. Since $\log_2 3 > 0$, write $\log_2 3 = p/q$ with positive integers $p, q$. Then $2^{p/q} = 3$, so raising to the $q$-th power, $2^{p} = 3^{q}$. The left side $2^p$ is even (as $p \ge 1$), while the right side $3^q$ is odd. An even number cannot equal an odd number — contradiction. Hence $\log_2 3$ is irrational. ∎

Remark (contradiction vs. contraposition). They are close cousins but not identical. Contraposition proves $p\to q$ by proving $\neg q \to \neg p$ with a direct argument and no contradiction. Contradiction is more general (it proves any statement, not just implications) but is often criticized for being less informative: it tells you that something is impossible without always revealing why constructively. Where a direct or contrapositive proof is available, many mathematicians prefer it.

7.10 Proof by cases and exhaustion #

Definition (proof by cases). Split the hypothesis into finitely many exhaustive cases $C_1, \dots, C_k$ (whose disjunction $C_1 \vee \dots \vee C_k$ is always true) and prove the conclusion separately in each. It rests on the tautology

$$\Big((C_1 \to q) \wedge \dots \wedge (C_k \to q)\Big) \wedge (C_1 \vee \dots \vee C_k) \;\to\; q.$$

Definition (proof by exhaustion). The special case in which the domain is finite and small enough that we simply check every element.

Common pitfall. The cases must be exhaustive — their disjunction must cover every possibility. Forgetting a case (e.g. handling $x>0$ and $x<0$ but not $x=0$) leaves a hole in the proof. The cases need not be mutually exclusive, but they must together cover everything.

Example 7.17 (exhaustion). $(n+1)^3 \ge 3^n$ for every natural number $n$ with $1 \le n \le 4$.

Proof. The domain $\{1,2,3,4\}$ is finite; check each.

All four hold. ∎ (The inequality fails at $n=5$: $6^3 = 216 < 243 = 3^5$ — which is exactly why the hypothesis restricts $n \le 4$.)

Example 7.18. For every integer $n$, $n^2 \equiv 0$ or $1 \pmod 4$.

Proof (two cases on parity). Case 1: $n$ even. Then $n = 2k$, so $n^2 = 4k^2 \equiv 0 \pmod 4$. Case 2: $n$ odd. Then $n = 2k+1$, so $n^2 = 4k^2 + 4k + 1 = 4(k^2+k) + 1 \equiv 1 \pmod 4$. Every integer is even or odd, so the cases are exhaustive and $n^2 \equiv 0$ or $1 \pmod 4$ always. ∎ (Corollary: no integer of the form $4m + 2$ or $4m+3$ is a perfect square.)

Example 7.19. Every prime $p > 3$ has the form $6k+1$ or $6k+5$ (equivalently $6k \pm 1$).

Proof. Any integer is exactly one of $6k, 6k+1, 6k+2, 6k+3, 6k+4, 6k+5$. We rule out four cases for a prime $p > 3$:

• $6k$, $6k+2$, $6k+4$ are all even, hence divisible by $2$; since $p > 3 > 2$, such $p$ would be composite.
• $6k+3 = 3(2k+1)$ is divisible by $3$; since $p > 3$, such $p$ would be composite.

The only remaining forms are $6k+1$ and $6k+5$, so a prime $p > 3$ must be one of these. ∎

Example 7.20 (cases via “without loss of generality”). For all real numbers $x, y$: $|x + y| \le |x| + |y|$ (the triangle inequality).

Proof. Recall $|a| \ge a$ and $|a| \ge -a$ for every real $a$; equivalently $-|a| \le a \le |a|$. Adding the inequalities $-|x| \le x \le |x|$ and $-|y| \le y \le |y|$ gives

$$-\big(|x|+|y|\big) \le x + y \le |x| + |y|.$$

A number $t$ satisfying $-c \le t \le c$ (with $c \ge 0$) satisfies $|t| \le c$. Taking $t = x+y$ and $c = |x|+|y|$ yields $|x+y| \le |x| + |y|$. ∎ (This packages the four sign-cases $x,y \gtrless 0$ into one uniform argument — the phrase “without loss of generality” often signals such a compression.)

7.11 Mathematical induction (weak form) #

Definition (mathematical induction, weak form). To prove that a statement $P(n)$ holds for every integer $n \ge a$, establish two obligations:

• Base step — show $P(a)$ is true.
• Inductive step — show that for every $k \ge a$, if $P(k)$ is true (the inductive hypothesis, IH), then $P(k+1)$ is true.

If both hold, then $P(n)$ is true for all $n \ge a$.

Intuitively, the base step knocks over the first domino, and the inductive step guarantees each domino knocks over the next; so every domino falls. Formally, induction is one of the Peano axioms characterizing the natural numbers — it is not derived from more basic principles but assumed as part of what $\mathbb{N}$ means.

Common pitfall (never skip the base step). Both steps are essential. Consider the false claim $P(n)$: “$n = n+1$.” Its inductive step actually goes through: if $k = k+1$ then adding $1$ gives $k+1 = k+2$, i.e. $P(k+1)$. Yet $P(n)$ is false for every $n$, because the base step fails. An inductive step with no valid base proves nothing.

Example 7.21 (arithmetic series). For every integer $n \ge 1$, $\displaystyle 1 + 2 + \dots + n = \frac{n(n+1)}{2}.$

Proof. Base ($n=1$): the left side is $1$; the right side is $\tfrac{1\cdot 2}{2} = 1$. Equal, so $P(1)$ holds. Inductive step: assume for some $k \ge 1$ that $1 + 2 + \dots + k = \tfrac{k(k+1)}{2}$ (IH). Then

$$1 + 2 + \dots + k + (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 $P(k+1)$. By induction the formula holds for all $n \ge 1$. ∎

Example 7.22 (sum of odd numbers). For every integer $n \ge 1$, $\displaystyle 1 + 3 + 5 + \dots + (2n-1) = n^2.$

Proof. Base ($n=1$): left side $= 1$, right side $= 1^2 = 1$. ✓ Inductive step: assume $1 + 3 + \dots + (2k-1) = k^2$ (IH). The $(k+1)$-th odd number is $2(k+1)-1 = 2k+1$, so

$$\underbrace{1 + 3 + \dots + (2k-1)}_{=\,k^2\ \text{by IH}} + (2k+1) = k^2 + 2k + 1 = (k+1)^2,$$

which is $P(k+1)$. By induction the identity holds for all $n \ge 1$. ∎

Example 7.23 (sum of squares). For every integer $n \ge 1$, $\displaystyle 1^2 + 2^2 + \dots + n^2 = \frac{n(n+1)(2n+1)}{6}.$

Proof. Base ($n=1$): left $=1$, right $= \tfrac{1\cdot 2\cdot 3}{6} = 1$. ✓ Inductive step: assume $\sum_{i=1}^{k} i^2 = \tfrac{k(k+1)(2k+1)}{6}$ (IH). Then

$$\sum_{i=1}^{k+1} i^2 = \frac{k(k+1)(2k+1)}{6} + (k+1)^2 = \frac{(k+1)\big[k(2k+1) + 6(k+1)\big]}{6} = \frac{(k+1)(2k^2 + 7k + 6)}{6}.$$

Factoring $2k^2 + 7k + 6 = (k+2)(2k+3)$ gives $\tfrac{(k+1)(k+2)(2k+3)}{6}$, which is the formula with $n = k+1$. By induction it holds for all $n \ge 1$. ∎

Example 7.24 (a divisibility result). For every integer $n \ge 1$, $6 \mid (n^3 - n)$.

Proof. Base ($n=1$): $1^3 - 1 = 0$, and $6 \mid 0$. ✓ Inductive step: assume $6 \mid (k^3 - k)$ (IH). Then

$$(k+1)^3 - (k+1) = k^3 + 3k^2 + 3k + 1 - k - 1 = (k^3 - k) + 3k^2 + 3k = (k^3 - k) + 3k(k+1).$$

The first term is divisible by $6$ by the IH. For the second, $k(k+1)$ is a product of consecutive integers, hence even (lemma of Example 7.9), so $3k(k+1)$ is divisible by $6$. A sum of two multiples of $6$ is a multiple of $6$, so $6 \mid \big((k+1)^3 - (k+1)\big)$. By induction $6 \mid (n^3 - n)$ for all $n \ge 1$. ∎

Example 7.25 (an inequality, non-unit base). For every integer $n \ge 4$, $2^n < n!$.

Proof. Base ($n = 4$): $2^4 = 16 < 24 = 4!$. ✓ (Note the base is $n=4$, not $1$: the claim is false for $n \le 3$, since $2^3 = 8 > 6 = 3!$.) Inductive step: assume $2^k < k!$ for some $k \ge 4$ (IH). Then

$$2^{k+1} = 2\cdot 2^k < 2 \cdot k! < (k+1)\cdot k! = (k+1)!,$$

where the middle inequality uses the IH and the last uses $k + 1 > 2$ (true since $k \ge 4$). Hence $2^{k+1} < (k+1)!$. By induction $2^n < n!$ for all $n \ge 4$. ∎

Remark (choosing the base). Induction proves “$P(n)$ for all $n \ge a$” for whatever starting value $a$ makes the base step true. Example 7.25 illustrates that the natural starting point is not always $1$ — you begin where the statement first holds.

7.12 Strong induction #

Definition (strong induction / complete induction). To prove $P(n)$ for all $n \ge a$:

• Base step — show $P(a)$ (and possibly a few more initial values) is true.
• Inductive step — show that for every $k \ge a$, if $P(a), P(a+1), \dots, P(k)$ are all true, then $P(k+1)$ is true.

The difference from weak induction is the strength of the hypothesis: you may assume the statement for all smaller values, not just the immediately preceding one.

Weak and strong induction are logically equivalent (each can be derived from the other, and both from the well-ordering principle: every nonempty set of positive integers has a least element). Strong induction is the natural tool when $P(k+1)$ depends on a value further back than $P(k)$ — for instance, when a number factors into two smaller-but-unpredictable pieces.

Example 7.26 (every integer $\ge 2$ has a prime factor). Every integer $n \ge 2$ is divisible by some prime.

Proof (strong induction). Base ($n = 2$): $2$ is prime and $2 \mid 2$. ✓ Inductive step: let $k \ge 2$ and assume every integer $m$ with $2 \le m \le k$ has a prime factor (IH). Consider $k+1$.

• If $k+1$ is prime, then $k+1$ is a prime factor of itself.
• If $k+1$ is composite, then $k+1 = a b$ with integers $2 \le a, b \le k$. By the IH (applied to $a$), $a$ has a prime factor $p$. Since $p \mid a$ and $a \mid (k+1)$, transitivity of divisibility (Example 7.7) gives $p \mid (k+1)$.

Either way $k+1$ has a prime factor. By strong induction every integer $\ge 2$ has one. ∎ (This is the fact borrowed in Euclid’s proof, Example 7.14, and it needs the full smaller-than-$k+1$ hypothesis — hence strong induction.)

Example 7.27 (existence of prime factorizations). Every integer $n \ge 2$ can be written as a product of primes.

Proof (strong induction). Base ($n=2$): $2$ is prime, a product of one prime. ✓ Inductive step: assume every integer $m$ with $2 \le m \le k$ is a product of primes. Consider $k+1$.

• If $k+1$ is prime, it is already such a product.
• If $k+1 = ab$ with $2 \le a, b \le k$, then by the IH both $a$ and $b$ are products of primes; concatenating those factorizations expresses $k+1$ as a product of primes.

By strong induction every integer $\ge 2$ is a product of primes. ∎ (This is the existence half of the Fundamental Theorem of Arithmetic; uniqueness of the factorization requires more work.)

Example 7.28 (a “postage stamp” / representation result). Every integer $n \ge 12$ can be written as $4a + 5b$ for some nonnegative integers $a, b$ (i.e. paid with 4-cent and 5-cent stamps).