Proofs

Lecture Notes: Methods of Proof
1. Direct Proof
Definition: In a direct proof, we start with known facts or premises and apply
logical steps to reach the statement we want to prove. This method is often
used for statements in the form ”If P , then Q.”
Structure:
• Assume P is true.
• Use logical steps to deduce Q directly.
Example 1: Prove that the sum of two even numbers is even.
Solution:
• Let the two even numbers be 2a and 2b for integers a and b.
• Their sum is 2a + 2b = 2(a + b), which is divisible by 2, hence even.
• Therefore, the sum of two even numbers is even.
Example 2: Prove that the square of any odd integer is odd.

Solution:
• Let n be an odd integer, so n = 2k + 1 for some integer k.
• Then n2 = (2k + 1)2 = 4k 2 + 4k + 1 = 2(2k 2 + 2k) + 1, which is odd.
• Therefore, the square of any odd integer is odd.

Exercises:
• Prove that the sum of two odd numbers is even.
• Prove that the product of two odd numbers is odd.

• Prove that the product of an even integer and any integer is even.
1
2. Proof by Contrapositive
Definition: Instead of proving ”If P , then Q,” we prove ”If ¬Q, then ¬P .”
This is logically equivalent and often simpler in cases where proving P ⇒ Q
directly is challenging.
Structure:
• Rewrite the statement in contrapositive form: ”If ¬Q, then ¬P .”

• Assume ¬Q and use logical steps to deduce ¬P .
Example 1: Prove that if n2 is even, then n is even.
Solution:
• Contrapositive statement: If n is odd, then n2 is odd.

• Assume n is odd, so n = 2k + 1 for an integer k.
• n2 = (2k + 1)2 = 4k 2 + 4k + 1, which is odd.
• Therefore, if n2 is even, n must be even.
Example 2: Prove that if n is not divisible by 3, then n2 is not divisible by

3.
Solution:
• We’ll prove the contrapositive: If n2 is divisible by 3, then n is divisible
by 3.
• Assume n2 is divisible by 3, meaning n2 = 3k for some integer k.
• If n were not divisible by 3, then n ≡ 1 or n ≡ 2 (mod 3).
• But in either case, n2 would not be divisible by 3, contradicting our as-
sumption.
• Therefore, if n2 is divisible by 3, n must be divisible by 3.
Exercises:
• Prove that if n3 is odd, then n is odd.
• Prove that if n is divisible by 3, then n2 is also divisible by 3.
3. Proof by Contradiction
Definition: To prove a statement P , assume that ¬P is true and show that
this leads to a contradiction. This contradiction implies that P must be true.
Structure:
• Assume ¬P (the opposite of what we want to prove).
2
• Show that this assumption leads to a logical contradiction, implying that
P must be true.
√
Example 1: Prove that 2 is irrational.
Solution:
√
• Assume the opposite: 2 is rational.
√
• Then 2 = ab , where a and b are integers with no common factors.
a2
• Squaring both sides, 2 = b2 ⇒ a2 = 2b2 .
• This implies a2 is even, so a must be even.

• Let a = 2k, then b must also be even, contradicting the assumption.
√
• Thus, 2 is irrational.
Example 2: Prove that there are infinitely many prime numbers.
Solution:
• Assume the opposite: there are finitely many primes, say p1 , p2 , . . . , pn .
• Consider N = p1 p2 · · · pn + 1.
• N is not divisible by any pi , so it must be prime or have a prime factor
not in the list, contradicting our assumption.
• Therefore, there are infinitely many primes.

Exercises:
• Prove that if n is a positive integer and n2 is divisible by 3, then n is also
divisible by 3.
4. Mathematical Induction
Definition: Mathematical induction is used to prove statements about integers,
typically involving a sequence or pattern. The proof consists of two steps: the
base case and the inductive step.
Structure:
• Base Case: Prove the statement is true for the initial integer (often n = 1
or n = 0).
• Inductive Step: Assume the statement is true for n = k (inductive

hypothesis) and prove it for n = k + 1.
n(n+1)
Example 1: Prove that the sum of the first n positive integers is 2 .
Solution:
3
• Base Case: For n = 1, the left side is 1, and the right side is 1×2
2 = 1, so
it holds.
k(k+1)
• Inductive Step: Assume it holds for n = k: 1 + 2 + · · · + k = 2 .
(k+1)(k+2)
• Show it holds for n = k + 1: 1 + 2 + · · · + k + (k + 1) = 2 .
Example 2: Prove that 2n > n2 for n ≥ 5.

Solution:
• Base Case: For n = 5, 25 = 32 and 52 = 25, so 2n > n2 .
• Inductive Step: Assume 2k > k 2 . Show 2k+1 > (k + 1)2 .
Exercises:
• Prove that 1 + 3 + 5 + · · · + (2n − 1) = n2 .
Summary Table
Proof Method Key Idea

Direct Proof Assume P and deduce Q.
Contrapositive Proof Prove ¬Q ⇒ ¬P .
Proof by Contradiction Assume ¬P and derive a contradiction.
Mathematical Induction Prove for base case; assume true for k, prove for k + 1.

Proofs

Uploaded by

Copyright:

Available Formats

Proofs

Uploaded by

Document Information

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Proofs

Uploaded by

Copyright:

Available Formats

Lecture Notes: Methods of Proof

Example 2: Prove that the square of any odd integer is odd.

• Therefore, the square of any odd integer is odd.

• Prove that the product of two odd numbers is odd.

• Rewrite the statement in contrapositive form: ”If ¬Q, then ¬P .”

• Contrapositive statement: If n is odd, then n2 is odd.

Example 2: Prove that if n is not divisible by 3, then n2 is not divisible by

• Prove that if n is divisible by 3, then n2 is also divisible by 3.

• This implies a2 is even, so a must be even.

• Therefore, there are infinitely many primes.

• Inductive Step: Assume the statement is true for n = k (inductive

Example 2: Prove that 2n > n2 for n ≥ 5.

Proof Method Key Idea

You might also like