Proof Techniques

Lesson 4 · OKSTEM College · AS Computer Science

Types of Mathematical Proof

A proof is a logical argument establishing the truth of a statement. Four core techniques appear constantly in CS theory.

Method	Strategy	When to use
Direct proof	Assume P, derive Q	Most straightforward "if P then Q"
Proof by contrapositive	Prove ¬Q ⇒ ¬P	When negating is easier than proving directly
Proof by contradiction	Assume ¬P, derive a contradiction	Showing something cannot exist
Mathematical induction	Base case + inductive step	Statements about natural numbers

Direct Proof

Claim: If n is even, then n² is even.

Assume: n is even. So n = 2k for some integer k.

Compute: n² = (2k)² = 4k² = 2(2k²).

Conclude: n² = 2m where m = 2k² is an integer. Therefore n² is even. □

Proof by Contradiction

Claim: √2 is irrational.

Assume for contradiction: √2 is rational, so √2 = p/q in lowest terms (gcd(p,q)=1).

Square both sides: 2 = p²/q², so p² = 2q². Thus p² is even, so p is even. Write p = 2m.

Substitute: (2m)² = 2q² ⇒ 4m² = 2q² ⇒ q² = 2m². So q is also even.

Contradiction: Both p and q are even, contradicting gcd(p,q)=1. □

Mathematical Induction

Claim: 1 + 2 + 3 + … + n = n(n+1)/2 for all n ≥ 1.

Base case (n=1): LHS = 1. RHS = 1·2/2 = 1. ✓

Inductive hypothesis: Assume the formula holds for some k ≥ 1: 1+…+k = k(k+1)/2.

Inductive step: Show it holds for k+1: 1+…+k+(k+1) = k(k+1)/2 + (k+1) = (k+1)(k/2+1) = (k+1)(k+2)/2. ✓

Conclusion: By induction, the formula holds for all n ≥ 1. □

Practice Problems

1. Prove by direct proof: if n is odd, n² is odd.

Assume n is odd. Then n = 2k+1 for some integer k.
n² = (2k+1)² = 4k² + 4k + 1 = 2(2k²+2k) + 1.
This has the form 2m+1, so n² is odd. □

2. Use induction to prove: ∑_i=1ⁿ (2i−1) = n².

Base (n=1): LHS=1, RHS=1²=1. ✓
Assume true for k: ∑(2i−1) = k².
For k+1: k² + (2(k+1)−1) = k²+2k+1 = (k+1)². ✓
By induction, holds for all n ≥ 1. □

Knowledge Check

A direct proof of 'P implies Q' starts by

That's the setup for proof by contrapositive.

Correct — direct: assume the hypothesis, work toward the conclusion.

That's not a standard proof strategy.

Counterexamples disprove, not prove.

Recap: direct proof = assume P, chain of logical steps, conclude Q. Cleanest method when the path from P to Q is clear.

Proof by contradiction assumes

You want to prove it's true; you assume the opposite.

Correct — assume ¬P, show that leads to something impossible.

Base cases are for induction, not contradiction.

That's case analysis / proof by cases.

Recap: contradiction = assume the opposite, follow logical consequences, hit an impossibility (like p and q both even when gcd=1), conclude the original must be true.

The inductive step must show

That's the base case.

Correct — the inductive step uses the hypothesis at k to prove k+1.

Induction works for all n above the base, not just even n.

The base case alone proves only n=1; the inductive step handles the rest.

Recap: induction has two parts — base case (anchor) and inductive step (propagation). Both are required.

Proof by contrapositive proves 'P implies Q' by proving

That would prove the opposite direction.

Correct — contrapositive is logically equivalent to the original implication.

That's the converse — not logically equivalent.

That's the inverse — also not equivalent.

Recap: P ⇒ Q is equivalent to ¬Q ⇒ ¬P. Use contrapositive when it's easier to work backward from 'not Q'.

To disprove a universal statement ∀x P(x) you need

One counterexample is sufficient.

Correct — one example where P fails is enough to disprove a universal claim.

Contradiction is for proving things true; a counterexample is quicker here.

That would say P fails for everything — you only need one failure.

Recap: universal = must hold for every element. One counterexample destroys it. Existential = must hold for at least one — one example proves it.

← Previous Next →