MTH 305X Test 2: Proofs, Recursion, and Algorithm Solutions

This document provides comprehensive solutions to a math assignment focusing on proof techniques and recursive definitions. The assignment covers various proof methods including contrapositive, converse, and proof by contradiction. It also includes problems on the Fibonacci sequence and recursive sequences, requiring students to find specific values and prove properties. Additionally, the document demonstrates the selection sort algorithm. The solutions are detailed, providing step-by-step explanations and examples to aid in understanding the concepts. The assignment covers topics such as direct proofs, proof by exhaustion, and counterexamples, all fundamental concepts in discrete mathematics. The document serves as a valuable resource for students studying proof techniques and recursion.

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.