Mathematical proving

Mathematical proving

1. Direct method

   • If p, then q ( p ---> q )
   • Outline
     • If p, then q
       • 1) suppose p
         • 2) input logic, definition, mathematical facts
           • 4) expand
             • 5) factorise
               • 6) simplify
                 • 7) therefore q
   • Example :-
     • Is m is an even integer, then 7m+4 is an even integer
       • 1) suppose m is an even integer
         • 2) then m = 2n
           • 3) 7m+4 = 7(2n)+4
             • 4) = 14n+4
               • 5) = 2(7n+2)
                 • 6) = 2q, q=7n+2
                   • 7) therefore 7m+4 is an even integer

2. Mathematical induction

   • outline
     • the statements S1,S2,S3,S4,... are all true
       • 1) prove that S1 is true
         • The first step is called the basis step. Because S1 is usually a very simple statement, the basis step is often quite easy to do.
         • 2) given any integer k>1, prove that the statement Sk-->Sk+1 is true. It follows by mathematical induction that every Sn is true
           • The second step is called the inductive step. In the inductive step direct proof is most often used to prove Sk-->Sk+1 , so this step is usually carried out by assuming Sk is true and showing this forces Sk+1 to be true.
   • example
     • prove that 1^3+2^3+3^3+...+n^3=n^2(n+1)^2/4 for all positive integers n

3. Indirect method

   • Contrapositive
     • an alternative to direct proof
     • sometimes much easier than direct proof
     • p -> q = ~q -> ~p
     • outline
       • 1) if p then q
         • 2) suppose ~q
           • 3) input logic, definition, mathematical facts
             • 4) therefore ~p
     • example :
   • Contradiction
     • Not limited to conditional statement
     • conditional statement
       • example :
         • if (n^2)
       • outline :
         • proposition : p ---> q
           • assume p is true, q is false ( p ---> ~q )
             • come across a contradiction
               • then p --> q must be true
     • non conditional statement
       • outline :
         • proposition : p
           • assume ~ p is true
             • come across a contradiction
               • then p must be true
       • example :

Images and files in the map