← Logic

Logic

Proof Techniques

Lesson

Four standard ways to prove a mathematical statement.

1. Direct proof

To prove p→qp \to q: assume pp, then show qq follows step-by-step.

2. Proof by contradiction

Assume the opposite of what you want to prove. Derive a contradiction. Conclude the original.

Classic example: proving 2\sqrt{2} is irrational.

3. Proof by contrapositive

To prove p→qp \to q, prove ¬q→¬p\neg q \to \neg p instead. Equivalent statement, sometimes much easier.

4. Mathematical induction

For statements about all natural numbers. Prove the base case (n=1n = 1), then show that if it holds for n=kn = k it holds for n=k+1n = k + 1.

How to type your answer

1 direct, 2 contradiction, 3 contrapositive, 4 induction.

Practice

Work through these. Stuck? Click Get a hint.

Warm-Up

Quick problems to get going.

Problem 1

“Assume p is true, show q follows.”\text{``Assume } p \text{ is true, show } q \text{ follows.''}

Problem 2

“Assume p AND NOT q, derive a contradiction.”\text{``Assume } p \text{ AND NOT } q, \text{ derive a contradiction.''}

Problem 3

“Show ¬q→¬p instead of p→q.′′\text{``Show } \neg q \to \neg p \text{ instead of } p \to q.''

Problem 4

“Prove for n=1, then n=k  ⟹  n=k+1.′′\text{``Prove for } n=1, \text{ then } n=k \implies n=k+1.''

Practice

Standard problems matching the lesson.

Problem 5

To prove p→q, assume p and show q.\text{To prove } p \to q, \text{ assume } p \text{ and show } q.

Problem 6

To prove “no rational equals 2”, assume one does, derive contradiction.\text{To prove ``no rational equals } \sqrt{2}\text{'', assume one does, derive contradiction.}

Problem 7

To prove “if n2 even then n even”, prove “if n odd then n2 odd”.\text{To prove ``if } n^2 \text{ even then } n \text{ even'', prove ``if } n \text{ odd then } n^2 \text{ odd''.}

Problem 8

Prove 1+2+⋯+n=n(n+1)2 for all n≥1.\text{Prove } 1+2+\dots+n = \tfrac{n(n+1)}{2} \text{ for all } n \geq 1.

Problem 9

Proof of “all primes > 2 are odd” by direct argument.\text{Proof of ``all primes > 2 are odd'' by direct argument.}

Problem 10

The classic proof that 2 is irrational\text{The classic proof that } \sqrt{2} \text{ is irrational}

Problem 11

Assume conclusion’s negation; show hypothesis fails.\text{Assume conclusion's negation; show hypothesis fails.}

Problem 12

Best for proving statements about all natural numbers\text{Best for proving statements about all natural numbers}

Problem 13

“Assume the opposite, derive an impossibility.”\text{``Assume the opposite, derive an impossibility.''}

Problem 14

Walk forward from hypothesis to conclusion\text{Walk forward from hypothesis to conclusion}

Problem 15

Show base case and inductive step both hold\text{Show base case and inductive step both hold}

Problem 16

Negate the conclusion, show the hypothesis fails\text{Negate the conclusion, show the hypothesis fails}

Problem 17

A geometric proof showing a property step by step\text{A geometric proof showing a property step by step}

Problem 18

“Suppose this were true... that would force a contradiction.”\text{``Suppose this were true... that would force a contradiction.''}

Challenge

Harder problems — edge cases, trickier numbers, multiple steps.

Problem 19

Constructive existence proof\text{Constructive existence proof}

Problem 20

Prove P(n) for all n∈N\text{Prove } P(n) \text{ for all } n \in \mathbb{N}

Problem 21

“Suppose not. Then... but this is false.”\text{``Suppose not. Then... but this is false.''}

Problem 22

Equivalent to direct proof, uses ¬q→¬p\text{Equivalent to direct proof, uses } \neg q \to \neg p

Problem 23

Prove a divisibility property holds for all natural n\text{Prove a divisibility property holds for all natural } n

Problem 24

Prove inequality by computing step-by-step from given\text{Prove inequality by computing step-by-step from given}

Problem 25

Show no solution exists by assuming one does\text{Show no solution exists by assuming one does}

Ask the tutor

Stuck on a concept? Want another example? Ask anything about this topic.

Type your own question below, or tap one of the suggestions. The tutor can re-explain the lesson, work through a specific problem with you, generate fresh practice tuned to where you are, or check your reasoning.

Quiz

Test yourself on this topic →

10 questions, no hints. About 5 minutes.