title: How do you pick variable substitutions in recurrence relations?
body: <p>In our Data Structures class we are learning how to solve recurrence relations in 1 variable. Unfortunately some things seem to come "out of the blue".</p>
  
  <p>For example, some exercises already tell you how to substitute the variable n:</p>
  
  <p>Compute T(n) for n = 2^k</p>
  
  <ul>
  <li><p>T(n) = a for n =&lt; 2</p></li>
  <li><p>T(n) = 8T(n/2) + bn^2 (a and b are > 0)</p></li>
  </ul>
  
  <p>But some exercises just give you the T(n) without providing a replacement for the variable n:</p>
  
  <ul>
  <li><p>T(n) = 1 n =&lt;1</p></li>
  <li><p>T(n) = 2T(n/4) + sqrt(n)</p></li>
  </ul>
  
  <p>I used the iterative method and arrived to the right answer: sqrt(n) + (1/2) * sqrt(n) * Log(n).</p>
  
  <p>But when the professor explained she started by saying: "Let n = 4^k", which is what I mean by "out of the blue". Using that fact the answer is simpler to obtain.</p>
  
  <p>But how is the student supposed to come up with that?</p>
  
  <p>This is another example:</p>
  
  <ul>
  <li><p>T(n) = 1 n =&lt;1</p></li>
  <li><p>T(n) = 2T( (n-1)/2 ) + n</p></li>
  </ul>
  
  <p>Here I started again with the iterative method but I can't reach a definitive answer, it looks more complex that way. 
  After 3 iterative steps I arrived to this:</p>
  
  <ol>
  <li><p>T(n) = 4T( (n-2)/4 ) + 2n - 1</p></li>
  <li><p>T(n) = 8T( (n-3)/8 ) + 3n - 3</p></li>
  <li><p>T(n) = 16T( (n-4)/16 ) + 4n - 6</p></li>
  </ol>
  
  <p>I am inclined to say T(i) = 2^i * T( (n-i)/2^i ) + i*n - ? This last part I can't figure out, maybe I made a mistake.</p>
  
  <p>However in the answer she provides she starts again with another substitution: Let n = (2^k) -1. I don’t see where this comes from - why would I do this? What is the logic behind that? </p>