───✱*.。:。✱*.:。✧*.。✰*.:。✧*.。:。*.。✱ ───

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

───✱*.。:。✱*.:。✧*.。✰*.:。✧*.。:。*.。✱ ───