Proofs and Recursion - MTH 305X Test 2

This document covers proof techniques and recursive definitions. It includes examples and solutions for contrapositive, converse, proof by contradiction, proof by exhaustion, and Fibonacci sequence.

Name____________________________________
MTH 305X Test 2
Proofs and Recursion
Proof Techniques
1. Write the contrapositive of “If n is even then n+1 is odd.”
Solution
If n+1 is even then n is odd
Can the contrapositive be used to prove P→ Q?
Solution
The contrapositive can be used to prove P→ Q? Since n+1 can only be even if n
is odd.
2. Write the converse of “If n is even then n+1 is odd.”
Answer: If n+1 is odd then n is even
Can the converse be used to prove P→ Q?
Solution
The converse can be used to prove P→ Q? Since n+1 can only be odd if n is
even.
3. To begin a proof by contradiction for “If n is even then n+1 is odd,”
what would you “assume true?”
Solution
I would assume n is even to be true and n+1 is odd to be false
4. Prove that the following is not true by finding a counterexample.
“The sum of any 3 consecutive integers is even.”
Solution
Case 1
Consider the following three consecutive integers: 2, 3, and 4
The sum of the three numbers is 9 which is not even
Case 2
Consider the following different three consecutive integers: 10, 11, and 12
The sum of the three numbers is 33 which is not even

Therefore, the statement “The sum of any 3 consecutive integers is even.” Is not true.
5. Show a Proof by exhaustion for the following: For n = 2, 4, 6, n²-1 is odd.
Solution
Case 1: n = 2
n2 – 1 = 22-1 = 4 – 1 = 3
Case 2: n = 4
n2 – 1 = 42-1 = 16 – 1 = 15
Case 3: n = 6
n2 – 1 = 62-1 = 36 – 1 = 35
6. Show an informal Direct Proof for “The sum of 2 even integers is even.”
Solution
Let the two even numbers be x and y
Therefore x+y is even.
Let x = 2, y = 4, 2 + 4 = 6 which is even
Let x =8, y = 6, 8 + 6 = 14 which is even
Let x =10, y = 12, 10 + 12 = 22 which is even
Therefore, the sum of two even integers is always even
Recursive Definitions
7. The Fibonacci Sequence is defined as follows:
F(1) = 1
F(2) = 1
F(n) = F(n-1) + F(n-2) for n>2.
The first 10 numbers in the sequence are 1, 1, 2, 3, 5, 8, 13, 21, 34, 55.
Find F(13) = 144+89 = 233 and F(14) = 233+144=377
8. Prove the following property of the Fibonacci numbers directly from the definition.
F(n+3) = 2F(n+1) + F(n-3)+ 2F(n-2)
Solution
Since F(1) = 1, the smallest value of n should be n – 3 = 1, from which n = 4
Case 1: let n = 4
F(n+3) = 2F(n+1) + F(n-3)+ 2F(n-2) becomes F(4+3) = 2F(4+1) + F(4-3)+ 2F(4-2)

F(7) = 2F(5) + F(1)+ 2F(2) which is true since
F(7) = 13, 2F(5) = 10, F(1) = 1, 2F(2) = 2
10+1+2 = 13
Case 2: let n = 10
F(10+3) = 2F(10+1) + F(10-3)+ 2F(10-2)
F(13) = 2F(11) + F(7)+ 2F(8)
233 = 178 + 13 + 42
Which is true
Therefore we can conclude that F(n+3) = 2F(n+1) + F(n-3)+ 2F(n-2)
9. Find the 3rd, 4th and 5th values in the sequence.
D(1) = 0
D(n) = 2D(n-1) + 2 for n>1.
D(2) = 0 +2 =2
D(3) = 4+2 = 6
D(4) = 12+2=14
10. Find the 3rd, 4th and 5th values in the sequence.
D(1) = 1
D(2) = 4
D(n) = 2D(n-1) + D(n-2) for n>2.
D(3) = 8+1 =9
D(4) = 18+4 =22
D(5) = 44 + 9 = 53
11. Using the Selection Sort algorithm on p 169 in your textbook, simulate the execution
of the algorithm on the following list L; write the list after every exchange.
L: 9, 2, 4, 8, 6
Solution
1st exchange: 2, 4,8,6,9
2nd exchange: 2, 4,6,8,9
The Elements of Advanced Mathematics Third Edition

References
Hunter, D. J. (2010). Essentials of Discrete Mathematics. Burlington, MA: Jones & Bartlett
Publishers.
Wallis, W. (2011). A Beginner's Guide to Discrete Mathematics. Berlin, Germany: Springer
Science & Business Media.