CPS420 MIDTERM 1 SOLUTIONS PART A – GRAPH THEORY – 20 MARKS
W2018
1.
Equivalent Graphs (4 marks)
A B2C
H9C 79842
D8H EF631
1
364 D7A5FB
2.
G5GE Graph Degrees (6 marks)
a) A graph with 5 vertices of degrees 5, 5, 4, 4, 3
This is not possible because the total degree of this graph would be 21 which is odd. By the Handshake theorem graphs must have even degrees,
b) A graph with 5 vertices of degrees 5, 5, 4, 4, 4
There are many possible answers. For
example
3.
Problem Solving with Graphs (10 marks)
WGCR|
RG
WC|RG
R
RC RG
RG RC
R
GR|CW
RG
|GRCW
WCR|G
W|RGC
WRG|C
RW
RW
C|RGW
PART B – SEQUENCES, RECURRENCE RELATIONS – 10 MARKS
1. Terms of a Sequence (6 marks)
a2 = a1 + 1 = 1⁄2 + 1/(2×3) = 1⁄2 × (1+1/3) = 1⁄2 × 4/3 =2/3 2(3)
= 3/4 + 1/(4×5) = 1/4 × (3+1/5) = 1/4 × 16/5 =4/5
CRG|W
G|RCW
a3 = a2+
a4 = a3 + 1
1 = 2/3 + 1/(3×4) = 1/3 × (2+1/4) = 1/3 × 9/4 =3/4 3(4)
4(5)
2. Iteration (4 marks) an = n / (n+1)
1
CPS420 MIDTERM 1 SOLUTIONS PART C – INDUCTION – 20 MARKS
W2018
1. Mathematical (weak) Induction (10 marks)
Prove by induction that for all positive integers n, ∑𝑛 𝑖=2
𝑖(𝑖 − 1) = 𝑛(𝑛−1)(𝑛+1) 3
Let P(n) be the property: ∑𝑛 𝑖=2
We must prove nN+ P(n) Proof by induction
Base case:
𝑖(𝑖 − 1) = 𝑛(𝑛−1)(𝑛+1) 3
𝑖(𝑖−1)=0
Letn=1,then ∑𝑛 𝑖(𝑖−1)=∑0
𝑖=2
Also 𝑛(𝑛−1)(𝑛+1) = 1(0)(2) = 0
33
So P(0) is true Inductive step:
𝑖=2
QED
2.
= 1/3 [3k(k+1) + k(k-1)(k+1)] = k(k+1)/3 [3+(k-1)]
= k(k+1)(k+2)/3
Types of induction (10 marks)
Assume that P(k) is true for some k1
i.e. ∑𝑘 𝑖(𝑖 − 1) = 𝑘(𝑘−1)(𝑘+1) (Inductive Hypothesis)
𝑖=2
𝑖=2 = k(k+1) + 𝑘(𝑘−1)(𝑘+1)
𝑖=2 3
We will show that P(k+1) is also true
i.e. we will show that ∑𝑘+1 𝑖(𝑖 − 1) = (𝑘+1)𝑘(𝑘+2)
𝑖=2
∑𝑘+1 𝑖(𝑖 − 1) = (𝑘 + 1)(𝑘) + ∑𝑘
3 𝑖(𝑖 − 1)
Definition of sum
by Inductive Hypothesis
algebra algebra algebra
3
Proof description
Needs
strong induction? (Y/N)
Explanation of your answer
Proof of the correctness of the solution for the sequence an recursively defined as:
a1=2, a2=3, an=an-2+2 for n>2
Y
The recurrence relation defines an in terms of an-2, Therefore in order to prove that the solution is correct for an, one must assume that the solution is correct for an-2. Therefore the inductive hypothesis cannot be simply that the solution is correct for an-1.
Proof of the correctness of the solution for the sequence bn recursively defined as:
b1=2, b2=5, bn=bn-1+3 for n>2
N
Even though this sequence has a recurrence relation that starts at n=3, the recurrence relation is also true for n=2, Therefore this sequence is a simple arithmetic sequence starting at n=1 with a recurrence relation where each term is defined as a function of the previous term. The correctness of the solution an= 2+3(n-1) can be proved using mathematical induction.
Proof that every positive integer has a unique binary representation starting with a leading 1.
Y
The proof of the existence part of this theorem is a proof by induction which proves the property for an integer n by assuming that it is true for n/2. Therefore the inductive hypothesis must be that the property is true for all number less than n.
2