[4 marks] Special numbers. For each n 2 N, de ne Fn = 22n + 1:
n 1
Y
Prove that for all natural numbers n, Fn 2 = Fi.
i
=0
Hints:
Please review product notation, including empty products, on page 16 of the course notes. For all n 2 N, 22n+1 = (22n )2.
2. [8 marks] Sequences. We de ne the following sequence of numbers a0; a1; a2 : : : recursively as:
a0 = 1; and for all n 2 N, an+1 =
1
1
+ 1
an
[1 mark] What are the values of a0, a1, a2, and a3?
[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
8n 2 N; an =
By \non-recursive" we mean that the formula you use to ll in the blank should not involve any ai terms.
[1 mark] Let’s now generalize the previous part. For every natural number k greater than 1, we de ne an in nite sequence ak;0; ak;1; : : : recursively as follows:
ak;0 = k; and for all n 2 N, ak;n+1 =
k
1
+ 1
ak;n
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?
[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 quanti cations in a proof by induction by rst letting one variable be arbitrary, and then doing induction on the other variable.
[11 marks] Properties of Asymptotic Notation.
Let f : N ! R 0. We de ne the cumulative sum of f, denoted Sumf , to be the function Sumf : N ! R 0 de ned as follows:
n
X
Sumf (n) = f(i) = f(0) + f(1) + + f(n)
i=0
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 de nition of big-Oh.
[4 marks] Prove that for all f : N ! R 0, if f 2 O(n), then Sumf 2 O(n2).
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:
b
c
b
Xi=a f(i) =
Xi=a
f(i) + i=Xc+1
f(i)for all a c b.
2n
(b) [3 marks] Prove by induction that for all natural numbers n, X 1i n2.
i=1
[4 marks] Using part (b), disprove the following claim: for all f; g : N ! R 0, if f(n) 2 O(g(n)), then Sumf (n) 2 O(n g(n)).
Page 4/4
