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: 






(3)  Desired conclusion: 


(4)  Proof: 
The proof is complete. 
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: 




(7)  Desired conclusion: 


(8)  Proof: 
The proof is complete. 
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. 
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) 
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) 
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: 




(14)  Desired conclusion: 


(15)  Proof: 


b.  (16)  Let 
m ( x ) mean that Quincy likes movie x.
a ( x ) mean that x is an action movie. 

(17)  Given hypotheses: 




(18)  Desired conclusion: 


(19)  Proof: 

SOLUTION: 


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 
p_{1} « p_{4}, p_{2} « p_{3}, p_{1} « p_{3}.
SOLUTION:  (24)  Proof: 
Given p_{1} « p_{4} and
p_{2} « p_{3} and
p_{1} « p_{3}.
Þ Since p_{1} « p_{3} and p_{2} « p_{3}, then p_{1} « p_{2}. Þ Since p_{1} « p_{4} and p_{1} « p_{2}, then p_{2} « p_{4}. Þ Since p_{1} « p_{3} and p_{1} « p_{4}, then p_{3} « p_{4} Þ \ p_{1} « p_{2} « p_{3} « p_{4} Þ the proof is complete 

1 1 • 2 
+  1 2 • 3 
+  1 3 • 4 
+  . . .  +  1 n ( n + 1 ) 

SOLUTION:  Proof by induction  

(25)  BASIS STEP: 
• • •


(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 ) is T.
Hence, P ( n ) ® P ( n + 1 ) is T for all positive integers n. \ P ( n ) is T. 
Inequality: 
[ 1 • 3 • 5 • ... • ( 2n – 1 ) ] [ 2 • 4 • 6 • ... • ( 2n ) ] 
£  1 ( n + 1 )^{½} 
, for n = 1, 2, ... 

SOLUTION:  (27)  BASIS STEP: 



(28)  INDUCTIVE STEP: 


P ( n + 1 ) is T.
Hence, P ( n + 1 ) is T and P(n) ® P ( n + 1 ) is T. \ P ( n ) is T. 
( A_{1} ∩ A_{2} ∩ . . . ∩ A_{n} ) ∪ B = ( A_{1} ∪ B ) ∩ ( A_{2} ∪ B ) ∩ . . . ∩ ( A_{n} ∪ B ).
SOLUTION:  Proof by induction  

(29)  BASIS STEP: 
P(n=2):  ( A_{1} ∩ A_{2} ) ∪ B = ( A_{1} ∪ B ) ∩ ( A_{2} ∪ B )  
• • •  
P ( n ):  ( A_{1} ∩ A_{2} ∩ . . . ∩ A_{n} ) ∪ B = ( A_{1} ∪ B ) ∩ ( A_{2} ∪ B ) ∩ . . . ∩ ( A_{n} ∪ 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):  ( [ A_{1} ∩ A_{2} ∩ . . . ∩ A_{n} ] ∩ A_{n+1} ) ∪ B  
= [ ( A_{1} ∩ A_{2} ∩ . . . ∩ A_{n} ) ∪ B ] ∩ ( A_{n+1} ∪ B )  
= [ ( A_{1} ∪ B ) ∩ ( A_{2} ∪ B ) ∩ . . . ∩ ( A_{n} ∪ B ) ] ∩ ( A_{n+1} ∪ B )  
= ( A_{1} ∪ B ) ∩ ( A_{2} ∪ B ) ∩ . . . ∩ ( A_{n} ∪ B ) ∩ ( A_{n+1} ∪ B )  
P ( n + 1 ) is T.
Hence, P ( n ) ® P ( n + 1 ) is T for all positive integers n. \ P ( n ) is T. 
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: 




$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. 
BASIS STEP:  ( 0, 0 ) Î S 

RECURSIVE STEP:  If ( a, b ) Î S, then ( a + 2, b + 3 ) Î S and ( a + 3, b + 2 ) Î S 
5  a + b when ( a, b) Î S.
SOLUTION:  a.  (34) 



b.  Let P ( n ) = 5  a + b whenever ( a, b ) Î S is obtained by n applications of recursive step.  
(35)  BASIS STEP: 


(36)  INDUCTIVE STEP: 

Statement:  6 • 7^{n} – 2 • 3^{n} is divisible by 4, for n = 1, 2, ... 
SOLUTION:  (37)  BASIS STEP: 
P ( 1 ): 6 • 7^{1} – 2 • 3^{1}
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 • 7^{n} – 2 • 3^{n} is T,
i.e. P ( n ) is divisible by 4. Prove P ( n ) ® P(n+1 by showing that P ( n + 1 ): 6 • 7^{n+1} – 2 • 3^{n+1} is T, i.e. P ( n + 1 ) is divisible by 4. 

P ( n + 1 ): 6 • 7^{n+1} – 2 • 3^{n+1}
P ( n + 1 ): 6 • ( 7 • 7^{n} ) – 2 • ( 3 • 3^{n} ) P ( n + 1 ): [ ( 6 • 7 ) • 7^{n} ] – [ ( 2 • 3 ) • 3^{n} ] P ( n + 1 ): [ ( 42 ) • 7^{n} ] – [ ( 6 ) • 3^{n} ] P ( n + 1 ): [ ( 6 + 6 • 6 ) • 7^{n} ] – [ ( 2 + 4 ) • 3^{n} ] P ( n + 1 ): [ ( 6 • 7^{n} ) + ( 6 • 6 • 7^{n} ) ] – [ ( 2 • 3^{n} ) + ( 4 • 3^{n} ) ] P ( n + 1 ): ( 6 • 7^{n} ) + ( 6 • 6 • 7^{n} ) – ( 2 • 3^{n} ) – ( 4 • 3^{n} ) P ( n + 1 ): ( 6 • 7^{n} ) – ( 2 • 3^{n} ) + ( 6 • 6 • 7^{n} ) – ( 4 • 3^{n} ) P ( n + 1 ): ( 6 • 7^{n} – 2 • 3^{n} ) + ( 6 • 6 • 7^{n} – 4 • 3^{n} ) P ( n + 1 ): P ( n ) + ( 36 • 7^{n} – 4 • 3^{n} ) P ( n + 1 ): P ( n ) + 4 ( 9 • 7^{n} – 3^{n} ) 

Since 4 ( 9 • 7^{n} – 3^{n} ) 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. 
log_{2}^{(k)}n =  ì í î 
n log_{2} ( log_{2}^{(k1)}n ) undefined 
if k = 0 if log_{2}^{(k1)}n is defined and positive otherwise 

The iterated logarithm is the function log_{2}*n whose value at n is the smallest nonnegative integer k such that log_{2}^{(k)}n £ 1. Find the value of log_{2}^{(4)}2^{265536}.
SOLUTION:  (39)  Note that 
log_{2}^{(1)}n = log_{2} n, for n > 0
log_{2}^{(2)}n = log_{2} ( log_{2} n ) ) = log_{2} log_{2} n, for n > 1 log_{2}^{(3)}n = log_{2} ( log_{2} ( log_{2} n ) ) ) = log_{2} log_{2} log_{2} n, for n > 2 • • • log_{2}^{n}n = log_{2} . . . ( log_{2} ( log_{2} n ) ) . . . ) = log_{2} . . . log_{2} log_{2} n, for n > 2 

Recall that 
2^{2} = 4
(2^{2})^{2} = 4^{2} = 16 ((2^{2})^{2})^{2} = (4^{2})^{2} = (16)^{2} = 256 (((2^{2})^{2})^{2})^{2} = ((4^{2})^{2})^{2} = ((16)^{2})^{2} = (256)^{2} = 65536 

Recall that 
y = b^{x} means exactly the same thing as log_{b}(y) = x
log_{b}b^{y} = x Þ b^{x} = b^{y} Þ x = y 

log_{2}^{(4)}2^{265536} 
= log_{2} log_{2} log_{2} log_{2} 2^{265536}
= log_{2} log_{2} log_{2} 2^{65536} = log_{2} log_{2} 65536 = log_{2} log_{2} 2^{16} = log_{2} 16 = log_{2} 2^{4} = 4 
a_{0} = 1, a_{1} = 2, a_{2} = 3 and a_{n} = a_{n1} + a_{n2} + a_{n3}, for n = 3, 4, 5, . . .
SOLUTION:  (40) 
int function Sequence ( n: nonnegative integer )
{ int k ; if ( n < 3 ) { k = n + 1 ; } else { k = Sequence ( n  1 ) + Sequence ( n  2 ) + Sequence ( n  3 ) ; } return ( k ) ; } 
