Analysis of Algorithms

I have some questions which are needed to be completed by tomorrow. Some of them i am going to post here. Kindly message me if you are able to complete this project on time. 1. Let {fn : n = 0,1,...} be the Fibonacci sequence (where by convention f0 = 0 and f1 = 1). (a) Prove that ∞ nfn =20 n=1 2n−1 Do this by using a generating function as shown in the last section of the Lecture 2 notes, and differentiating. (b) Show why (in the same way as you proved the first part of this problem) you might think that ∞ nfn = 2 n=1 Then show why it could not possibly be true. 2. Prove that for positive integers a, b, and n, n a b = a+b k=0 k n−k n Use the following facts in your proof: (a) (1+x)a(1+x)b =(1+x)a+b (b) You may find it convenient at some point to remember that if m and j are integers (and m ≥ 0), then mj = 0 i f j < 0 o r j > m 3. Decide whether each of the following statements is true or false, and prove that your conclusion is correct. • n2 = O(2n) • 2n+1 = O(2n) • 22n = O(2n) • f(n) = O g(n) implies 2f(n) = O 2g(n) 4. Provethatlogax=O(logbx)foranya>1andb>1.