Methods of Proof

By Eric Yu

What is a Proof?

A proof is a logical argument for the truth of a statement or theorem.

Example: If f is differentiable on the interval [a,b] and f(a)=f(b), then there exists some c in the open interval (a,b) such that f’(c)=0. (Rolle’s Theorem)

​

Converse, Inverse, Contrapositive.

Statement: “A implies B”,

Converse: “B implies A”,

Inverse: “not A implies not B”,

Contrapositive: “not B implies not A”.

​

Statement ⟺ Contrapositive

Converse ⟺ Inverse

T

F

T

T

A

not A

B

not B

Truth table for statement and contrapositive:

Proof by Contradiction

If we want to prove some statement A, it’s sufficient to show that (not A) implies something false.

Example:

Proof by Induction

If we want to prove some statement is true for all natural numbers n, we can first prove it’s true for n=1 (base case), then prove that the statement holding for n implies it holds for n+1 (inductive case).

Example: Prove that 11ⁿ - 6 is divisible by 5 for all natural numbers n.

Base case: 11¹ - 6 = 5, which is divisible by 5.

Inductive case: assuming 11ⁿ - 6 is divisible by 5, we see that

11ⁿ⁺¹ - 6 = 11(11ⁿ - 6) + 60, which is divisible by 5.