$(2).($a$).$ Solve the following recurrence relation: $a_n=4a_{\frac{n}{2}}+3n,a_1=1($You may assume that $n=2^m,$ for some $m=0,1,2,$dots $)$

$($b$).$ Consider the recursion $a_n=2a_{n-1}+1,$ with initial condition $a_1=1.$ Prove $($using induction$)$ that $a_n=2^n-1.$