1.15 Proof by induction, contradiction and counterexample

A proof is a chain of logical steps that shows a statement must be true in every case it covers, not only in the cases that have been checked. Direct proof, where you start from known facts and work forwards to the result, is not always the easiest route. Three further methods extend what can be proved: induction, for statements about every positive integer; contradiction, for statements that are hard to attack directly; and counterexample, for showing that a general claim is false.

These methods are used throughout mathematics. Induction proves the formulas for sums of series and De Moivre's theorem; contradiction proves that $\sqrt{2}$ is irrational and that the primes never run out; a single counterexample is enough to destroy a conjecture that has been checked thousands of times.

Statements and the logic of proof

Statements, implications and quantifiers

A mathematical statement is a sentence that is either true or false, such as "$7$ is prime" or "$x^2 \ge 0$ for all real $x$". A conjecture is a statement believed to be true but not yet proved. Once it has been proved it becomes a theorem.

Many statements are implications of the form "if $A$, then $B$", written $A \Rightarrow B$. Here $A$ is the condition (the hypothesis) and $B$ is the conclusion. The statement $A \Rightarrow B$

Statements also carry quantifiers. "For all" (written $\forall$) claims that something holds in every case; "there exists" (written $\exists$) claims that it holds in at least one case. The two kinds need opposite amounts of work. To prove a "for all" statement, a general argument is needed. To disprove one, a single case where it fails is enough.

Three methods of proof

Proof by mathematical induction

The idea behind induction

Suppose $P(n)$ is a statement about a positive integer $n$, such as

Checking $n = 1, 2, 3, \ldots, 1000$ does not prove it for every $n$: there are infinitely many cases. Proof by induction gets round this by proving two finite things that together cover every case. First, $P(1)$ is true. Second, for any positive integer $k$

Together these give an endless chain. $P(1)$ is true; then $P(1) \Rightarrow P(2)$ makes $P(2)$ true; then $P(2) \Rightarrow P(3)$

The inductive step does not assume that $P(k)$ is actually true for every $k$; that would be assuming the result. It proves a conditional statement, $P(k) \Rightarrow P(k+1)$, which is a fact about how each case is linked to the next. Induction is a natural way to prove results about sequences and series, because each term is built from the one before: the structure of the proof matches the structure of the object.

Writing an induction proof

An induction proof has four parts, and each one should appear in the written proof.

1. Base case. Substitute the first value (usually $n = 1$) into both sides, evaluate each side separately, and state that they are equal, so $P(1)$ is true.

2. Assumption. Write "Assume that $P(k)$ is true for some $k \in \mathbb{Z}^+$

The Khan Academy video proves the formula $1 + 2 + \dots + n = \frac{n(n+1)}{2}$ with this structure.

YouTube

Proving formulas for series

For a series, the target $P(k+1)$ always contains the sum to $k$ terms plus one extra term. Once it is split off, the assumption replaces the sum to $k$ terms with its formula.

After that, the work is algebra: factorise, and aim for the formula with $k+1$ in place of $n$. Writing the target down first makes the algebra much easier, because you know what form to aim for.

The next example needs more algebra. The key technique is to take out the common factor $(k+1)$ straight away rather than expanding everything, since the target also contains $(k+1)$.

Series with fractions or powers work in the same way, but more care is needed when combining terms over a common denominator or collecting powers of 2.

Proving divisibility results

A statement such as "$5^n - 1$ is divisible by $4$" means $5^n - 1 = 4m$ for some integer $m$

When the expression has two powers, such as $7^n - 3^n$, the substitution method is awkward. Instead, add and subtract a term so that the $k$ expression appears as a block. This is often called the "add and subtract" technique.

Polynomial expressions are handled by expanding $(k+1)^3$ and grouping the terms of the assumption together. For example, to prove that $n^3 + 2n$ is divisible by $3$, assume $k^3 + 2k = 3m$

which is $3(m + k^2 + k + 1)$, a multiple of $3$. With the base case $1^3 + 2(1) = 3$

Proving inequalities

Some statements are true only from a certain integer onwards, so the base case is not always $n = 1$. In the inductive step for an inequality, chains of the form $a = b > c \ge d$ are used, and each $>$ or $\ge$

The graph suggests where an induction proof of $2^n > n^2$ should start. At $n = 1$ the statement is true ($2 > 1$), but it fails for $n = 2, 3, 4$

The same pattern proves that $n! > 2^n$ for all integers $n \ge 4$, using factorials. The base case is $4! = 24 > 16 = 2^4$

where the last step uses $k + 1 > 2$. Inequalities can also contain a second variable. The next example, known as Bernoulli's inequality, needs a condition on $x$ so that multiplying an inequality by $1 + x$ keeps its direction.

Proving formulas for derivatives

The notation $\frac{d^n y}{dx^n}$, or $f^{(n)}(x)$

Formulas for $n$th derivatives often contain $(-1)^n$, which makes the sign alternate, and $n!$, which collects the factors brought down by repeated use of the power rule. For $f(x) = \frac{1}{x} = x^{-1}$

In the inductive step, differentiating $(-1)^k\, k!\, x^{-(k+1)}$ brings down the factor $-(k+1)$:

which is the formula with $n = k + 1$. Together with the base case $f'(x) = -\frac{1}{x^2} = \frac{(-1)^1\, 1!}{x^2}$

De Moivre's theorem and recurrence relations

De Moivre's theorem states that $(\cos\theta + i\sin\theta)^n = \cos n\theta + i\sin n\theta$. Its proof for positive integers $n$

Induction also proves a closed formula for a sequence defined by a recurrence relation. For example, if $u_1 = 1$ and $u_{n+1} = 2u_n + 1$

so the formula holds for $n = k + 1$ as well, and by induction it holds for all $n \in \mathbb{Z}^+$.

Why both parts are needed

A proof that skips either part is not valid, even if the part that is written is correct. The base case alone proves only one case. The inductive step alone proves only a chain of "if… then…" links, which may never start.

The opposite flaw occurs when a step that looks general fails for one particular value of $k$. In the well-known false "proof" that all horses are the same colour, the step from $k$ horses to $k + 1$ uses two overlapping groups of $k$ horses, but when $k = 1$

Proof by contradiction

The method

Some statements are hard to prove directly because they say that something does not exist or cannot happen: "$\sqrt{2}$ is not a fraction", "there is no largest prime". Proof by contradiction turns this around. It assumes the statement is false and shows that this assumption leads, by valid steps, to something impossible: a statement that contradicts the assumption itself or a known fact. Since valid reasoning from a true assumption cannot reach a false conclusion, the assumption must be false, so the original statement is true.

Negating a statement

The first step is to write down the negation correctly. The negation of a statement is true exactly when the statement is false. It is usually not the "opposite" in an everyday sense.

Proving that the square root of 2 is irrational

A rational number can be written as $\frac{p}{q}$ with $p, q \in \mathbb{Z}$ and $q \ne 0$

The main proof now follows. Its contradiction is that a fraction assumed to be in its lowest terms turns out to have a common factor of $2$.

There are infinitely many primes

A prime number is a positive integer greater than 1 whose only positive factors are 1 and itself. Every integer greater than 1 is either prime or a product of primes, so every integer greater than 1 has at least one prime factor. The following proof, which goes back to Euclid, uses this fact.

Further proofs by contradiction

The same three steps prove many other results. In each case, identify what the negation allows you to write down (an equation, a largest number, a fraction), then look for a property that cannot hold, such as an odd number equalling an even one.

Disproof by counterexample

One case is enough

A statement that claims something for all cases is false if it fails in even one case. Such a case is a counterexample. It must satisfy every condition in the statement, and it must make the conclusion false.

To disprove a statement by counterexample, give the specific value, check that it meets the conditions, and evaluate it to show clearly that the conclusion fails. No general argument is needed.

Checking many cases is not a proof

Finding cases where a statement works never proves a "for all" statement, however many cases are checked. A classic illustration is Euler's polynomial

For $n = 0, 1, 2, \ldots, 39$, every value is prime: $41, 43, 47, 53, 61, \ldots, 1601$. Forty prime values in a row suggest the conjecture "$n^2 + n + 41$

which is not prime. Rewriting the expression shows why $n = 40$ fails without any calculator work, and $n = 41$ fails too: $41^2 + 41 + 41 = 41 \times 43$

The mathematician Pierre de Fermat conjectured that every number of the form $F_n = 2^{2^n} + 1$ is prime. The first five, $3, 5, 17, 257, 65537$

Counterexamples also correct mistaken beliefs in calculus. A common belief is that a stationary point must be a maximum or a minimum.

Choosing a method and spotting flawed proofs

Which method to use

The form of the statement usually suggests the method.

A statement about integers can sometimes be proved in more than one way. For example, $n^3 - n = (n - 1)n(n + 1)$ is a product of three consecutive integers, so it is divisible by $6$ by a direct argument, and the same result can also be proved by induction. Any valid proof is acceptable.

Common flaws in proofs

A proof is only as strong as its weakest step. The following flaws appear often, both in student work and in deliberately misleading "proofs".

• Proof by examples. Checking cases is not a proof of a "for all" statement (Euler's polynomial).

• Circular reasoning. Using the result, or something equivalent to it, as a step in its own proof.

• Working backwards with steps that cannot be reversed. Starting from the statement to be proved and reaching something true proves nothing unless every step can be reversed. Squaring is not reversible: from $-1 = 1$, squaring gives $1 = 1$, which is true, yet $-1 = 1$ is false.

• Dividing by zero. Dividing both sides by an expression that might equal zero.

• Confusing a statement with its converse.

Exam-style questions on proof

Proof questions test the structure of the argument as much as the algebra. In induction, marks are usually given separately for the base case, the assumption, the inductive step and the conclusion, so a proof with correct algebra but no conclusion loses a mark. Contradiction and counterexample questions often come in parts that build on each other ("hence").

The second question combines a direct argument, a contradiction proof that uses it, and a counterexample.

Self-check

• To do:

  I can explain why both the base case and the inductive step are needed in a proof by induction.

• To do:

  I can write a complete induction proof with a base case, an assumption, an inductive step and a conclusion.

• To do:

  I can prove formulas for series, divisibility results, inequalities and $n$th derivatives by induction.

• To do:

  I can prove De Moivre's theorem for positive integers by induction.

• To do:

  I can write down the negation of a statement and use it to start a proof by contradiction.

• To do:

  I can prove that $\sqrt{2}$