title: Solving a recurrence: T(n)=3T(n/2)+n
body: <p>I need to Find the solution of the recurrence for n, a power of two if <code>T(n)=3T(n/2)+n</code> for n>1 and T(n)=1 otherwise.</p>
  
  <p>using substitution of <code>n=2^m,S(m)=T(2^(m-1))</code> I can get down to:</p>
  
  <p><code>S(m)=2^m+3*2^(m-1)+3^2*2^(m-2)+⋯+3^(m-1) 2^1+3^m</code></p>
  
  <p>But I have no idea how to simply that.</p>