Strategy of Mathematical Proof :)

Strategy of Mathematical Proof :)

1. Direct Proof

   • • The most straightforward approach
   • Description of each step
     • Description of each step: 1. Identify p and q of the question. 2. Relate p and q using connective symbol 3. Solve the question using Direct proof outline
     • 1. Identify p and q of the question.
       • 2. Relate p and q using connective symbol
         • 3. Solve the question using Direct proof outline
   • remarkably simple
   • • Simple way to prove theorems or propositions that have the form of conditional statements.
   • • To understand direct proof works, suppose we have some proposition in the form ;
     • o Proposition If P, then Q.
       • o This proposition is a conditional statement of form P=>Q. Our goal is to show that this conditional statement is true. To see how to proceed look at the truth table.
         • o We must show that the condition of P being true forces Q to be true also, means the second line of the table cannot happen.
   • outline

2. Contradiction

   • Assume that the statement we want to prove is false,
     • then show that this assumption leads to nonsense
       • We are then led to conclude that we were wrong to assume the statement was false
         • so the statement must be true.
     • BASIC IDEA
   • The rules:
     • p --> q is logically equivalent to ~p --> q
       • ~(p --> q) is logically equivalent to p^ ~q
   • Prove that if 7x + 9 is even, then x is odd by using the method of proof by contradiction
     • Example
     • Solution:  Step 1: Write the statement in symbol  Step 2: Use Proof by Contradiction outline to prove the statement
       • If 7x + 9 is even, then x is odd
         • 1. p : 7x + 9 is even
         • q : x is odd
         • ~q : x is even
       • Suppose ~(p→q) = p^~q ( By using the rules )
         • = If 7x + 9 is even, then x is even
           • • This contradict from what we assume which was 7x + 9 is even. So, If 7x + 9 is even, then x is a true statement.
               • ∴Contradiction
   • - It’s best to use proof by contradiction only when the direct and contrapositive approaches do not seem to work
     • - A proof by contradiction can often have hidden in it a simpler contrapositive proof, and if this is the case it’s better to go with the simpler approach.

3. Contrapositive Proof

   • Imagine that you need to prove a proposition of the following form. Proposition If P, then Q.
     • Our goal is to show that this conditional statement is true
       • We knew that P -> Q is logically equivalent to ~Q-> ~P based on the truth table.
         • Hence, we know that The expression to ~Q -> ~P is called the contrapositive form of P->Q.
   • Setup for contrapositive proof
     • 1) first line of the proof is the sentence “Suppose Q is not true.”
     • 2) The last line is the sentence “Therefore P is not true.”
     • 3) Between the first and last line we use logic and definitions to transform the statement »Q to the statement » P

4. Mathematical Induction

   • powerful proof technique
   • used to proof a conjecture
   • two steps' technique
   • Fibonacci sequence
     • Leonardo Pisano a.k.a. Fibonacci describe this sequence. The first two numbers are 1 and 1, and thereafter any entry is the sum of the previous two entries.
       • Proposition: The Fibonacci sequence obeys F2n+1-Fn+1Fn-F2n=(-1)n. For all positive integer n element of Natural numbers, Ɐn Ꞓ N
         • 1. Basis step: P(1): F21+1-F1+1F1-F21=(-1)1 1-1(1)-1=-1  proven
     • appears with surprising frequency filled with mysterious patterns and hidden structures

Images and files in the map