Mathematical induction proves that we can climb as high as we like on a ladder, by proving that we can climb onto the bottom rung (the basis) and that from each rung we can climb up to the next one “(the step).” — Concrete Mathematics, by Ronald Graham, Donald Knuth, and Oren Patashnik.

The Architecture of Truth: A Guide to Mathematical Proofs

In mathematics, a proof is more than just a verification of facts—it is a logical narrative. It explains not just that something is true, but why it is inescapably true. To build these narratives, mathematicians rely on a specific toolkit of logical frameworks. Below, we explore the four foundational methods of mathematical proof.

1. Direct Proof

A direct proof is a straightforward logical chain. Typically, we use it to prove mathematical statements of the form: if P, then Q.

The strategy is simple:

We take the original statement P and assume it to be true.
We use this original statement P to show directly that another mathematical statement Q is also true.
We use what we know about P, i.e., unpack it using known definitions, axioms, and facts or results (a.k.a. lemmas and theorems) that we already know about P.
Basically, we get equivalent statements about P, perform some mathematical calculations, logical reasoning, computations, and analytical thinking.
Finally, we repack or rewrite Q.

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

Proof:

Assume that $n$ is an odd integer. By the mathematical definition of an odd number, there exists some integer $k \in \mathbb{Z}$ such that $n = 2k + 1$.

Now, let us examine $n^2$ by substituting this definition:

$$\begin{aligned} n^2 &= (2k + 1)^2 \\ &= 4k^2 + 4k + 1 \\ &= 2(2k^2 + 2k) + 1 \end{aligned}$$

Because $k$ is an integer, the term $(2k^2 + 2k)$ is also an integer. Let’s call it $m$. We have rewritten $n^2$ in the form $2m + 1$, which is the exact definition of an odd integer. ∎

Example. Sums of Odds. The sum of two odd integers is even.

Proof:

Let $n$ and $m$ be odd integers. By definition, there exist integers $s, t \in \mathbb{Z}$ such that $n = 2s + 1$ and $m = 2t + 1$.

Adding them together yields:

$$\begin{aligned} n + m &= (2s + 1) + (2t + 1) \\ &= 2s + 2t + 2 \\ &= 2(s + t + 1) \end{aligned}$$

Because $s + t + 1$ is an integer, the sum is a multiple of $2$. Therefore, the sum is even. ∎

2. Proof by Contrapositive

Sometimes, proving $P \implies Q$ directly is mathematically clumsy or difficult. Proof by contrapositive allows us to tackle the problem from the opposite direction.

Proof by contrapositive consists of exchanging the hypothesis and conclusion of a conditional statement and negating both hypothesis and conclusion. It relies on the fact that a conditional statement $P \implies Q$ is logically equivalent to $\neg Q \implies \neg P$.

The Rule of Contraposition: A conditional statement is true if and only if its contrapositive is true. If you can prove that not Q implies not P, you have automatically proven that P implies Q.

Example. Statement about Divisibility: Let $a, b, n \in \mathbb{Z}$. If $n$ does not divide $ab$ ($n \nmid ab$), then $n$ does not divide $a$ ($n \nmid a$) and $n$ does not divide $b$ ($n \nmid b$).

Proof.

Proving non-divisibility directly is difficult because it involves remainders. Instead, we will prove the contrapositive.

To form the contrapositive, we negate the conclusion and make it our new hypothesis. By De Morgan’s Laws, the negation of an “AND” statement becomes an “OR” statement: Contrapositive: If $n \mid a$ OR $n \mid b$, then $n \mid ab$.

Assume $n \mid a$. By definition, there exists an integer $c$ such that $a = nc$.

Multiplying both sides by $b$ gives: $ab = (nc)b = n(cb)$

Since $cb$ is an integer, $n \mid ab$. Mutatis mutandis (a Latin phrase meaning “with the necessary changes having been made”), if we assume $n \mid b$ instead, the exact same algebraic argument proves $n \mid ab$. Since the contrapositive is true, our original statement is true. ∎

Mutatis mutandis expresses that an argument can be applied to a new situation when some work but no imagination is demanded of the reader.

Example. Parity of Roots. If $n^2$ is an even integer, then $n$ is an even integer.

Proof.

Directly taking the square root of an even number leads to irrational numbers, making a direct proof messy.

Instead, we prove the contrapositive: If $n$ is odd, then $n^2$ is odd. But wait! We already proved exactly this in our first Direct Proof example. Because we know the contrapositive is true, the original statement is definitively true. ∎

3. Proof by Contradiction (Reductio ad Absurdum)

It is a form of proof that establishes the truth or validity of a proposition or statement by showing that assuming the proposition to be false leads to a contradiction.

Suppose the proposition to be proved is $P$. We assume the statement $P$ to be false ($\neg P$) and show that this leads to a contradiction (denoted by the symbol $\bot$, read as falsum), then it is concluded that P must be true.

Example: Statement: $\sqrt{2}$ is irrational.

Suppose, for the sake of contradiction, that $\sqrt{2}$ is rational. By definition, it can be written as a fraction of two integers: $\sqrt{2} = \frac{a}{b}$

Without loss of generality, assume this fraction is fully simplified, meaning $a$ and $b$ share no common factors.

Squaring both sides and rearranging yields:

$$\begin{aligned} 2 &= \frac{a^2}{b^2} \\ 2b^2 &= a^2 \end{aligned}$$

Because $a^2$ is equal to $2$ times an integer, $a^2$ is even. As we proved in the Contrapositive section, if $a^2$ is even, $a$ itself must be even. Therefore, $a = 2k$ for some integer $k$.

Substitute $a = 2k$ back into our equation:

$$\begin{aligned} 2b^2 &= (2k)^2 \\ 2b^2 &= 4k^2 \\ b^2 &= 2k^2 \end{aligned}$$

By the exact same logic, $b^2$ is even, which means $b$ must also be even.

Here is our contradiction ($\bot$): We initially stated that $\frac{a}{b}$ is a fully simplified fraction. However, we just proved that both $a$ and $b$ are even, meaning they share a common factor of $2$. A fraction cannot be both fully simplified and reducible at the same time. Therefore, our initial assumption must be false. $\sqrt{2}$ is irrational. ∎

Example: Euclid’s Infinitude of Primes. Statement: There are an infinite number of primes.

Proof.

Suppose that the set of prime numbers is finite. Then there exists a complete list of all $n$ primes: $p_1, p_2, \dots, p_n$.

Consider a newly constructed number, $P$, formed by multiplying all existing primes together and adding $1$: $P = (p_1 \cdot p_2 \cdot \dots \cdot p_n) + 1$

By the Fundamental Theorem of Arithmetic, $P$ must be divisible by some prime number. Since our list of primes is assumed to be complete, some prime on our list (let’s call it $p_i$) must divide $P$.

However, we also know that $p_i$ divides the product $(p_1 \cdot p_2 \dots p_n)$.

Because $p_i$ divides both $P$ and $(P - 1)$, it must divide their difference: $p_i \mid [P - (P-1)] \implies p_i \mid 1$

The only positive integer that divides $1$ is $1$ itself. But $1$ is not a prime number! This is a contradiction ($\bot$). Therefore, no finite list of primes can ever be complete. ∎

Mathematical Induction

Principle of induction. It is a way of proving that a statement $P(n)$ is true for every natural number (or more generally for all natural numbers greater than a fixed element “a”). Let $P(n)$ be a family of statements indexed by the natural numbers. Suppose that:

(i) $P(0)$ holds true. This is the Base case and…
(ii) for any $n$, if the statement holds for $n$, i.e., $P(n)$ is true, then it holds for $n + 1$, that is, $P(n + 1)$ is also true. This is the Inductive case.

Then $P(n)$ is true for all natural numbers n. Proof by induction is analogous to the toppling of dominoes. If dominoes are stacked in such a way (sufficiently close) that if the $n$-th domino falls, it will push the $(n + 1)$-th domino over, then for every domino to fall we only need to topple the first one. Mathematical induction

Example 1: Sum of the First $n$ Integers

Statement: For any integer $n \ge 0$, the sum $\sum_{k=0}^n k = \frac{n(n+1)}{2}$.

Proof:

Base Case ($n=0$): $0 = \frac{0(0+1)}{2} = 0$. The base case holds.

Inductive Step: Assume the formula holds for an arbitrary integer $n$. We must prove it holds for $n+1$.

$$\begin{aligned} \sum_{k=0}^{n+1} k &= \left( \sum_{k=0}^n k \right) + (n+1) \\ &= \frac{n(n+1)}{2} + (n+1) \quad \text{[By our inductive assumption]} \\ &= \frac{n(n+1) + 2(n+1)}{2} \\ &= \frac{(n+1)(n+2)}{2} \end{aligned}$$

This perfectly matches the formula for $n+1$. By the principle of induction, the statement is true for all $n \ge 0$, QED.

Example 2: Divisibility by 9. $10^{n+1} + 3(10^n) + 5$ is divisible by $9$ for all $n \in \mathbb{N}$.

Proof:

Base Case ($n=0$): $10^1 + 3(10^0) + 5 = 10 + 3 + 5 = 18$. Since $18$ is divisible by $9$, the base case holds.

Inductive Step: Assume the statement holds for $n$. This means there is some integer $m$ such that $10^{n+1} + 3(10^n) + 5 = 9m$. We must prove it holds for $n+1$.

$10^{(n+1)+1} + 3(10^{n+1}) + 5 = 10 \cdot 10^{n+1} + 10 \cdot 3(10^n) + 5 = 10 \left[ 10^{n+1} + 3(10^n) \right] + 5$

From our assumption, we know $10^{n+1} + 3(10^n) = 9m - 5$. Substituting this in: $10^{(n+1)+1} + 3(10^{n+1}) + 5 = 10(9m - 5) + 5 = 90m - 50 + 5 = 90m - 45 = 9(10m - 5)$ Because $(10m-5)$ is obviously an integer, the entire expression is a multiple of $9$. ∎

The Strong Form of Induction

Sometimes, assuming $P(n)$ is true isn’t enough information to prove $P(n+1)$. In strong induction, our inductive step assumes that the statement is true for all previous steps: $P(0), P(1), \dots, P(n)$, and uses that combined knowledge to prove $P(n+1)$.

Strong Form of Induction. Let $P(n)$ be a family of statements indexed by the natural numbers. Suppose that

(i) $P(0)$ is true and
(ii) for any $n$, if $P(0), P(1), \cdots, P(n)$ are true then $P(n + 1)$ is also true.

Then $P(n)$ is true for all natural numbers $n$.

Example 3: Recursive Sequences. Given a sequence where $a_0 = 1, a_1 = 3$, and $a_n = 2a_{n-1} - a_{n-2}$ for all $n \ge 2$, prove that $a_n = 2n + 1$ for all $n \ge 0$.

Proof:

Base Cases: We must check $n=0$ and $n=1$. $a_0 = 2(0) + 1 = 1$. (Matches given). $a_1 = 2(1) + 1 = 3$. (Matches given).

Strong Inductive Step: Suppose $a_k = 2k + 1$ is true for all $0 \le k \le n$. We must prove it is true for $n+1$.

Using the recursive definition:

$$\begin{aligned} a_{n+1} &= 2a_n - a_{n-1} \\ &= 2[2n + 1] - [2(n-1) + 1] \quad \text{[By the strong inductive hypothesis]} \\ &= (4n + 2) - (2n - 1) \\ &= 2n + 3 \\ &= 2(n+1) + 1 \end{aligned}$$

. This perfectly matches the closed-form formula for $n+1$. ∎ Q.E.D.

Historically, mathematicians ended proofs with the letters Q.E.D. (quod erat demonstrandum, meaning “which was to be demonstrated”). Today, modern technical writing uses the Halmos symbol (∎), often called a tombstone, to clearly mark the visual conclusion of a proof.

Mathematical induction is often compared to a line of falling dominoes: if you can knock over the first one (the Base Case), and you can prove that any falling domino will perfectly strike the one immediately after it (the Inductive Step), you have proven that the entire infinite line will fall.

While induction is famous for proving summation formulas, its true power shines when applied to other domains of mathematics.

Prove that $6$ divides $8^n - 2^n$ for every positive integer $n$.

Proof:

Let $P(n)$ be the statement that $8^n - 2^n = 6k$ for some integer $k$.

Base Case ($n=1$): $8^1 - 2^1 = 6$. Since $6$ perfectly divides $6$, $P(1)$ is true.

Inductive Step: Assume $P(n)$ is true, $8^n - 2^n = 6k$.

Now evaluate $P(n+1)$: $8^{n+1} - 2^{n+1} = 8 \cdot 8^n - 2 \cdot 2^n$

Here we are going to use an algebraic trick. We want to extract an $8^n - 2^n$ from this expression. We can split the $8$ into $(6 + 2)$: $= (6 + 2)8^n - 2 \cdot 2^n = 6 \cdot 8^n + 2 \cdot 8^n - 2 \cdot 2^n = 6 \cdot 8^n + 2(8^n - 2^n) $

By our inductive hypothesis, we know that $(8^n - 2^n) = 6k$. Substitute this in: $= 6 \cdot 8^n + 2(6k) = 6(8^n + 2k)$

Since $(8^n + 2k)$ is an integer, the entire expression is a multiple of $6$. Thus, $P(n+1)$ is true. ∎

The Exponential Bound. Prove that $2^n > n$ for all $n \in \mathbb{N}$.

Proof:

Let $P(n)$ be the statement that $2^n > n$.

Base Cases: For inequalities, verifying the first couple of base cases ensures stability. For $n=0$: $2^0 = 1 \gt 0$. True. For $n=1$: $2^1 = 2 \gt 1$. True.

Inductive Step: Assume $P(n)$ is true for some integer $n \ge 1$. (We restrict $n \ge 1$ here because we have already proved $n=0$ manually, and we will need $n \ge 1$ for a bounding step below). We assume: $2^n \gt n$.

Multiply both sides of the inequality by 2: $2 \cdot 2^n \gt 2n \implies 2^{n+1} \gt 2n$

Now, we look at the term $2n$. We can obviously rewrite this algebraically: $2n = n + n$

Because we established that $n \ge 1$, we know that: $n + n \ge n + 1$

Through the transitive property of inequalities ($a \gt b$ and $b \ge c \implies a \gt c$), we connect our logic: $2^{n+1} \gt n + n \ge n + 1 \implies 2^{n+1} \gt n + 1$ and this is exactly the statement $P(n+1)$. Therefore, by the principle of mathematical induction, $2^n \gt n$ for all $n \in \mathbb{N}$. ∎

Theorem: The Existence of Prime Factorization

Proposition: Every natural number strictly greater than 1 can be expressed as a product of one or more prime numbers.

Proof:

Let $P(n)$ be the statement that n can be expressed as a product of prime numbers.

Base Case ($n = 2$): The number 2 is a prime number. A single prime is trivially considered a “product of one prime.” Thus, $P(2)$ is true.
Strong Inductive Step: Assume that $P(m)$ is true for all integers $m$ such that $2 \le m \lt n$. This is our strong inductive hypothesis.

Now consider the number n. There are exactly two possibilities for n:
Case 1: n is prime. If n is prime, then it is already a product of one prime, and P(n) is obviously true.
Case 2: n is composite. If n is not prime, by the definition of composite numbers, it can be factored into two smaller integers, say s and t: $n = s \cdot t$

Crucially, because n is composite, neither factor can be 1 or n. Therefore, we know the strict bounds of these factors: $1 \lt s \lt n$ and $1 \lt t \lt n$.

Because s and t are strictly between $2$ and $n−1$, they fall perfectly within the domain of our strong inductive hypothesis. Therefore, we know that $s$ can be written as a product of primes ($p_1 p_2 \dots p_k$), and $t$ can be written as a product of primes ($q_1 q_2 \dots q_j$).

Substituting these prime decompositions back into our equation for $n$: $n = (p_1 p_2 \dots p_k) \cdot (q_1 q_2 \dots q_j)$

Thus, n itself is expressed as a product of prime numbers. Whether $n$ is prime or composite, $P(n)$ holds true. By the strong form of mathematical induction, every natural number greater than 1 can be decomposed into primes. ∎

Writing Proofs

The Architecture of Truth: A Guide to Mathematical Proofs

1. Direct Proof

2. Proof by Contrapositive

3. Proof by Contradiction (Reductio ad Absurdum)

Mathematical Induction

The Strong Form of Induction