CPS420 MIDTERM 1 SOLUTIONS
W2020
PART
1.
A – GRAPH THEORY
Subgraphs and Connectivity (10 marks)
Matrices in Graph Theory (10 marks)
null graph
Connected: Y
1
Connected: Y
2
Connected: Y
3
Connected: Y
1
2
Connected: N
1
3
Connected: N
23
Connected: N
1
23
Connected: N
1
2
Connected: Y
1
3
Connected: Y
1
23 Connected: N
1
23
Connected: N
1
23
Connected: Y
2.
a) 0 b) j0123
i
310 1
1
0
1
0
1
1
2
0
1
0
2
0
0
0
1
0
1.
a1 a2
a3 a4
2.
Terms of the Sequence (4 marks)
= 5 + 1 + 21 = 8
= 5 + 1 + 21 + 2 + 22 = 14
= 5 + 1 + 21 + 2 + 22 + 3 + 23 = 25
= 5 + 1 + 21 + 2 + 22 + 3 + 23 + 4 + 24 = 45
Iteration (6 marks)
2
2 3
PART B – SEQUENCES, RECURRENCE RELATIONS – 10 MARKS
𝑎
= 5 + ∑𝑛 𝑖 + ∑𝑛 2𝑖 = 5 + 𝑛(𝑛+1) + ∑𝑛 2𝑖- 20 𝑛 𝑖=1 𝑖=1 2 𝑖=0
= 5 + 𝑛(𝑛+1) + 2n+1 – 1 – 1 = 2n+1 + 𝑛(𝑛+1) + 3 22
1
CPS420 MIDTERM 1 SOLUTIONS PART C – INDUCTION – 20 MARKS
W2020
1. N+
2.
∑𝑛 𝑖=1
3.
For n=1
𝑛1
∑𝑖2 =∑𝑖2 = 12 =1 𝑖=1 𝑖=1
𝑛(𝑛+1)(2𝑛+1)=1(2)(3)= 6=1 666
So P(1) is true.
4. Inductive Step of the Proof (11 marks)
Assume that P(k) is true for some k≥1, i.e. that ∑𝑘 𝑖=1
Set D (1 mark)
P(n) (4 marks)
𝑖2 = 𝑛(𝑛+1)(2𝑛+1) 6
Basic Step of the Proof (4 marks)
𝑖2 = 𝑘(𝑘+1)(2𝑘+1) (Inductive Hypothesis) 6
We will show that P(k+1) is true, i.e. that ∑𝑘+1 𝑖2 = (𝑘+1)(𝑘+2)(2(𝑘+1)+1) = (𝑘+1)(𝑘+2)(2𝑘+3) 𝑖=1 6 6
𝑘+1
∑ 𝑖2 𝑖=1
𝑘
= (𝑘 + 1)2 + ∑ 𝑖2 𝑖=1
666
= (𝑘 + 1)2 + 𝑘(𝑘+1)(2𝑘+1) 6
by Inductive Hypothesis
= 6(𝑘+1)2+ 𝑘(𝑘+1)(2𝑘+1) = (𝑘+1)(6(𝑘+1)+ 𝑘(2𝑘+1)) = (𝑘+1)(2𝑘2+7𝑘+6)
We want to show that this equal to (𝑘+1)(𝑘+2)(2𝑘+3) i.e. that 2𝑘2 + 7𝑘 + 6 = (𝑘 + 2)(2𝑘 + 3) 6
(𝑘 + 2)(2𝑘 + 3) = 2k2 + 3k + 4k + 6 = 2k2 + 7k + 6 QED
2