Please help with 1.67

1.67. Find an exact closed-form formula for T in each of the following recursions when n=2m for mZ+: (i) T(n)=8T(2n)+n. (ii) T(n)=3T(2n)+n. (iii) T(n)=3T(2n)+n3. 1.68. Prove that the recurrence T(n)=3T([4n)+nlogn,n2, with T(1)=T1>0, satisfies T(n)O(nlogn). 1.69. Assume that T(n) satisfies the recurrence (1.45) for n=bm for mN. Generalize Theorem 1.10.2(ii) by proving the following theorem: If d=logba and f(n)O(nd(logn)), then T(n)O(nd(logn)+1). Hint: Show that T(n)O(ndm+1) and then use the fact that m=logbn. 1.70. Show that the sequence (1.55) satisfies bknnk for each k{0,1,2,,m}. In particular, bmnnm=1. 1.71. Prove that recursion depth m, given by the sequence (1.55), is bounded below by logbn, that is, mlogbn