$30.00
Description

[4 marks] Special numbers. For each n 2 N, de ne F_{n} = 2^{2}^{n} + 1:
n 1
Y
Prove that for all natural numbers n, F_{n} 2 = F_{i}.
i
=0
Hints:
Please review product notation, including empty products, on page 16 of the course notes. For all n 2 N, 2^{2}^{n+1} = (2^{2}^{n} )^{2}.
2. [8 marks] Sequences. We de ne the following sequence of numbers a_{0}; a_{1}; a_{2} : : : recursively as:

a_{0} = 1; and for all n 2 N, a_{n+1} =
1
1
+ 1
a_{n}

[1 mark] What are the values of a_{0}, a_{1}, a_{2}, and a_{3}?

[3 marks] Find and prove a nonrecursive formula for a_{n} that is valid for all natural numbers n. That is, the statement you will prove should be of the form
8n 2 N; a_{n} =
By \nonrecursive” we mean that the formula you use to ll in the blank should not involve any a_{i} 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 a_{k;0}; a_{k;1}; : : : recursively as follows:

a_{k;0} = k; and for all n 2 N, a_{k;n+1} =
k
1
+ 1
^{a}k;n
What are the values of a_{2;0}, a_{2;1}, a_{2;2}, and a_{2;3}? What are the values of a_{3;0}, a_{3;1}, a_{3;2}, and a_{3;3}?

[3 marks] Find and prove a nonrecursive formula for a_{k;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 Sum_{f} , to be the function Sum_{f} : N ! R ^{0} de ned as follows:
n
X
Sum_{f} (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 bigOh.

[4 marks] Prove that for all f : N ! R ^{0}, if f 2 O(n), then Sum_{f} 2 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:

b
c
b
^{X}_{i=a} f(i) =
^{X}i=a
f(i) + _{i=}^{X}_{c+1}
f(i)for all a c b.
2^{n}
(b) [3 marks] Prove by induction that for all natural numbers n, ^{X} ^{1}_{i} ^{n}_{2}.
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 Sum_{f} (n) 2 O(n g(n)).
Page 4/4