title: Solving a recurrence T(n) = 2T(n/2) + sqrt(n)
body: <p>Need a little help! This is what I have so far using backward substitution:</p>
  
  <pre><code>T(n) = 2T(n/2) + sqrt(n), where T(1) = 1, and n = 2^k
  T(n) = 2[2T(n/4) + sqrt(n/2)] + sqrt(n) = 2^2T(n/4) + 2sqrt(n/2) + sqrt(n)
  T(n) = 2^2[2T(n/8) + sqrt(n/4)] + 2sqrt(n/2) + sqrt(n)
       = 2^3T(n/8) + 2^2sqrt(n/4) + 2sqrt(n/2) + sqrt(n)
  </code></pre>
  
  <p>In general</p>
  
  <pre><code>T(n) = 2^kT(1) + 2^(k-1) x sqrt(2^1) + 2^(k-2) x sqrt(2^2) + ... + 2^1 x sqrt(2^(k-1)) + sqrt(2^k)
  </code></pre>
  
  <p>Is this right so far? If it is, I can not figure out how to simplify it and reduce it down to a general formula.</p>
  
  <p>I'm guessing something like this? Combining the terms</p>
  
  <pre><code>= 1 + 2^(k-(1/2)) + 2^(k-(2/2)) + 2^(k-(3/2)) + ... + 2^((k-1)/2) + 2^(k/2)
  </code></pre>
  
  <p>And this is where I'm stuck. Maybe a way to factor out a 2^k?
  Any help would be great, thanks!</p>