11.7 Proof strategies

Mathematical proofs demonstrate the validity of statements through logical arguments. They form the backbone of rigorous mathematical thinking, and learning different proof strategies gives you a toolkit for tackling problems across every branch of math.

This guide covers the major proof types, key techniques, how to write and verify proofs, and common mistakes to watch out for.

Types of mathematical proofs

Each proof type has a different approach to establishing truth. Knowing when to reach for each one is half the battle.

Direct proof

A direct proof starts with known facts and moves step by step toward the conclusion. You build a chain of reasoning from hypothesis to conclusion, using definitions, axioms, and previously proven theorems along the way.

How it works:

1. State your hypothesis (what you're given).
2. Apply definitions, known theorems, or algebraic manipulation.
3. Arrive at the conclusion through a logical chain.

For example, to prove that the sum of two even integers is even, you'd start from the definition of even numbers ($a = 2m$, $b = 2n$), add them ($a + b = 2m + 2n = 2(m+n)$), and show the result fits the definition of even.

Direct proofs are the most common type in algebra and number theory.

Proof by contradiction

This strategy assumes the opposite of what you want to prove, then shows that assumption leads to a logical impossibility. Since the negation can't be true, the original statement must be.

How it works:

1. Assume the negation of the statement you want to prove.
2. Reason logically from that assumption.
3. Arrive at a contradiction (something that violates a known fact or definition).
4. Conclude the original statement is true.

The classic example is proving that $\sqrt{2}$ is irrational. You assume it is rational, write it as $\frac{a}{b}$ in lowest terms, and eventually show both $a$ and $b$ must be even, contradicting the "lowest terms" assumption.

Reach for this method when a direct proof feels hard to construct.

Proof by contrapositive

Every "if P, then Q" statement is logically equivalent to "if not Q, then not P." A contrapositive proof proves this equivalent version instead.

Sometimes proving "if not Q, then not P" is much more straightforward than proving "if P, then Q" directly. This technique shows up often in abstract algebra and topology.

Proof by induction

Induction is your go-to method for proving statements about all natural numbers (or any well-ordered set).

The two steps:

1. Base case: Prove the statement holds for the starting value (usually $n = 0$ or $n = 1$).
2. Inductive step: Assume the statement is true for some arbitrary $n = k$ (this is the inductive hypothesis). Then prove it must also be true for $n = k + 1$.

Once both steps are established, the statement holds for all values from the base case onward, like a chain of dominoes falling. Induction is widely used in discrete mathematics and computer science for proving summation formulas, divisibility properties, and algorithm correctness.

Key proof techniques

These are the underlying logical tools you'll use inside any proof type.

Logical reasoning

All proofs rest on drawing valid conclusions from premises using rules of inference. The most important ones to know:

• Modus ponens: If P implies Q, and P is true, then Q is true.
• Modus tollens: If P implies Q, and Q is false, then P is false.
• Syllogism: If P implies Q and Q implies R, then P implies R.

These rules, drawn from propositional and predicate logic, are the building blocks of every proof you'll write.

Deductive vs. inductive reasoning

These terms describe two directions of reasoning:

• Deductive reasoning moves from general principles to specific conclusions. Mathematical proofs are deductive: they provide certainty.
• Inductive reasoning generalizes from specific observations to broader claims. This is how conjectures are formed, but it doesn't constitute proof on its own.

Don't confuse inductive reasoning (observing patterns) with proof by induction (a formal proof technique). They share a name but work very differently.

Counterexamples

A single counterexample is enough to disprove a universal claim. If someone claims "all prime numbers are odd," you just point to $2$, which is prime and even. Done.

Finding good counterexamples takes creativity. You're looking for the specific case that breaks the pattern. This is one of the most efficient tools in math: it can demolish a conjecture in one line.

Exhaustive proof

An exhaustive proof checks every possible case. This only works when the number of cases is finite and manageable. For instance, you could prove a property about all single-digit prime numbers by checking 2, 3, 5, and 7 individually.

This method is common in combinatorics and finite mathematics, and it guarantees completeness since no case is left unchecked.

Elements of a proof

Understanding the anatomy of a proof helps you both write and read them more effectively.

Hypothesis and conclusion

Most theorems follow an "if-then" structure: If [hypothesis], then [conclusion]. The hypothesis states your given conditions; the conclusion is what you need to prove. Clearly identifying these two components before you start writing is essential. Many students struggle with proofs simply because they haven't pinpointed exactly what they're given and what they need to show.

Assumptions and givens

Givens are facts known to be true in the context of the problem. Assumptions are additional conditions you accept without proof for the current argument (like axioms or previously proven theorems).

Always state these explicitly. Leaving assumptions unstated is one of the fastest ways to introduce errors or circular reasoning.

Logical steps and justifications

The body of a proof is a series of statements, each supported by a justification. Every step should cite a definition, theorem, axiom, or logical rule. If you can't justify a step, it's either wrong or you're missing something.

These steps might involve algebraic manipulation, geometric construction, or logical deduction, but each one must follow from what came before.

QED or conclusion statement

QED stands for quod erat demonstrandum ("which was to be demonstrated"). It signals that you've reached the desired conclusion and the proof is complete. Many modern texts use a filled square (■) or simply write "This completes the proof." Whatever the convention, the point is the same: you're declaring the argument finished.

Common proof strategies

These are higher-level approaches for planning how to attack a proof.

Forward vs. backward reasoning

• Forward reasoning starts from what you know and works toward the conclusion. This is the natural approach for direct proofs.
• Backward reasoning starts from the conclusion you want and asks, "What would I need to be true for this to follow?" Then you work backward until you reach something you know.

Backward reasoning is especially helpful when the goal is clear but the path isn't. In practice, many proofs are discovered using a mix of both directions.

Breaking into cases

When a problem has distinct scenarios that require different reasoning, split it into exhaustive, mutually exclusive cases and prove each one separately. A classic example: proving a property for all integers by handling even and odd cases separately.

The key requirement is that your cases must cover every possibility with no gaps.

Proof by example (existence proofs)

Showing one concrete example proves that something exists, but it does not prove a statement is true in general. For instance, exhibiting a specific graph with a certain property proves such graphs exist, but says nothing about all graphs.

Use this for existence statements ("there exists...") and for providing counterexamples.

Diagrammatic proofs

Visual representations like diagrams, Venn diagrams, or geometric constructions can illustrate relationships and provide intuition. They're common in geometry and graph theory. While a diagram alone usually isn't a formal proof, it can guide your reasoning and make your argument clearer to readers.

Advanced proof methods

These methods handle more complex situations and often combine multiple strategies.

Proof by mathematical induction

This was introduced earlier under "Types of mathematical proofs." In advanced settings, you'll encounter variations:

• Strong induction: Instead of assuming the statement holds just for $k$, you assume it holds for all values up to $k$, then prove it for $k + 1$.
• Structural induction: Used in computer science to prove properties of recursively defined structures like trees or lists.

The core logic is the same: establish a base case, then show the truth propagates forward.

Proof by construction

A constructive proof demonstrates that a mathematical object exists by explicitly building it. Rather than just arguing something must exist, you produce it. For example, to prove there exists a function with certain properties, you define one and verify it works.

This is often more satisfying than nonconstructive proofs because you walk away with a concrete example.

Nonconstructive proofs

A nonconstructive proof shows something exists without ever producing it. These often rely on proof by contradiction or the law of excluded middle. For instance, you can prove transcendental numbers exist by showing the set of algebraic numbers is countable while the reals are uncountable, so transcendental numbers must exist, even though this argument doesn't name a single one.

Probabilistic proofs

The probabilistic method (pioneered by Paul Erdős) proves that an object with a desired property exists by showing that a randomly chosen object has a nonzero probability of having that property. This is widely used in combinatorics and in analyzing randomized algorithms in computer science.

These proofs provide certainty about existence, even though the method involves probability.

Proof writing skills

A correct proof that nobody can follow isn't much use. Clear writing matters.

Clear and concise language

Use precise mathematical terms and avoid ambiguity. Explain complex ideas simply, but don't sacrifice accuracy. Transitional phrases like "since," "therefore," and "it follows that" help guide the reader through your logic.

Cut unnecessary words. If a sentence doesn't advance the argument, remove it.

Proper notation and symbolism

Use standard mathematical notation consistently throughout your proof. If you introduce any non-standard symbols, define them before first use. Strike a balance between symbolic expressions and verbal explanations: a proof that's all symbols is hard to read, and one that's all words can be imprecise.

Logical flow and organization

Structure your proof so each statement follows logically from what came before. Use numbered steps or clear paragraphs to separate distinct parts of the argument. A reader should never have to wonder, "Where did that come from?"

Addressing all cases

If your proof involves cases, make sure you've covered every possibility. Explicitly state when a case is trivial or follows from a previous argument. Overlooking an edge case is one of the most common reasons proofs are incomplete.

Proof verification

Writing a proof is only half the job. Checking it is equally important.

Checking for logical gaps

Go through each step and ask: "Is this justified?" Every claim should be supported by a definition, axiom, theorem, or valid inference rule. Pay special attention to the transition from the last step to the conclusion, since that's where gaps often hide.

Identifying hidden assumptions

Look for unstated assumptions you might be relying on. Are you using a theorem whose hypotheses you haven't verified? Are you assuming something that actually depends on the conclusion (circular reasoning)? Scrutinize every step for implicit conditions.

Peer review process

Having someone else read your proof is one of the best ways to catch errors. A fresh pair of eyes can spot logical gaps, unclear reasoning, or hidden assumptions that you've become blind to. This mirrors the formal peer review process in mathematical publications.

Computer-assisted proofs

Software tools like Coq and Isabelle can formally verify proofs, which is especially valuable for proofs involving massive case analyses or complex computations. The Four Color Theorem, for example, was proved with significant computer assistance. These tools raise interesting philosophical questions about what constitutes understanding in mathematics, but their practical value for verification is clear.

Applications of proofs

Proof techniques extend well beyond pure math.

Theoretical mathematics

Proofs establish new mathematical knowledge, resolve open conjectures, and reveal unexpected connections between different areas of math. Fields like group theory and topology are built entirely on chains of proven results.

Computer science algorithms

Proofs are used to verify that algorithms are correct and to establish their time complexity (worst-case, average-case, best-case). Without proofs of correctness, there's no guarantee a program does what it's supposed to do.

Cryptography and security

Modern encryption relies on proofs about the computational hardness of certain problems, like factoring large numbers. Proofs verify the security of encryption schemes, digital signatures, and authentication protocols. If the underlying proof breaks, the security breaks with it.

Scientific theories

Mathematical proofs provide rigorous foundations for physical laws and models. They verify that theoretical predictions are internally consistent and help develop models for complex systems. In fields like theoretical physics, where direct experimentation may be impossible, mathematical proof is sometimes the only way to test ideas.

Common proof pitfalls

Knowing these traps helps you avoid them in your own work and spot them when reviewing others'.

Circular reasoning

This happens when your proof secretly assumes the thing it's trying to prove. It can be subtle: the conclusion might be buried in a definition you're using or hidden in an earlier step. To avoid it, trace each step back to its justification and make sure nothing depends on the conclusion.

Logical fallacies

Two of the most common:

• Affirming the consequent: "If P then Q; Q is true; therefore P is true." This is invalid. (If it rains, the ground is wet. The ground is wet. Therefore it rained? Not necessarily.)
• Denying the antecedent: "If P then Q; P is false; therefore Q is false." Also invalid.

Watch for these, especially when working with conditional statements.

Incomplete proofs

A proof that doesn't address all necessary cases is incomplete, even if the cases it does cover are handled correctly. Edge cases and special situations (like $n = 0$, empty sets, or degenerate geometric configurations) are the usual culprits. Systematically list all cases before you start writing.

Misuse of definitions

Applying a definition incorrectly or outside its valid context leads to false conclusions. This often happens with subtle concepts where the precise wording of the definition matters. Before using any definition in a proof, make sure you understand its exact conditions and scope.

Proof in different math fields

Different branches of math favor different proof styles and techniques.

Proofs in algebra

Algebra proofs work with abstract structures like groups, rings, and fields. You'll derive properties from axioms and use tools like homomorphisms and isomorphisms to relate structures. Induction and contradiction are common techniques here.

Proofs in geometry

Geometry proofs rely on visual reasoning and spatial relationships. Synthetic proofs work from axioms and postulates directly, while analytic proofs use coordinate geometry and algebraic methods. Construction techniques and transformations (rotations, reflections) are frequently employed.

Proofs in analysis

Analysis is where you'll encounter epsilon-delta proofs, the formal framework for limits and continuity. These proofs are notoriously precise: you must show that for every $\epsilon > 0$, there exists a $\delta > 0$ such that a certain condition holds. Contradiction and contrapositive arguments are also common in analysis.

Proofs in number theory

Number theory proofs focus on properties of integers and primes. Key tools include modular arithmetic, congruences, and proof by induction. Proof by infinite descent (a variant of strong induction that works downward) is a technique particularly associated with number theory, famously used by Fermat.