Mathematical Proof Strategy

Mathematical Proof Strategy

1. DIRECT PROOF

   • OUTLINE
     • PROPOSITION IF P THEN Q
       • PROOF. SUPPOSE P . . .
         • THEREFORE Q
   • EXAMPLE
     • EXAMPLE
       • If a is an odd integer, then a^2 + 3a + 5 is odd
         • the formula (1^2) is 
         • Suppose a is an odd integer
           • Then a = 2b + 1 ,
             • Then, a^2 + 3a + 5
               • = (2b + 1)^2 + 3(2b+1) + 5
                 • = 4b^2 + 10b + 8 + 1
                   • 2( 2b^2 + 5b + 4 ) + 1
                     • 2c + 1 , c = 2b^2 + 5b + 4
                       • Therefore a^2 + 3a + 5 is odd.
   • METHODS
     • IF P, THEN Q
       • ASSUME THAT P IS TRUE
         • USE P TO SHOW THAT Q MUST BE TRUE

2. INDIRECT PROOF

   • CONTRADICTION
     • OUTLINE
       • PROPOSITION P
         • PROOF. SUPPOSE ~ P . . .
           • THEREFORE Q ^ ~ Q
     • METHODS
       • IF P, THEN Q
         • TO PROVE THE GIVEN PROPOSITION IS TRUE
           • ASSUME P IS FALSE
             • USE LOGIC TO EVENTUALLY GET a CONTRADICTION Q AND NOT Q
               • CONCLUDE P SINCE THE SUPPOSITION THAT P IS FALSE LEADS TO CONTRADICTION
     • EXAMPLE
       • IF N IS AN INTEGER AND 3N + 2 IS EVEN , THEN N IS EVEN
         • ASSUME 3N + 2 IS EVEN AND N IS ODD
           • N = 2A + 1
             • FOR SOME INTEGER A BY THE DEFINITION OF ODD INTEGER
             • 3N + 2 = 3(2A + 1) + 2
               • = 6A + 3 + 2
                 • = 6A + 4 + 1
                   • = 2 (3A + 2) + 1
                     • = 2B + 1
                       • B = 3A + 2
                       • FROM LAST LINE, 3N + 2 IS ODD BUT 3N + 2 MUST BE EVEN
                         • CONTRADICTION
                         • THE GIVEN PROPOSITION IS TRUE
   • CONTRAPOSITIVE
     • OUTLINE
       • PROPOSITION IF P, THEN Q
         • PROOF. SUPPOSE ~ Q . . .
           • THEREFORE ~ P
     • EXAMPLE
       • FOR ALL INTEGERS n, IF n^2 IS ODD, THEN n IS ODD.
         • FOR ALL INTEGERS n, IF n IS EVEN, THEN n^2 IS EVEN
           • CONTRAPOSITIVE STATEMENT
           • SUPPOSE n = 2m
             • THEN, n^2 = 4m^2
               • = 2 ( 2m^2)
                 • 2p , p = 2m^2
                   • THEREFORE n^2 IS EVEN
         • PROPOSITION
     • METHODS
       • IF P ,THEN Q
         • NEGATE P AND Q
           • REVERSE THE DIRECTION OF INVERSE
             • SUPPOSE Q IS NOT TRUE
               • USE LOGIC AND DEFINITION TO TRANSFORM ~Q TO ~P

3. MATHEMATICAL INDUCTION

   • EXAMPLE
     • PROVE THAT 1^2 + 2^2 + 3^2 + ....+ n^2 = n( n + 1) ( 2n + 1) / 6
       • BASIS STEP
         • LEFT SIDE : 1^2 = 1
           • RIGHT SIDE : 1(1+1) (2(1)+1) / 6 = 1
             • THEREFORE S(1) IS TRUE
           • SHOW THAT S(1) IS TRUE
       • INDUCTION STEP
         • Sk : 1^2 + 2^2 + 3^2 + ......+ k^2 = k( k + 1) ( 2k + 1) / 6
           • Sk + 1 : 1^2 + 2^2 + 3^2 +......+ ( k+ 1)^2 = k + 1 (k + 2) ( 2(k + 1) + 1) /6
         • 1^2 + 2^2 + 3^2 +....+ k^2 + (k + 1) ^ 2 = k ( k + 1) ( 2k + 1) / 6 + (k + 1 ) ^2
           • 2. SHOW THAT Sk + 1 iS TRUE BY USING DIRECT PROOF
           • k + 1 ( 2k^2 + 7k + 6) / 6
             • 3. SET COMMON DENOMINATOR AND FACTORISE K + 1 ON THE RIGHT SIDE
             • k + 1 ( 2k + 3) ( k + 2) / 6
               • 4. FACTORISE 2k^2 + 7k +6
               • 1^2 + 2^2 + 3^2 + ....+ ( k + 1) ^ 2 = k +1 ( 2k + 3) ( k + 2) / 6
                 • THEREFORE, Sk --> Sk + 1
         • 1. ASSUME THAT Sk IS TRUE
           • 1^2 + 2^2 + 3^2 +...+k^2 = k( k+1 ) (2k +1) / 6
   • METHODS
     • a) BASIC STEP
       • 1. PROVE THAT FIRST STATEMENT S1 IS TRUE
     • b) INDUCTIVE STEP
       • 1. USE DIRECT PROOF TO PROVE Sk --> Sk + 1 IS TRUE
         • 2. ASSUME Sk IS TRUE AND SHOWING THIS FORCES Sk + 1 IS TRUE

Imágenes y archivos del mapa