Please help with 1.69.

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. Theorem 1.10.2 (Master Theorem). Consider a function T:Z+[0,) satisfying the recursion rule T(n){aT(bn)+f(n)T1ifn>1ifn=1 where a>0 and T1>0 are real constants, b2 is an integer constant, and f(n) is nonnegative, with fO(nd) for some d0. (i) If bd>a, then T(n)O(nd). (ii) If bd=a, then T(n)O(ndlogn). (iii) If bd