૭( ᵕ•̀ᵕ•́૭)

Methods of Proof

3 min read

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

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 2𝑘+1,𝑘∈ℤ
    • Since 3=2(1)+1, 3 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 2𝑘,𝑘∈ℤ
    • Let 𝑥=2𝑚 and 𝑦=2𝑛, where 𝑛∈ℤ
    • 𝑥+𝑦=2𝑚+2𝑛=2(𝑚+𝑛)≡2𝑘
    • ∴2(𝑚+𝑛) is even. □

Proof by Contrapositive

  • Instead of proving 𝑝→𝑞, we prove ¬𝑞→¬𝑝
  • Example → prove that if 𝑛2 is odd, then 𝑛 is odd.
    • Contrapositive → if 𝑛 is even, then 𝑛2 is even.
    • Let 𝑛=2𝑘 where 𝑘 is an integer
    • Then 𝑛2=(2𝑘)2=4𝑘2, 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 𝑝1,𝑝2,𝑝3,…,𝑝𝑛
    • Define a new number 𝑃=𝑝1𝑝2𝑝3…𝑝𝑛+1
    • ∴ 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 367>366
    • ∴ 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 𝑛=1)
    • Inductive hypothesis → assume statement is true for some arbitrary 𝑘, 𝑛=𝑘
    • Inductive step → prove that if statement holds for 𝑛=𝑘, then it also holds for 𝑛=𝑘+1
  • Example → the sum of the first 𝑛 natural numbers is 1+2+3+…+4=𝑛(𝑛+1)2
    • Base case (𝑛=1) → 1=1(1+1)2=1(2)2=22=1
    • Inductive hypothesis → 1+2+3+…+𝑘=𝑘(𝑘+1)2
    • Inductive step → 1+2+3+…+𝑘+(𝑘+1)=𝑘(𝑘+1)2+(𝑘+1)
      • Factor 𝑘+1 out → 𝑘(𝑘+1)+2(𝑘+1)2=(𝑘+1)(𝑘+2)2≡𝑘(𝑘+1)2□

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

Graph View