## 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