Problem Set 3 Solution

$30.00

Description

  1. [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. [1 mark] What are the values of a0, a1, a2, and a3?

  1. [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. [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?

  1. [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.

  1. [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.

  1. [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

  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