CSC165H1: Problem Set 3

CSC165H1 Problem Set 3
CSC165H1: Problem Set 3

General instructions
Please read the following instructions carefully before starting the problem set. They contain important
information about general problem set expectations, problem set submission instructions, and reminders
of course policies.
• Your problem sets are graded on both correctness and clarity of communication. Solutions that are
technically correct but poorly written will not receive full marks. Please read over your solutions
carefully before submitting them.
• Each problem set may be completed in groups of up to three. If you are working in a group for this
problem set, please consult https://github.com/MarkUsProject/Markus/wiki/Student_Groups
for a brief explanation of how to create a group on MarkUs.
Exception: Problem Set 0 must be completed individually.
• Solutions must be typeset electronically, and submitted as a PDF with the correct filename. Handwritten submissions will receive a grade of ZERO.
The required filename for this problem set is problem set3.pdf.
• Problem sets must be submitted online through MarkUs. If you haven’t used MarkUs before, give
yourself plenty of time to figure it out, and ask for help if you need it! If you are working with a
partner, you must form a group on MarkUs, and make one submission per group. “I didn’t know
how to use MarkUs” is not a valid excuse for submitting late work.
• Your submitted file should not be larger than 9MB. This may happen if you are using a word
processing software like Microsoft Word; if it does, you should look into PDF compression tools to
make your PDF smaller, although please make sure that your PDF is still legible before submitting!
• Submissions must be made before the due date on MarkUs. You may use grace tokens to extend
the deadline; please see the Problem Set page for details on using grace tokens.
• The work you submit must be that of your group; you may not refer to or copy from the work of
other groups, or external sources like websites or textbooks. You may, however, refer to any text
from the Course Notes (or posted lecture notes), except when explicitly asked not to.
Additional instructions
• For each proof by induction, clearly define the predicate (P(n)) that is relevant for your induction
proof, so that you’re proving a statement with structure ∀n ∈ N, P(n) or ∀n ∈ N, n ≥ ⇒ P(n).
• Always label the steps that use the induction hypothesis.
• You may not use forms of induction we have not covered in lecture.
• Please follow the same guidelines as Problem Set 2 for all proofs.
Page 1/4
CSC165H1, Winter 2018 Problem Set 3
1. [4 marks] Special numbers. For each n ∈ N, define Fn = 22
n
+ 1.
Prove that for all natural numbers n, Fn − 2 =
nY−1
i=0
Fi
.
Hints:
• Please review product notation, including empty products, on page 16 of the course notes.
• For all n ∈ N, 22
n+1 = (22
n
)
2
.
Page 2/4
CSC165H1, Winter 2018 Problem Set 3
2. [8 marks] Sequences. We define the following sequence of numbers a0, a1, a2 . . . recursively as:
a0 = 1, and for all n ∈ N, an+1 =
1
1
an
+ 1
(a) [1 mark] What are the values of a0, a1, a2, and a3?
(b) [3 marks] Find and prove a non-recursive formula for an that is valid for all natural numbers n.
That is, the statement you will prove should be of the form
∀n ∈ N, an =
By “non-recursive” we mean that the formula you use to fill in the blank should not involve any ai
terms.
(c) [1 mark] Let’s now generalize the previous part. For every natural number k greater than 1, we
define an infinite sequence ak,0, ak,1, . . . recursively as follows:
ak,0 = k, and for all n ∈ N, ak,n+1 =
k
1
ak,n
+ 1
What are the values of a2,0, a2,1, a2,2, and a2,3? What are the values of a3,0, a3,1, a3,2, and a3,3?
(d) [3 marks] Find and prove a non-recursive formula for ak,n that is valid for all natural numbers k
greater than 1, and all natural numbers n. Hint: as we saw in class, it’s easiest to handle multiple
universal quantifications in a proof by induction by first letting one variable be arbitrary, and then
doing induction on the other variable.
Page 3/4
CSC165H1, Winter 2018 Problem Set 3
3. [11 marks] Properties of Asymptotic Notation.
Let f : N → R
≥0
. We define the cumulative sum of f, denoted Sumf , to be the function Sumf : N →
R
≥0 defined as follows:
Sumf (n) = Xn
i=0
f(i) = f(0) + f(1) + · · · + f(n)
For example, we have previously proved in this course that if f(n) = n, then Sumf (n) = n(n + 1)
2
.
In Parts (a) and (c), you may not use any theorems that may have been shown in lecture/tutorial, and
must use the formal definition of big-Oh.
(a) [4 marks] Prove that for all f : N → R
≥0
, if f ∈ O(n), then Sumf ∈ O(n
2
).
Hint: be careful about choosing constants here! It may be tempting to say that “f(n) ≤ kn,” but
this is only true after a certain point. Also remember that you can break up summations:
X
b
i=a
f(i) = Xc
i=a
f(i) + X
b
i=c+1
f(i) for all a ≤ c ≤ b.
(b) [3 marks] Prove by induction that for all natural numbers n,
2
Xn
i=1
1
i
≥
n
2
.
(c) [4 marks] Using part (b), disprove the following claim: for all f, g : N → R
≥0
, if f(n) ∈ O(g(n)),
then Sumf (n) ∈ O(n · g(n)).
Page 4/4