title: "Lecture 1 - Proof Techniques - Induction and Contradiction"
unit: 0
lecture: 1

Lecture 1 - Proof Techniques - Induction and Contradiction

Why Proofs?

This is a theory course, and in a theory course the proof is the deliverable. A proof is a complete chain of reasoning that starts from definitions and previously proved facts and ends at the claim, written so that a skeptical reader can check every step without trusting you. Examples, pictures, and intuition are how we find proofs, and they will appear all over these notes, but they are never the proof itself: checking a claim for the first million cases does not establish it for all cases, and Lecture 2 will show claims that hold for every case anyone has ever checked yet resist all known proofs.

Two habits will be enforced all semester, in every problem set and on every exam:

1. Be wordy; err on the side of detail. Write for a skeptical reader: justify each step, name the fact or assumption it uses, and spell out reasoning you might be tempted to wave off as obvious. Extra detail never costs you; a gap does.
2. Label the skeleton of the proof. Say what you are assuming, say what you are trying to show, and when the technique has named parts (base case, inductive hypothesis, inductive step), label them.

Every example below follows both habits; hold your own write-ups in the exercises at the end of each lecture, and on the exams, to the same standard.

Direct Proof

The plainest way to prove "if $P$, then $Q$" is to assume $P$, then reason forward until $Q$ appears. One tiny example, done in full, to fix the format.

Definition. An integer $n$ is even if $n = 2k$ for some integer $k$, and odd if $n = 2k + 1$ for some integer $k$.

Example 1: the sum of two odd integers is even

Claim. If $m$ and $n$ are odd integers, then $m + n$ is even.

Proof. By the definition of odd, there must be integers $j$ and $k$ such that $m = 2j + 1$ and $n = 2k + 1$. Then

Since $j + k + 1$ is an integer, $m + n$ matches the definition of even. $\blacksquare$

Example 1's skeleton is not a one-off. The next two facts reuse it, and both feed directly into the $\sqrt{2}$ proof later in this lecture.

Example 2: if $n$ is odd, then $n^2$ is odd

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

Proof. By the definition of odd, there must be an integer $k$ such that $n = 2k + 1$. Then

Since $2k^2 + 2k$ is an integer, $n^2$ matches the definition of odd. $\blacksquare$

Example 3: if $n^2$ is even, then $n$ is even

Try proving this directly and you hit a wall: assuming $n^2$ is even gives an equation about $n^2$, and there is no clean algebraic road from a fact about $n^2$ down to a fact about $n$.

The way out is the contrapositive: the statement "if $P$, then $Q$" is true exactly when "if not $Q$, then not $P$" is true, because each one says there is no situation where $P$ is true and $Q$ is false. Proving either form proves both.

Claim. If $n$ is an integer and $n^2$ is even, then $n$ is even.

Proof. We prove the contrapositive: if $n$ is not even, then $n^2$ is not even. Every integer is either even or odd and not both (divide by 2 and look at the remainder, which is 0 or 1), so "not even" means odd, and the contrapositive reads: if $n$ is odd, then $n^2$ is odd. That is exactly Example 2, already proved. Since a statement and its contrapositive are equivalent, the claim holds. $\blacksquare$

Proof by Contradiction

To prove a statement $P$ by contradiction, we assume $P$ is false and derive something impossible. Valid steps from a true assumption can only produce truths, so if the derivation lands on something impossible, the assumption must have been false, and $P$ is true. The general approach is:

1. Announce it: "Suppose, for the sake of contradiction, that $P$ is false."
2. Write out exactly what "not $P$" says.
3. Derive a statement that is obviously false.
4. Conclude $P$.

Example 4: there is no smallest positive rational number

Definition. A real number $x$ is rational if $x = a/b$ for some integers $a$ and $b$ with $b \neq 0$, and irrational otherwise.

Claim. There is no smallest positive rational number.

Proof. Suppose, for the sake of contradiction, that there does exist a smallest positive rational number. Let's call it $q$. By the definition of rational, $q = a/b$ for some integers $a$ and $b$ with $b \neq 0$. Then $q/2 = a/(2b)$, and since $2b$ is a nonzero integer, $q/2$ is rational by that same definition. Moreover, half of a positive number is positive, so $0 < q/2$, and since $q$ is positive, $q/2 < q$. So $q/2$ is a positive rational smaller than the smallest positive rational, which is impossible. Therefore, no smallest positive rational exists. $\blacksquare$

Example 5: $\sqrt{2}$ is irrational

Claim. $\sqrt{2}$ is irrational.

Proof. Suppose, for contradiction, that $\sqrt{2}$ is rational. Then $\sqrt{2} = a/b$ for some integers $a, b$ with $b \neq 0$. A rational number has many such forms ($1/2 = 2/4 = 3/6 = \cdots$), and we are free to pick which form to work with, so pick one in lowest terms, meaning $a$ and $b$ share no common factor greater than 1. Why is this possible? If our $a$ and $b$ do share a common factor $d > 1$, divide both by $d$: the fraction's value is unchanged and the numerator shrinks. Repeating this cannot go on forever (the numerator's absolute value gets strictly smaller each time), so it eventually stops, and it stops exactly when no common factor greater than 1 remains. We may therefore assume from the start that $a$ and $b$ share no common factor greater than 1. Squaring both sides and clearing denominators:

So $a^2$ is even. By Example 3, $a$ is even, say $a = 2c$. Substituting: $2b^2 = 4c^2$, so $b^2 = 2c^2$, so $b^2$ is even, so $b$ is even. Now $a$ and $b$ are both even, contradicting the choice that they share no common factor greater than 1. Hence $\sqrt{2}$ is irrational. $\blacksquare$

Induction

Induction proves statements of the form "for every natural number $n \geq n_0$, $P(n)$ holds."

Principle of mathematical induction. Let $P(n)$ be a statement about a natural number $n$, and let $n_0$ be a natural number. If

1. $P(n_0)$ holds (base case), and
2. for every $n \geq n_0$, if $P(n)$ holds then $P(n+1)$ holds (inductive step, where the assumption "$P(n)$ holds" is the inductive hypothesis),

then $P(n)$ holds for every $n \geq n_0$.

Why do these two parts cover every case? The base case establishes the claim for one concrete value, $n_0$. On its own that proves nothing about the rest. The inductive step is what reaches them: it shows that truth at any value forces truth at the next one, so the base case sets off a chain. $P(n_0)$ holds by the base case; the inductive step applied at $n_0$ then gives $P(n_0 + 1)$; applied again it gives $P(n_0 + 2)$; and every $n \geq n_0$ is reached after finitely many of these hand-offs. The usual picture is a line of dominoes: the base case tips the first one, and the inductive step guarantees each domino knocks over the next.

In this course an induction proof must label all three parts. Here is the template at full detail.

Example 6: the sum of the first $n$ positive integers

Claim. For every $n \geq 1$: $\displaystyle\sum_{i=1}^{n} i = \frac{n(n+1)}{2}$.

Proof. By induction on $n$. Let $P(n)$ be the statement $\sum_{i=1}^{n} i = n(n+1)/2$.

Base case ($n = 1$). The left side is $1$; the right side is $1 \cdot 2 / 2 = 1$. Equal, so $P(1)$ holds.

At this point we know the claim holds for one value, $n = 1$, and nothing more. The inductive step must supply every remaining case. We do this by showing that the claim holding at any $n$ forces it to hold at $n + 1$: combined with the base case, that reaches $2$, then $3$, and so on through every $n \geq 1$.

Inductive step. Let $n \geq 1$ and assume the inductive hypothesis $P(n)$: $\sum_{i=1}^{n} i = n(n+1)/2$. We must show $P(n+1)$. Splitting off the last term of the sum and applying the hypothesis:

which is exactly $P(n+1)$. By induction, $P(n)$ holds for all $n \geq 1$. $\blacksquare$

Example 7: guess the formula, then prove it

Induction shines when paired with a guess-then-verify workflow.

Question. What is $1 + 3 + 5 + \cdots + (2n - 1)$, the sum of the first $n$ odd numbers?

Compute small cases: $1$, $1+3 = 4$, $1+3+5 = 9$, $1+3+5+7 = 16$.

The values are $1, 4, 9, 16$: perfect squares!

Claim. For every $n \geq 1$: $\displaystyle\sum_{i=1}^{n} (2i - 1) = n^2$.

Proof. By induction on $n$. Base case ($n=1$): both sides are $1$. Inductive step: let $n \geq 1$, assume $\sum_{i=1}^{n}(2i-1) = n^2$, and split off the last term:

Example 8: the base case is a choice

Induction does not have to start at $1$, and sometimes it cannot.

Claim. For every $n \geq 5$: $2^n > n^2$.

First, why $5$? Check small cases: at $n = 2, 3, 4$ we get $4 = 4$, $8 < 9$, $16 = 16$, so the claim is false! At $n = 5$ we get $32 > 25$.

Proof. By induction on $n$. Base case ($n = 5$): $2^5 = 32 > 25 = 5^2$.

Inductive step. Let $n \geq 5$ and assume $2^n > n^2$. We must show $2^{n+1} > (n+1)^2$. Justifying every link:

A famous failure mode: all horses are the same color

Induction can go wrong in a way that is easy to miss, and the classic demonstration is a "proof" of something absurd. Read it and try to find the flaw before continuing; every step will look reasonable.

"Claim." In any group of $n$ horses, all the horses are the same color.

"Proof." By induction on $n$. Base case ($n = 1$): a group of one horse is trivially all one color. Inductive step: let $n \geq 1$ and assume any group of $n$ horses is all one color. Take any group of $n + 1$ horses, numbered $1$ through $n+1$. Removing horse $1$ leaves the group $\{2, \ldots, n+1\}$ of $n$ horses, all one color by the hypothesis. Removing horse $n+1$ instead leaves the group $\{1, \ldots, n\}$, also all one color by the hypothesis. The two groups share horses $2$ through $n$, so both groups have the color of the shared horses, and all $n + 1$ horses are the same color. By induction, every group of horses is monochrome, so all horses are the same color. "$\blacksquare$"

The flaw: the gluing move needs the two groups to overlap. The shared horses $\{2, \ldots, n\}$ carry the color from one group to the other, but when $n = 1$ (that is, going from $1$ horse to $2$), the two groups are $\{2\}$ and $\{1\}$ and the shared set is empty: nothing links the two horses' colors. The inductive step is perfectly valid for every $n \geq 2$ and fails only at $n = 1$, which is exactly the hand-off the base case feeds. The chain never gets started, and one broken link is all it takes.

Strong induction

Sometimes $P(n+1)$ does not follow from $P(n)$ but from earlier cases further back. Strong induction allows that.

Principle of strong induction. Let $P(n)$ be a statement about a natural number $n \geq n_0$. If for every $n \geq n_0$, the implication "if $P(k)$ holds for all $n_0 \leq k < n$, then $P(n)$ holds" is true, then $P(n)$ holds for every $n \geq n_0$. (The base case is the $n = n_0$ instance of the implication, where the hypothesis is vacuous and $P(n_0)$ must be shown outright.)

Example 9: every integer at least 2 is a product of primes

Definition. An integer $p \geq 2$ is prime if its only positive divisors are $1$ and $p$. A single prime counts as a product of primes (a product with one factor).

Claim. Every integer $n \geq 2$ is a product of primes.

Proof. By strong induction on $n$. Let $n \geq 2$ and assume every integer $k$ with $2 \leq k < n$ is a product of primes. If $n$ is prime, it is a product of primes by itself. Otherwise, $n$ has a divisor other than $1$ and $n$, so $n = ab$ with $2 \leq a, b < n$. By the inductive hypothesis applied to each factor, $a$ and $b$ are products of primes, so their product $n$ is too. $\blacksquare$

Example 10: there are infinitely many primes

The capstone: a proof by contradiction that also uses the strong-induction fact we just proved.

Claim. There are infinitely many primes.

Proof. Suppose, for the sake of contradiction, that there are only finitely many primes. List all of them as $p_1, p_2, \ldots, p_m$. Let

Since $N \geq 2$, Example 9 says $N$ is a product of primes, so some prime $p$ divides $N$. That $p$ appears on our list, so $p$ also divides the product $p_1 p_2 \cdots p_m$. Then $p$ divides the difference $N - p_1p_2\cdots p_m = 1$, which is impossible for a prime. So the list could not have contained all primes, and thus there must be infinitely many. $\blacksquare$

Quantifiers

Every definition in this course is a quantified statement: to prove "for all $x$, $P(x)$" you take an arbitrary $x$; to prove "there exists $x$ with $P(x)$" you exhibit one; and to prove either by contradiction you must negate it correctly. The negation rules:

• not (for all $x$: $P(x)$) is: there exists $x$ with not $P(x)$.
• not (there exists $x$ with $P(x)$) is: for all $x$: not $P(x)$.

When quantifiers are nested, apply these rules one layer at a time: the "not" starts outside, moves past each quantifier in turn (flipping for-all to there-exists and there-exists to for-all), and finally lands on the innermost statement. For example:

The quantifiers keep their order; only their flavors flip, and the "not" ends up attached to the innermost claim, where it usually simplifies (not "$f(n) \leq c \cdot g(n)$" becomes "$f(n) > c \cdot g(n)$"). Order itself matters too: "every lock has a key that opens it" and "there is a key that opens every lock" are different claims.

You will use this mechanically in Lecture 4 - Asymptotic Notation and Growth Rates: the definition of $f(n) = O(g(n))$ has the form "there exist $c$ and $n_0$ such that for all $n \geq n_0$, $f(n) \leq c \cdot g(n)$", so proving a function is not $O(g(n))$ means proving "for all $c$ and $n_0$ there exists $n \geq n_0$ with $f(n) > c \cdot g(n)$": given an arbitrary $c$ and $n_0$, you must produce a specific $n \geq n_0$ that violates the inequality. The same discipline is the entire content of the pumping lemma arguments in Lecture 7 - The Pumping Lemma and Nonregular Languages.

Exercises

These are not collected or graded, they are your study material! The warm-ups and exams will look alot like them. Each exercise is a variation of an example above.

Exercise 1

Prove that the sum of an odd integer and an even integer is odd (see Example 1).

Exercise 2

Prove by contradiction that there is no largest negative rational number (see Example 4).

Exercise 3

Prove that $\sqrt{3}$ is irrational (see Example 5). Where does your argument break if you try to run it on $\sqrt{4}$?

Exercise 4

Prove by induction that for every $n \geq 1$: $\displaystyle\sum_{i=1}^{n} i^2 = \frac{n(n+1)(2n+1)}{6}$ (Example 6's rhythm).

Exercise 5

Prove by induction that $n^3 - n$ is divisible by $3$ for every $n \geq 1$ (Example 6's rhythm with different algebra).

Exercise 6

Find the smallest integer $n_0$ such that $2^n > 10 n$ for every $n \geq n_0$, then prove your answer by induction (Example 8, both halves).

Exercise 7

Write out the negation of: "for every $\epsilon > 0$ there exists $\delta > 0$ such that for all $x$, if $|x| < \delta$ then $|f(x)| < \epsilon$." Push the negation all the way inward, one quantifier at a time.