Mathematical proving.

Mathematical proving.

1. Direct method

   • Conditional statement 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
         • Basis step
         • 2) given any integer k>1, prove Sk-->Sk+1 is true.
           • Inductive step
           • It follows by mathematical induction that every Sn is 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 is even, then n is even
           • assume n^2 is even, n is odd
             • since n is odd, n = 2k+1
               • then n^2 = (2k+1)^2
                 • = 4k^2 + 4k +1
                   • = 2(2k^2 + 2k) + 1
                     • n^2 = 2m + 1, m = 2k^2 + 2k
                       • Since n^2 is odd, this contradicts with the above statement since n^2 must be even
                         • therefore, n must be even
       • outline :
         • proposition : p ---> q
           • assume p is true, q is false ( p ---> ~q )
             • input logic, definitions or mathematical facts
               • come across a contradiction
                 • then p --> q must be true
     • non conditional statement
       • outline :
         • proposition : p
           • assume ~ p is true
             • input logic, definitions or mathematical facts
               • come across a contradiction
                 • then p must be true
       • example :
         • for all integers x and y, x^2 is not equal to 4y + 2
           • so x^2 = 4y + 2
             • then x^2 = 2(2y + 1)
               • x^2 is even, x must be even as well
                 • x = 2k
                   • x^2 = (2k)^2 = 4k^2
                     • then 4k^2 = 2(2y + 1)
                       • 2k^2 = 2y + 1
                         • 2k^2 is even but 2y + 1 is odd. They cannot be equal to each other.
                           • therefore, x^2 must be not equal to 4y + 2

Bilder und Dateien der Mindmap