python

1. The Fibonacci numbers F0, F1, F2, ... are defined by the following:

F0 = 0, F1 = 1, Fn = Fn1 + Fn2.

(a) Use proof by induction approach to prove that Fn 2 0.5n for n 6. Recall that proof by induction has two steps: basis step and inductive step.

(b) Find a positive constant c < 1 such that Fn 2 cn for all n 0. Justify your answer. Hint: you may use the idea of proof by induction and focus on the inductive step.

2. Prove the following:

(a) 4n log n = O(n 2 )

(b) n 1/2 = (n 1/3)

(c) 5 n is not O(3 n )

3. Let c be a positive real number. Show that, g(n) = 1 + c + c 2 + ... + c n is

(a) (1) if c < 1;

(b) (n) if c = 1;

(c) (c n ) if c > 1.

Hint: Here g(n) is the sum of a geometric series which can be expressed compactly using its closed-form formula. You may also want to use the following lemma to show the results. Lemma: Let T(n) and g(n) are two functions such that limn T(n) g(n) = c for some positive number c. Then, T(n) = (g(n)).