Proof Methods and Strategies

There are several ways to prove a mathematical statement. Some are straightforward, some are sneaky, and some make you wonder who decided mathematics needed this many ways to say "yes, this is true."

What is a Proof?

A proof is a logical argument used to establish that a mathematical statement must be true.

Many mathematical statements can be written as an implication:

Here, p is the hypothesis and q is the conclusion.

Different statements can require different strategies. The sections below cover the main proof methods in the order used by this documentation.

Proof Methods at a Glance

1. Direct Proof

A direct proof is usually the first method to try.

To prove:

assume that p is true and use definitions, known facts, algebra, and logical reasoning to establish q.

Example

Prove that if p and q are odd integers, then p + q is even.

Since both numbers are odd, there are integers m and n such that:

p = 2m + 1

q = 2n + 1

Therefore:

p + q = (2m + 1) + (2n + 1) = 2(m + n + 1)

The result is divisible by 2, so p + q is even.

2. Proof by Contraposition

The contrapositive of:

is:

These statements are logically equivalent. Therefore, proving the contrapositive proves the original implication.

Example

Prove that if n² is even, then n is even.

Rather than proving this directly, prove:

If n is odd:

n = 2k + 1

Therefore:

n² = (2k + 1)² = 4k² + 4k + 1 = 2(2k² + 2k) + 1

Thus n² is odd. Therefore, by contraposition, if n² is even, n must be even.

3. Vacuous Proof

A vacuous proof establishes an implication because its hypothesis is false.

Remember the truth table for implication:

Therefore, if you can show that p cannot be true, then:

is automatically true, regardless of whether q is true or false.

Example

Consider:

The hypothesis is false because:

Therefore the implication is vacuously true.

4. Trivial Proof

A trivial proof establishes an implication because the conclusion is already known to be true.

More precisely, if q is true independently of p, then p → q is true regardless of the value of p.

Example

Consider:

The conclusion:

is true regardless of the number of employees. Therefore, the implication is true.

5. Proof by Contradiction: Proving p

To prove a statement p by contradiction, assume that p is false.

Then use that assumption to derive something impossible, such as:

Since assuming ¬p leads to a contradiction, the assumption must be false. Therefore, p is true.

Example

Prove that there is no largest integer.

Assume the opposite: suppose that n is the largest integer.

But n + 1 is also an integer, and:

This contradicts the assumption that n was the largest integer.

Therefore, there is no largest integer.

6. Proof by Contradiction: Proving p → q

To prove an implication:

assume that the hypothesis is true while the conclusion is false:

Then derive a contradiction.

Example

Suppose:

We want to prove:

Assume the opposite:

The equation gives:

Since y ≠ 0, divide by y:

This is impossible. Therefore the assumption y ≠ 0 must be false, and:

7. Counterexample

A counterexample is used to disprove a universal statement.

If someone claims:

you only need to find one value of x for which P(x) is false.

One counterexample is enough to destroy a universal claim.

Example

Consider the claim:

Choose:

Then:

but y ≠ 0.

Therefore, the original universal claim is false.

8. Exhaustive Proofs and Proof by Cases

An exhaustive proof checks every possible element or possibility in the relevant domain.

A proof by cases divides the problem into distinct cases and proves the conclusion in every case.

The important requirement is that the cases must cover all possibilities.

Example: Even or Odd

Every integer is either even or odd. Therefore, to prove a statement about every integer, we can consider those two cases.

Example

Prove that for every integer n, n² + n is even.

Case 1: n is even.

n = 2k

n² + n = 4k² + 2k = 2(2k² + k)

Therefore, the expression is even.

Case 2: n is odd.

n = 2k + 1

n² + n = (2k + 1)² + (2k + 1) = 2(2k² + 3k + 1)

Therefore, the expression is also even.

Since every integer is either even or odd, all possibilities have been covered.

Non-Traditional Proofs
(Aka I was not taught this wtf is this)

The methods above are the main proof styles introduced first in this documentation.

The following techniques are also useful, but they are being kept separately because they are more specialized, combine multiple proof techniques, or may not appear in every introductory treatment of proofs.

Existence Proofs

An existence proof establishes that at least one object with a specified property exists.

A constructive existence proof gives an actual example, called a witness.

Example

Show that there exists a positive integer satisfying:

Factor:

Therefore n = 4 is a positive integer satisfying the equation.

Thus, the required object exists.

Uniqueness Proofs

A uniqueness proof establishes that exactly one object satisfies a property.

It generally consists of two parts:

1. Show that a solution exists.
2. Show that any solution must be the same solution.

Example

Consider:

where a ≠ 0.

Solving gives:

So a solution exists.

If another value y also satisfies the equation, then:

Solving gives:

Therefore y = x, so the solution is unique.

Mathematical Induction

Mathematical induction is a method commonly used for statements involving positive integers.

It consists of two main steps:

Base Case

Prove that the statement is true for the initial value.

Inductive Step

Assume the statement is true for some integer k, then use that assumption to prove that it is true for k + 1.

Example

Prove:

The base case n = 1 works:

Assume:

Then:

1 + 2 + ... + k + (k + 1) = k(k + 1) / 2 + (k + 1)

= (k + 1)(k + 2) / 2

which is the required expression for k + 1.

If and Only If Proofs

An "if and only if" statement is written:

This means both directions must be proven:

Therefore, proving an iff statement normally requires two separate arguments.

Without Loss of Generality

Without loss of generality, usually written as WLOG, is a strategy for reducing the number of cases in a proof.

It can be used when the other cases can be handled by essentially the same argument, usually because of symmetry.

Forward and Backward Reasoning

Forward Reasoning

Start with the known information and work toward the conclusion.

Backward Reasoning

Start with the conclusion and ask what would be sufficient to establish it.

Backward reasoning is often useful while discovering a proof. The finished proof can then be written forward from the assumptions to the conclusion.

Adapting Existing Proofs

A new theorem may resemble one that has already been proven.

Instead of inventing an entirely new argument, you can examine the existing proof and determine whether its structure can be adapted to the new statement.

This is especially useful when two theorems rely on similar assumptions or definitions.

Summary

Proofs are not just about knowing the answer. They are about showing why the answer must follow from the assumptions.