PROOFS HOMEWORK

  1. Use rules of inference to show that the hypotheses "If it does not rain or if it is not foggy, then the sailing race will be held and the lifesaving demonstration will go on.", "If the sailing race is held, then the trophy will be awarded.", and "The trophy was not awarded." imply the conclusion "It rained.".


    2. SOLUTION: (1) Let r be the proposition that "It rains."
    f be the proposition that "It is foggy."
    s be the proposition that "The sailing race will be held."
    l be the proposition that "The life saving demonstration will go on."
    t be the proposition that "The trophy will be awarded."
    (2) Given
    hypotheses:
      If it does not it does rain or if it is not it is foggy,   then   the sailing race will be held and the lifesaving demonstration will go on.  
    ( Ø r \/ Ø f ) ® ( s /\ l )
    If the sailing race is held, then the trophy will be awarded.
    s ® t
    The trophy was not was awarded.
    Ø t
    (3) Desired
    conclusion:
    It rained.
    r
    (4) Proof:
    STEP REASON
    (1) Ø t Hypothesis
    (2) s ® t Hypothesis
    (3) Ø s Modus tollens using (1) and (2)
    (4) ( Ø r \/ Ø f ) ® ( s /\ l ) Hypothesis
    (5) ( Ø ( s /\ l ) ) ® ( Ø ( Ø r \/ Ø f ) ) Contrapositive of (4)
    (6) ( Ø s \/ Ø l ) ® ( Ø ( Ø r ) /\ Ø ( Ø f ) ) De Morgan's Law
    (7) ( Ø s \/ Ø l ) ® ( r /\ f ) Double Negation
    (8) Ø s \/ Ø l Addition with (3)
    (9) r /\ f Modus ponens using (7) and (8)
    (10) r Simplication using (9)

    The proof is complete.

  2. For each of these arguments, explain which rules of inference are used for each step.


    3. Arguments: "Each of five roommates, Melissa, Aaron, Ralph, Vaneesha, and Keeshawn, has taken a course in discrete mathematics.
    Every student who has taken a course in discrete mathematics can take a course in algorithms.
    Therefore, all five roommates can take a course in algorithms next year.    "

    SOLUTION: (5) Let r ( x ) mean that x is a roommate.
    d ( x ) mean that x has taken a course in discrete mathematics.
    a ( x ) mean that x can take a course in algorithm.
    (6) Given
    hypotheses:
    Each of   five roommates,
    Melissa, Aaron, Ralph, Vaneesha, and Keeshawn,     		  has taken a course in discrete mathematics.  
    "x ( r ( x ) ® d ( x ) )
    Every student   who has taken a course in discrete mathematics can take a course in algorithms.  
    "x ( d ( x ) ® a ( x ) )
    (7) Desired
    conclusion:
    Therefore, all five   roommates can take a course in algorithms next year.  
    "x ( r ( x ) ® a ( x ) )
    (8) Proof:
    STEP REASON
    (1) " x ( r ( x ) ® d ( x ) ) Hypothesis
    (2) r ( y ) ® d ( y ) Universal Instantiation using (1)
    (3) "x ( d ( x ) ® a ( x ) ) Hypothesis
    (4) d ( y ) ® a ( y ) Universal Instantiation using (3)
    (5) r ( y ) ® a ( y ) Hypothetical Syllogism using (2) and (4)
    (6) "x ( r ( x ) ® a ( x ) ) Universal Generalization using (5)

    The proof is complete.

  3. Write the given argument in words and determine whether each argument is valid.


    4. Let p: 4 megabytes is better than no memory at all
    q: We will buy more memory.
    r: We will buy a new computer.

    Arguments: p ® r
    r ® q
    p
    \ q

    SOLUTION: (9) (1) p ® r Hypothesis If 4 megabytes of memory is better than no memory at all,
    then we will buy a new computer.
    (2) r ® q Hypothesis If we will buy a new computer,
    then we will buy more memory.
    (3) p ® q Hypothetical
    Syllogism         		If 4 megabytes of memory is better than no memory at all,
    then we will buy more memory.
    (4) p Hypothesis 4 megabytes of memory is better than no memory at all.
    (5) \ q Modus Ponens Therefore, we will buy more memory.

  4. Determine whether each argument is valid.


    5. Arguments: ( p ® q ) /\ ( r ® s )
    p \/ r
    \ q \/ s

    SOLUTION: (10) (1) ( p ® q ) /\ ( r ® s ) Hypothesis
    (2) p ® q º ¬ p \/ q LECS#1
    (3) r ® s º ¬ r \/ s LECS#1
    (4) ( ¬ p \/ q ) /\ ( ¬ r \/ s ) Conjunction from (1), (2), (3)
    (5) ( ¬ p \/ q ) Simplification
    (6) ( ¬ r \/ s ) Simplification
    (7) p \/ r Hypothesis
    (8) q \/ r Resolution from (5) & (7)
    (9) \ q \/ s Resolution from (6) & (8)

  5. Use resolution to derive the conclusion.


    6. Arguments: ¬ p \/ t
    ¬ q \/ s
    ¬ r \/ ( s /\ t )
    p \/ q \/ r \/ u
    \ s \/ t \/ u

    SOLUTION: (11) (1) ¬ p \/ t Hypothesis
    (2) ¬ q \/ s Hypothesis
    (3) ¬ r \/ ( s /\ t ) Hypothesis
    (4) ( ¬ r \/ s ) /\ ( ¬ r \/ t ) Distributive Law
    (5) ¬ r \/ s Simplification
    (6) ¬ r \/ t Simplification
    (7) p \/ q \/ r \/ u Hypothesis
    (8) t \/ q \/ r \/ u Resolution from (1) & (7)
    (9) s \/ t \/ r \/ u Resolution from (2) & (8)
    (10) s \/ t \/ u Resolution from (5) & (9) or (6) & (9)

  6. Determine whether or not the argument is correct and explain why.


    7. Arguments: a. A convertible car is fun to drive.
    Isaac's car is not a convertible.
    Therefore, Isaac's car is not fun to drive.
    b. Quincy likes all action movies.
    Quincy likes the movie "Eight Men Out".
    Therefore, "Eight Men Out" is an action movie.

    SOLUTION: a. (12) Let c ( x ) mean that x is a convertible.
    f ( x ) mean that x is fun to drive.
    (13) Given
    hypotheses:
      A convertible car is fun to drive.
    "x ( c ( x ) ® f ( x ) )
    Isaac's car is not a convertible.
    Ø ( c ( Isaac )
    (14) Desired
    conclusion:
    Therefore, Isaac's car is not fun to drive.
    Ø f ( Isaac ) )
    (15) Proof:
      STEP REASON
    (1) "x ( c ( x ) ® f ( x ) ) Hypothesis
    (2) c ( y ) ® f ( y ) Universal Instantiation
    (3) Ø c ( Isaac ) Hypothesis
    (4) Ø f ( Isaac ) Fallacy of Denying the Hypothesis
    b. (16) Let m ( x ) mean that Quincy likes movie x.
    a ( x ) mean that x is an action movie.
    (17) Given
    hypotheses:
    Quincy like all action movies.
    "x ( m ( x ) ® a ( x ) )
    Quincy likes the movie "Eight Men Out".
    m ( "Eight Men Out" )
    (18) Desired
    conclusion:
    Therefore, "Eight Men Out" is an action movie.
    a ( "Eight Men Out" )
    (19) Proof:
      STEP REASON
    (1) "x ( m ( x ) ® a ( x ) ) Hypothesis
    (2) m ( y ) ® a ( y ) Universal Instantiation
    (3) m ( "Eight Men Out" ) Hypothesis
    (4) a ( "Eight Men Out" ) Fallacy of Affirming the Conclusion

  7. Prove that if n is an integer and 3n + 2 is even, then n is even using


    1. proof by contraposition
    2. proof by contradiction

    SOLUTION:
    Problem: Prove that if n is an integer and 3n + 2 is even, then n is even.
    Proof:
    (20) a. by Contraposition:   If n is odd, then 3n + 2 is odd.
    Assume n is odd.
    Þ n = 2k + 1, for some integer k.
    Þ 3n + 2 = 3 ( 2k + 1) + 2.
    Þ 3n + 2 = 6k + 3 + 2.
    Þ 3n + 2 = 6k + 5.
    Þ 3n + 2 = 6k + 4 + 1.
    Þ 3n + 2 = 2 ( 3k + 2 ) + 1.
    Þ 3n + 2 = 2c + 1, for some integer c = 3k + 2.
    Þ \ 3n + 2 is odd.
    Þ the proof is complete.
    (21) b. by Contradiction:   Suppose that 3n + 2 is even and n is odd.
    Since 3n + 2 is even, then so is 3n.
    Þ If we add or subtract an odd number from an even number, then the answer is odd.
    Þ Since n is odd
    Þ 3n - n = 2n is odd, which is clearly not the case.
    Þ \ the supposition is not valid.
    Þ the proof is complete.

  8. Prove that if n is a positive integer, then n is even iff 7n + 4 is even.


    9. SOLUTION: Proof: (22) Prove ®: if n is even, then 7n + 4 is even.
    Since n is even.
    Þ n = 2k, for some integer k
    Þ 7n + 4 = 7 ( 2k ) + 4
    Þ 7n + 4 = 14k + 4
    Þ 7n + 4 = 2 ( 7k + 2)
    Þ 7n + 4 = 2c, for c = 7k + 2
    Þ 7n + 4 is even.
    Þ the proof is complete
    (23) Prove ¬: if 7n + 4 is even, then n is even.
    Prove by Contraposition, i.e. if n is odd, then 7n + 4 is odd.
    Suppose n is odd.
    Þ n = 2k + 1, for some integer k
    Þ 7n + 4 = 7 ( 2k + 1 ) + 4
    Þ 7n + 4 = 14k + 7 + 4
    Þ 7n + 4 = 14k + 11
    Þ 7n + 4 = 14k + 10 + 1
    Þ 7n + 4 = 2 ( 7k + 5 ) + 1
    Þ 7n + 4 = 2c + 1, for c = 7k + 5
    Þ 7n + 4 is odd.
    Þ the proof is complete

  9. Show that the propositions p1, p2, p3, p4 can be shown to be equivalent by showing that

    10. p1 « p4, p2 « p3, p1 « p3.

    SOLUTION: (24) Proof: Given p1 « p4 and p2 « p3 and p1 « p3.
    Þ Since p1 « p3 and p2 « p3, then p1 « p2.
    Þ Since p1 « p4 and p1 « p2, then p2 « p4.
    Þ Since p1 « p3 and p1 « p4, then p3 « p4
    Þ \ p1 « p2 « p3 « p4
    Þ the proof is complete

  10. Determine and prove the formula for
    11. 1
     1 • 2     		 + 1
     2 • 3     		 + 1
     3 • 4     		 + . . . + 1
     n ( n + 1 ) 

    SOLUTION: Proof by induction
    (25) BASIS
    STEP:
    P ( n = 1 ): 1
     1 • 2     		 = 1
     2 
    P ( n = 2 ): 1
     1 • 2     		 + 1
     2 • 3     		 = 1
     2     		 + 1
     6     		 = 3
     6     		 + 1
     6     		 = 4
     6     		 = 2
     3 
    P(n=3): 1
     1•2     		 + 1
     2•3     		 + 1
     3•4     		 = 1
     2     		 + 1
     6     		 + 1
     12     		 = 6
     12     		 + 2
     12     		 + 1
     12     		 = 9
     12     		 = 3
     4 

                      •
                      •
                      •
    P ( n ): 1
     1 • 2     		 + 1
     2 • 3     		 + 1
     3 • 4     		 + • • • + 1
     n ( n + 1 )     		 = n
     n + 1 
    (26) INDUCTIVE
    STEP:    		 Assume that P ( n ) is T.
    Show, by using P ( n ), that P ( n + 1 ) is T.
    Prove P ( n ) ® P ( n + 1 ) by showing the P ( n + 1 ) is T.
    P(n+1):
    1
     1 • 2     		 + 1
     2 • 3     		 + 1
     3 • 4     		 + • • • + 1
     n ( n + 1 )     		 + 1
     ( n + 1) ( n + 2 ) 
    = é
    ê
    ê
    ë    		 1
     1•2     		 + 1
     2•3     		 + 1
     3•4     		 + • • • + 1
     n ( n + 1 )     		 ù
    ú
    ú
    û    		 + 1
     ( n + 1 ) ( n + 2 ) 
    = é
    ê
    ê
    ë    		 n
     n + 1     		 ù
    ú
    ú
    û    		 + 1
     ( n + 1 ) ( n + 2 ) 
    = n ( n + 2 )
     ( n + 1 ) ( n + 2 )     		 + 1
     ( n + 1 ) ( n + 2 ) 
    = n2 + 2n
     ( n + 1 ) ( n + 2 )     		 + 1
     ( n + 1 ) ( n + 2 ) 
    = n2 + 2n + 1
     ( n + 1 ) ( n + 2 ) 
    = ( n + 1 )2
     ( n + 1 ) ( n + 2 ) 
    = n + 1
     n + 2 
    P ( n + 1 ) is T.
    Hence, P ( n ) ® P ( n + 1 ) is T for all positive integers n.
    \ P ( n ) is T.

  11. Using induction, verify the inequality.


    12. Inequality: [ 1 • 3 • 5 • ... • ( 2n – 1 ) ]
    [ 2 • 4 • 6 • ... • ( 2n ) ]     		 £  1
    ( n + 1 )½    		 , for n = 1, 2, ...

    SOLUTION: (27) BASIS
    STEP:
    P ( 1 ):  1 
    2    		 £ 1
    ( 1 + 1 )½
    P ( 1 ): 1
    2    		 £ 1
    2½
    \ P ( 1 ) is T.
    (28) INDUCTIVE
    STEP:
    Assume P(n): 1 • 3 • 5 • ... • ( 2n – 1 )
    2 • 4 • 6 • ... • ( 2n )     		£ 1
    ( n + 1 )½    		  is T.
    Show, by using P ( n ), that P ( n + 1 ) is T.
    Prove P ( n ) ® P ( n + 1 ) by showing
    P ( n + 1 ) : 1 • 3 • 5 • ... • ( 2n – 1 ) • ( 2n + 1 )
    2 • 4 • 6 • ... • ( 2n ) • ( 2n + 2 )     		£ 1
    (n + 2)½    		  is T.
    P ( n + 1 ) : 1 • 3 • 5 • ... • ( 2n – 1 ) • ( 2n + 1 )
    2 • 4 • 6 • ... • ( 2n ) • 2( n + 1 )     		£ 1
    ( n + 2 )½
    Applying the assumption that P(n) is true, we get
    P ( n + 1 ) : [ 1 • 3 • 5 • ... • ( 2n – 1 ) ] • ( 2n + 1 )
    [ 2 • 4 • 6 • ... • ( 2n ) ] • 2 ( n + 1 )     		£ 1
    (n + 2)½
    P ( n + 1 ) : [ 1 ] • ( 2n + 1 )
    [ ( n + 1 )½ ] • 2 ( n + 1 )     		£ 1
    ( n + 2 )½
    P ( n + 1 ) : ( 2n + 1 )
    ( n + 1 )½ 2 ( n + 1 )    		 £ 1
    ( n + 2 )½
    Multiplying both sides of the inequality by 2 ( n + 1 )
    P ( n + 1 ) : ( 2n + 1 )
    ( n + 1 )½    		 £ 2 ( n + 1 )
    ( n + 2 )½
    Multiplying both sides of the inequality by (n+2)½ / (2n + 1)
    P ( n + 1 ) : ( n + 2 )½
    ( n + 1 )½    		 £ 2 ( n + 1 )
    ( 2n + 1 )
    Squaring both sides of the inequality
    P ( n + 1 ) : n + 2
    n + 1    		 £ 4 ( n + 1 )2
    ( 2n + 1 )2
    Multiplying both sides of the inquality by (n+1) (2n + 1)2
    P ( n + 1 ) : ( n + 2 ) ( 2n + 1 )2 £ ( n + 1 ) 4 ( n + 1 )2
    P ( n + 1 ) : 4n3 + 12n2 + 9n + 2 £ 4n3 + 12n2 + 12n + 4
    P ( n + 1 ) : 9n + 2 £ 12n + 4
    P ( n + 1 ) is T.
    Hence, P ( n + 1 ) is T and P(n) ® P ( n + 1 ) is T.
    \ P ( n ) is T.

  12. Prove that if A1, A2, . . ., An and B are sets, then

    13. ( A1 ∩ A2 ∩ . . . ∩ An ) ∪ B = ( A1 ∪ B ) ∩ ( A2 ∪ B ) ∩ . . . ∩ ( An ∪ B ).

    SOLUTION: Proof by induction
    (29) BASIS
    STEP:    		 P(n=2): ( A1 ∩ A2 ) ∪ B = ( A1 ∪ B ) ∩ ( A2 ∪ B )
    •
    •
    •
    P ( n ): ( A1 ∩ A2 ∩ . . . ∩ An ) ∪ B = ( A1 ∪ B ) ∩ ( A2 ∪ B ) ∩ . . . ∩ ( An ∪ B )
    (30) INDUCTIVE
    STEP:    		 Assume that P ( n ) is T.
    Show, by using P ( n ), that P ( n + 1 ) is T.
    Prove P ( n ) ® P ( n + 1 ) by showing P ( n + 1 ) is T.
    P(n+1): ( [ A1 ∩ A2 ∩ . . . ∩ An ] ∩ An+1 ) ∪ B
    = [ ( A1 ∩ A2 ∩ . . . ∩ An ) ∪ B ] ∩ ( An+1 ∪ B )
    = [ ( A1 ∪ B ) ∩ ( A2 ∪ B ) ∩ . . . ∩ ( An ∪ B ) ] ∩ ( An+1 ∪ B )
    = ( A1 ∪ B ) ∩ ( A2 ∪ B ) ∩ . . . ∩ ( An ∪ B ) ∩ ( An+1 ∪ B )
    P ( n + 1 ) is T.
    Hence, P ( n ) ® P ( n + 1 ) is T for all positive integers n.
    \ P ( n ) is T.

  13. Suppose that a store offers gift certificates in denominations of $25 and $40.   Determine the possible total amounts you can form using these gift certificates.   Prove your answer using strong induction.


    14. SOLUTION: Proof by strong induction.  
    Since both $25 and $40 are multiples of $5,
    only total amounts that are multiples of $5 can be formed.
    (31) Observe:
    P(n=5): n$5 = 5•$5 = 1(5•$5)+0(8•$5) = 1•$25+0•$40 = $25
    P(n=8): n$5 = 8•$5 = 0(5•$5)+1(8•$5) = 0•$25+1•$40 = $40
    P(n=10): n$5 = 10•$5 = 2(5•$5)+0(8•$5) = 2•$25+0•$40 = $50
    P(n=13): n$5 = 13•$5 = 1(5•$5)+1(8•$5) = 1•$25+1•$40 = $65
    P(n=16): n$5 = 16•$5 = 0(5•$5)+2(8•$5) = 0•$25+2•$40 = $80
    P(n=15): n$5 = 15•$5 = 3(5•$5)+0(8•$5) = 3•$25+0•$40 = $75
    P(n=18): n$5 = 18•$5 = 2(5•$5)+1(8•$5) = 2•$25+1•$40 = $90
    P(n=21): n$5 = 21•$5 = 1(5•$5)+2(8•$5) = 1•$25+2•$40 = $105
    P(n=24): n$5 = 24•$5 = 0(5•$5)+3(8•$5) = 0•$25+3•$40 = $120
    P(n=20): n$5 = 20•$5 = 4(5•$5)+0(8•$5) = 4•$25+0•$40 = $100
    P(n=23): n$5 = 23•$5 = 3(5•$5)+1(8•$5) = 3•$25+1•$40 = $115
    P(n=26): n$5 = 26•$5 = 2(5•$5)+2(8•$5) = 2•$25+2•$40 = $130
    P(n=29): n$5 = 29•$5 = 1(5•$5)+3(8•$5) = 1•$25+3•$40 = $145
    P(n=32): n$5 = 32•$5 = 0(5•$5)+4(8•$5) = 0•$25+4•$40 = $160
    P(n=25): n$5 = 25•$5 = 5(5•$5)+0(8•$5) = 5•$25+0•$40 = $125
    P(n=28): n$5 = 28•$5 = 4(5•$5)+1(8•$5) = 4•$25+1•$40 = $140
    P(n=31): n$5 = 31•$5 = 3(5•$5)+2(8•$5) = 3•$25+2•$40 = $155
    P(n=34): n$5 = 34•$5 = 2(5•$5)+3(8•$5) = 2•$25+3•$40 = $170
    P(n=37): n$5 = 37•$5 = 1(5•$5)+4(8•$5) = 1•$25+4•$40 = $185
    P(n=40): n$5 = 40•$5 = 0(5•$5)+5(8•$5) = 0•$25+5•$40 = $200
    P(n=30): n$5 = 30•$5 = 6(5•$5)+0(8•$5) = 6•$25+0•$40 = $150
    P(n=33): n$5 = 33•$5 = 5(5•$5)+1(8•$5) = 5•$25+1•$40 = $165
    P(n=36): n$5 = 36•$5 = 4(5•$5)+2(8•$5) = 4•$25+2•$40 = $180
    P(n=39): n$5 = 39•$5 = 3(5•$5)+3(8•$5) = 3•$25+3•$40 = $195
    P(n=42): n$5 = 42•$5 = 2(5•$5)+4(8•$5) = 2•$25+4•$40 = $210
    P(n=45): n$5 = 45•$5 = 1(5•$5)+5(8•$5) = 1•$25+5•$40 = $225
    P(n=48): n$5 = 48•$5 = 0(5•$5)+6(8•$5) = 0•$25+6•$40 = $240
    P(n=35): n$5 = 48•$5 = 7(5•$5)+0(8•$5) = 7•$25+0•$40 = $175
    P(n=38): n$5 = 48•$5 = 6(5•$5)+1(8•$5) = 6•$25+1•$40 = $190
    P(n=41): n$5 = 48•$5 = 5(5•$5)+2(8•$5) = 5•$25+2•$40 = $205
    P(n=44): n$5 = 48•$5 = 4(5•$5)+3(8•$5) = 4•$25+3•$40 = $220
    P(n=47): n$5 = 48•$5 = 3(5•$5)+4(8•$5) = 3•$25+4•$40 = $235
    P(n=50): n$5 = 48•$5 = 2(5•$5)+5(8•$5) = 2•$25+5•$40 = $250
    P(n=53): n$5 = 48•$5 = 1(5•$5)+6(8•$5) = 1•$25+6•$40 = $265
    P(n=56): n$5 = 48•$5 = 0(5•$5)+7(8•$5) = 0•$25+7•$40 = $280
    n = { 5, 8, 10, 13, 15, 16, 18, 20, 21, 23, 24, 25, 26,
    P(n)={ $25, $40, $50, $65, $75, $80, $90, $100, $105, $115, $120, $125, $130,
     
    28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, ...}
    $140, $145, $150, $155, $160, $165, $170, $175, $180, $185, $190, $195, $200, ...}
    4f+1e, 1f+3e, 6f+0e, 3f+2e, 0f+4e, 5f+1e, 2f+3e, 7f+0e, 4f+2e, 1f+4e, 6f+1e, 3f+3e, 0f+5e,
    Let f =$25
    and e =$8     		3 • $25 + $5 = 2 • $40
    3 • $40 + $5 = 5 • $25
    $135, where n = 27, is the largest multiple of $5 that
    cannot be generated by the combinations of $25 and $40.

    After $135 all the multiples of $5
    can be generated by the combination of $25 and $40.
    To prove by strong induction,
    let P ( n ) be the statement that n$5 gift certificates
    can be formed using $25 and $40 denomination certificates.

    Prove that P ( n ) is T for all n ³ 28.
    (32) BASIS
    STEP:    		 From the observation above, P ( 28 ) to at least P ( 40 ) is T.
    Assume that P ( n ) is T.
    Show, by using P ( n ), that P ( n + 1 ) is T.
    Prove P ( n ) ® P ( n + 1 ) by showing the P ( n + 1 ) is T.
    (33) INDUCTIVE
    STEP:    		 Note that when n ³ 28, the gift certificate will contain at least
    three $25 certificates or three $40 certificates.
    Note also that two $40 certificates is $5 more than three $25 certificates
    and five $25 certificates is $5 more than three $40 certificates.
    Hence, to form P ( n + 1 ),
    either replace three $25 = $75 certificates with two $40 = $80 certificates
    or replace three $40 = $120 certificates with five $25 = $125 certificates.
    P ( n + 1 ) is T.
    Hence, P ( n ) ® P ( n + 1 ) is T for n ³ 28.
    \ P ( n ) is T.

  14. Let S be the subset of the set of ordered pairs of integers defined recursively by:


    15. BASIS STEP: ( 0, 0 ) Î S
    RECURSIVE STEP: If ( a, b ) Î S, then ( a + 2, b + 3 ) Î S and ( a + 3, b + 2 ) Î S

    1. List the elements of S produced by the first five applications of the recursive definition.
    2. Use strong induction on the number of applications of the recursive step of the definition to show that

      3. 5 | a + b when ( a, b) Î S.


    SOLUTION: a. (34)
    S = { ( 0, 0 ),
       ( 2, 3 ), ( 3, 2 ), (after 1st application)
       ( 4, 6 ), ( 5, 5 ), ( 6, 4 ), (after 2nd application)
       ( 6, 9 ), ( 7, 8 ), ( 8, 7 ), ( 9, 6 ), (after 3rd application)
       ( 8, 12 ), ( 9, 11 ), ( 10, 10 ), ( 11, 9 ), ( 12, 8 ), (after 4th application)
       ( 10, 15 ), ( 11, 14 ), ( 12, 13 ) , ( 13, 12 ), ( 14, 11 ), (15, 10 ) (after 5th application) }
    S = { ( 0, 0 ), ( 2, 3 ), ( 3, 2 ), ( 4, 6 ), ( 5, 5 ), ( 6, 4 ), ( 6, 9 ), ( 7, 8 ), ( 8, 7 ), ( 8, 12 ), ( 9, 6 ), ( 9, 11 ),
        ( 10, 10 ), ( 10, 15 ), ( 11, 9 ), ( 11, 14 ), ( 12, 8 ), ( 12, 13 ), ( 13, 12 ), ( 14, 11 ), (15, 10 ) }
    b. Let P ( n ) = 5 | a + b whenever ( a, b ) Î S is obtained by n applications of recursive step.
    (35) BASIS
    STEP:
    P ( 0 ): ( 0, 0 ) Î S
    Þ 0 + 0 = 0
    Þ 5 | 0
    \ P ( 0 ) is T
    P ( 1 ): ( 2, 3 ) Î S
    Þ 2 + 3 = 5
    Þ 5 | 5
    ( 3, 2 ) Î S
    Þ 3 + 2 = 5
    Þ 5 | 5
    \ P ( 1 ) is T
    (36) INDUCTIVE
    STEP:
    Assume that P ( n ) is T.
    Show, by using P ( n ), that P ( n + 1 ) is T.
    Prove P ( n ) ® P ( n + 1 ) by showing the P ( n + 1 ) is T.
    For P ( n ), let ( a, b ) Î S where 5 | a + b
    For P ( n + 1 ), ( a + 3, b + 2 ), ( a + 2, b + 3 ) Î S.
    Show that 5 | ( a + 3 ) + ( b + 2 ) and 5 | ( a + 2 ) + ( b + 3 )
    5 | ( a + 3 ) + ( b + 2 )
    = 5 | a + 3 + b + 2
    = 5 | a + b + 3 + 2
    = 5 | a + b + 5
    5 | ( a + 2 ) + ( b + 3 )
    = 5 | a + 2 + b + 3
    = 5 | a + b + 2 + 3
    = 5 | a + b + 5
    P ( n + 1 ) is T.
    Hence, P ( n ) ® P ( n + 1 ) is T.
    \ P ( n ) is T.

  15. Use induction to prove the statement.


    16. Statement: 6 • 7n – 2 • 3n is divisible by 4, for n = 1, 2, ...

    SOLUTION: (37) BASIS
    STEP:         		P ( 1 ): 6 • 71 – 2 • 31
    P ( 1 ): 6 • 7 – 2 • 3
    P ( 1 ): 42 – 6
    P ( 1 ): 36
    36 is divisible by 4
    \ P ( 1 ) is T.
    (38) INDUCTIVE
    STEP:         		Assume P ( n ): 6 • 7n – 2 • 3n is T,
    i.e. P ( n ) is divisible by 4.
    Prove P ( n ) ® P(n+1 by showing
    that P ( n + 1 ): 6 • 7n+1 – 2 • 3n+1 is T,
    i.e. P ( n + 1 ) is divisible by 4.
    P ( n + 1 ): 6 • 7n+1 – 2 • 3n+1
    P ( n + 1 ): 6 • ( 7 • 7n ) – 2 • ( 3 • 3n )
    P ( n + 1 ): [ ( 6 • 7 ) • 7n ] – [ ( 2 • 3 ) • 3n ]
    P ( n + 1 ): [ ( 42 ) • 7n ] – [ ( 6 ) • 3n ]
    P ( n + 1 ): [ ( 6 + 6 • 6 ) • 7n ] – [ ( 2 + 4 ) • 3n ]
    P ( n + 1 ): [ ( 6 • 7n ) + ( 6 • 6 • 7n ) ] – [ ( 2 • 3n ) + ( 4 • 3n ) ]
    P ( n + 1 ): ( 6 • 7n ) + ( 6 • 6 • 7n ) – ( 2 • 3n ) – ( 4 • 3n )
    P ( n + 1 ): ( 6 • 7n ) – ( 2 • 3n ) + ( 6 • 6 • 7n ) – ( 4 • 3n )
    P ( n + 1 ): ( 6 • 7n – 2 • 3n ) + ( 6 • 6 • 7n – 4 • 3n )
    P ( n + 1 ): P ( n ) + ( 36 • 7n – 4 • 3n )
    P ( n + 1 ): P ( n ) + 4 ( 9 • 7n – 3n )
    Since 4 ( 9 • 7n – 3n ) is also divisible by 4,
    then P ( n + 1 ) is divisible by 4.
    Hence, P ( n + 1 ) is T and P ( n ) ® P ( n + 1 ) is T.
    \ P ( n ) is T.

  16. The function log2kn is recursively defined by


    17. log2(k)n = ì
    í
    î    		 n
    log2 ( log2(k-1)n )
    undefined    		 if k = 0
    if log2(k-1)n is defined and positive
    otherwise

    The iterated logarithm is the function log2*n whose value at n is the smallest non-negative integer k such that log2(k)n £ 1.   Find the value of log2(4)2265536.

    SOLUTION: (39) Note that log2(1)n = log2 n, for n > 0
    log2(2)n = log2 ( log2 n ) ) = log2 log2 n, for n > 1
    log2(3)n = log2 ( log2 ( log2 n ) ) ) = log2 log2 log2 n, for n > 2
    •
    •
    •
    log2nn = log2 . . . ( log2 ( log2 n ) ) . . . ) = log2 . . . log2 log2 n, for n > 2
    Recall that 22 = 4
    (22)2 = 42 = 16
    ((22)2)2 = (42)2 = (16)2 = 256
    (((22)2)2)2 = ((42)2)2 = ((16)2)2 = (256)2 = 65536
    Recall that y = bx means exactly the same thing as logb(y) = x
    logbby = x Þ bx = by Þ x = y
    log2(4)2265536 = log2 log2 log2 log2 2265536
    = log2 log2 log2 265536
    = log2 log2 65536
    = log2 log2 216
    = log2 16
    = log2 24
    = 4

  17. Devise a recursive algorithm to find the nth term of the sequence defined by

    18. a0 = 1, a1 = 2, a2 = 3 and an = an-1 + an-2 + an-3, for n = 3, 4, 5, . . .

    SOLUTION: (40) int function Sequence ( n: non-negative integer )
        {
            int k ;

            if ( n < 3 )
                {
                    k = n + 1 ;
                }
            else
                {
                    k = Sequence ( n - 1 ) + Sequence ( n - 2 ) + Sequence ( n - 3 ) ;
                }

            return ( k ) ;
        }
© 2002-04-08 cpsm ; last update 2010-09-08 22:58