Description
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, 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, 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
