Problem 4: [10 points] Solve the following recurrences exactly, using backward substitution. (a) T(1)=8 and for all n2,T(n)=2T(n1)5 (b) T(1)=3 and for all n2,T(n)=T(n1)+n1 (c) T(1)=1 and for all n2 such that n is a power of 2,T(n)=2T(2n)+2n (d) T(1)=1 and for all n2 such that n is a power of 3,T(n)=T(3n)+n