Examples of Basic Proofs

Proving "If A, then B" directly

Proof:
Suppose A.
Then … (( insert sequence of logical arguments here; probably will involve the definitions of the objects involved ))
Therefore, B.   ∗

Example:
Prove that the sum of two odd integers is even.

Rewrite as an "if... then" statement and introduce variables:
Prove that if n and m are odd integers, then n + m is even.

Proof:
Suppose n and m are odd integers.
By the definition of "odd", this means that there are some integers j and k such that n = 2j + 1 and m = 2k + 1.
This means that n + m = (2j + 1) + (2k + 1) = 2j + 2k + 2 = 2(j + k + 1).
Therefore, by the definition of "even" (and the fact that j + k + 1 is an integer), we know that n + m is even.   ∗

Proving "If A, then B" by contrapositive

Proof:
To prove that "If A, then B," we will prove the equivalent statement "If (Not B), then (Not A)."
Suppose Not B.
Then … (( insert sequence of logical arguments here; probably will involve the definitions of the objects involved ))
Therefore, Not A.   ∗

Example:
Prove that an integer that is not divisible by 2 cannot be divisible by 4.

Rewrite as an "if... then" statement and introduce variables:
For any integer n, show that if n is not divisible by 2, then n is not divisible by 4.

Proof:
Suppose n is an integer.
To prove that "if n is not divisible by 2, then n is not divisible by 4," we will prove the equivalent statement "if n is divisible by 4, then n is divisible by 2."
Suppose n is divisible by 4.
By the definition of "divisible by 4", this means that there is some integer k so that n = 4k.
This means that n = 4k = 2(2k).
Therefore, by the definition of "divisible by 2" (and the fact that 2k is an integer), we know that n is divisible by 2.   ∗

Proving "If A, then B" by contradiction

Proof:
Suppose A.
Seeking a contradiction, suppose Not B.
Then … (( make logical conclusions until you come to two statements that contradict each other, such as "X is true" and X is false" ))
But this is a contradiction because … (( explicitly mention the contradictory statements ))
Therefore our initial assumption that "Not B" cannot possibly be true (i.e. "Not B" must be false).
Thus B must be true.   ∗

Example:
Prove that the sum of two consecutive integers cannot be even.

Rewrite as an "if... then" statement and introduce variables:
Prove that if n and n+1 are consecutive integers, then n and n+1 cannot both be even.

Proof:
Suppose n and n+1 are consecutive integers.
Seeking a contradiction, suppose that n and n+1 are both even.
Since n+1 is even, by the definition of "even" we know that there is some integer k such that n+1 = 2k.
Solving this equation for n and doing a little bit of algebra we get n = 2k - 1 = 2k - 2 + 1 = 2(k-1) + 1.
By the definition of "odd" (and the fact that k-1 is an integer, this means that n must be odd.
This contradicts our previous statment that n was even.
Therefore our initial assumption that "n and n+1 are both even" must have been false.
Thus n and n+1 cannot both be even.   ∗

Disproving an implication "If A, then B" with a counterexample

Counterexample:
______ is a counterexample
because … (( state how A is true in your example ))
but … (( state how B is false in your example )).   ∗

Example:
Prove that it is false that every rational number is an integer.

Rewrite as an "if... then" statement and introduce variables:
Prove that the following statement is false: "If x is a rational number, then x is an integer."

Counterexample:
x = 2/3 is a counterexample because 2/3 is a rational number but 2/3 is not an integer.   ∗