design-proof-strategy

name	design-proof-strategy
description	Use when selecting an approach for constructing a mathematical proof or verifying a conjecture
source	George Polya "How to Solve It" (1945), Daniel Solow "How to Read and Do Proofs" (2013), Paul Halmos "How to Write Mathematics" (1970)
tags	["mathematics","proof","logic","induction","contradiction","direct-proof","problem-solving"]
verified	true

Design Proof Strategy

Select the appropriate proof technique for a mathematical claim and build the proof structure before writing it out.

Why This Is Best Practice

Adopted by: Polya's heuristics are foundational to mathematics education worldwide; used in every major undergraduate real analysis and discrete mathematics course Impact: Polya's "How to Solve It" has sold over 1 million copies and is cited as the single most influential book in mathematics pedagogy; its heuristics demonstrably reduce the time to find valid proofs in educational settings

Why best: Choosing the wrong proof strategy wastes significant time. A direct proof that cannot be completed is often a signal that contradiction or contrapositive would work. Understanding which technique fits which claim structure prevents the common failure of pushing one approach until the proof collapses. Polya's heuristics — draw a picture, work backward, find an analogous problem — consistently surface the right strategy faster than random exploration.

Steps

1. Understand the claim — Rewrite the statement formally: identify what is given (hypotheses) and what must be shown (conclusion). A proof proves P → Q; be clear on what P and Q are.
2. Consider direct proof first — If Q follows naturally from P by algebraic manipulation, definition application, or known theorems, attempt direct proof. Most computational proofs are direct.
3. Consider contrapositive if direct fails — Proof by contrapositive proves ¬Q → ¬P instead of P → Q (logically equivalent). Useful when the negation of Q provides strong constraints that make the proof tractable.
4. Consider proof by contradiction — Assume the claim is false (P ∧ ¬Q) and derive a contradiction. Useful for claims about uniqueness ("there is only one..."), impossibility ("there is no..."), and irrational/transcendental numbers.
5. Consider mathematical induction for universal claims over integers — For claims of the form "for all n ≥ n₀, P(n)": prove base case P(n₀), then prove P(n) → P(n+1). Strong induction (assuming P for all k < n) is available when the inductive step requires more than just P(n-1).
6. Consider construction for existence proofs — "There exists x such that P(x)" is often best proved by constructing the x explicitly. Alternatively, use probabilistic or pigeonhole arguments for non-constructive existence.
7. Identify and apply known lemmas — Before building from scratch, search for known theorems that imply the result. Recognize structural patterns (divisibility, group theory, topology) and apply the appropriate lemma.
8. Write a proof outline before the proof — State the strategy in one sentence. Write the major logical steps as a numbered list. Then fill in the details. A proof without an outline often wanders and introduces unjustified steps.

Rules

• Never begin writing a proof before identifying the strategy — prose mathematics written without a plan produces circular or incomplete arguments.
• A failed direct proof is information — what step did it fail at? That failure reveals why an indirect approach is needed.
• Every "it is clear that" or "obviously" in a proof is a warning flag — write out what is actually clear to verify no implicit assumption is being smuggled in.
• For induction, state the inductive hypothesis explicitly before using it — "assume P(n) is true for some n ≥ n₀" must appear verbatim.

Examples

Claim: √2 is irrational. Strategy selection: Irrationality is an impossibility claim ("there exist no integers p, q such that √2 = p/q in lowest terms") → proof by contradiction is the natural fit. Assume √2 = p/q in lowest terms → 2q² = p² → p² is even → p is even → p = 2k → 2q² = 4k² → q² is even → q is even. But p and q were assumed coprime (contradiction). QED.

Common Mistakes

• Attempting direct proof on every claim — some claims are not directly provable and will resist indefinitely; recognizing when to switch strategies is a core skill.
• Writing the inductive step without stating the inductive hypothesis — assumes what must be proved; a logical error that invalidates the proof.
• Circular reasoning in contradiction proofs — deriving the contradiction using the original claim (not its negation) proves nothing.
• Confusing "proof by example" with a universal proof — a single example demonstrates a claim for one case; it does not prove the universal.

When NOT to Use

• When the goal is numerical computation or approximation rather than deductive proof — selecting a proof strategy is irrelevant if the task requires a calculated result rather than a logical derivation.
• When the claim is an open conjecture at the research frontier where no known technique is sufficient — applying standard proof strategies to unsolved problems wastes time better spent on exploratory heuristics, special cases, and literature review.
• When the claim's truth value is first being established empirically via counterexample search — verifying a conjecture is false requires producing one counterexample, not designing a proof strategy for it.