Use mathematical induction to prove that n (1/2)2^(n) for all integers n 0.

Give an asymptotic estimate, using the -notation, for g(n) = 2^(n) n. You need to give a completerigorous proof derived directly from the definitions of O-notation and -notation. (Without using anytheorems from class.)Hint: In (a), deal with the case n = 0 separately, and use induction for n 1. In (b), the inequality inpart (a) will be helpful in showing the -estimate for g(n).