Methods of Proof

───✱*.｡:｡✱*.:｡✧*.｡✰*.:｡✧*.｡:｡*.｡✱ ───

Why?

• Verification of truth
• Remove ambiguity
• Build more knowledge (such as new theorems)
• Problem solving

Modus Ponens (Law of Detachment)

• Fundamental rule of logic
• If is true and is true, then must be true
  • If a number is even then it is divisible by 2 → 4 is even so therefore it must be divisible by 2

QED (Quod Erat Demonstrandum)

• “Which was to be demonstrated”
• Written at the end of a proof to conclude
• Also indicated with or

Proof by Definition

• Definition-based proofs establish truth by referring to a mathematical definition
• Example → prove that 3 is an odd number
  • Odd definition → a number of the form
  • Since , is odd.

Direct Proof

• Starts from known facts, then uses logic to arrive at a conclusion
• Example → prove that the sum of two even numbers is an even number
  • Even definition → a number of the form
  • Let and , where
  • is even.

Proof by Contrapositive

• Instead of proving , we prove
• Example → prove that if is odd, then is odd.
  • Contrapositive → if is even, then is even.
  • Let where is an integer
  • Then , which is even
  • Since contrapositive is true, the original statement is true.

Proof by Contradiction

• We assume the opposite of what we want to prove and derive a contradiction
• Example → prove that there are infinitely many prime numbers (Euclid’s theorem)
  • Assumption (negation) → there are a finite number of primes
  • Let those primes be
  • Define a new number
  • P must either by prime itself or be divisible by a “new prime”
  • This contradicts our assumption that we had listed all primes
  • There are infinitely many primes.

Pigeonhole Principle

• If more objects are placed into fewer containers, then at least one container must contain multiple objects.
• Example → prove that in a group of 367 people, then at least 2 share a birthday.
  • There are only 366 possible birthdays and
  • By the pigeonhole principle, at least 2 people share a birthday.

Proof by Counterexample

• To disprove a statement, provide one counterexample.
• Example → disprove that all prime numbers are odd
  • Counterexample → 2 is a prime number

Proof by Induction

• Induction → used to prove statements that apply to all
  • Base case → prove statement for the smallest (typically )
  • Inductive hypothesis → assume statement is true for some arbitrary ,
  • Inductive step → prove that if statement holds for , then it also holds for
• Example → the sum of the first natural numbers is
  • Base case () →
  • Inductive hypothesis →
  • Inductive step →
    • Factor out →

───✱*.｡:｡✱*.:｡✧*.｡✰*.:｡✧*.｡:｡*.｡✱ ───