title: Solving T(n) = 4T(n/2)+n²
body: <p>I am trying to solve a recurrence using substitution method. The recurrence relation is:</p>
  
  <blockquote>
    <p>T(n) = 4T(n/2)+n<sup>2</sup></p>
  </blockquote>
  
  <p>My guess is T(n) is Θ(nlogn) (and i am sure about it because of master theorem), and to find an upper bound, I use induction. I tried to show that 
  T(n)&lt;=cn<sup>2</sup>logn, but that did not work.</p>
  
  <p>I got T(n)&lt;=cn<sup>2</sup>logn+n<sup>2</sup>. Then I tried to show that, if T(n)&lt;=c<sub>1</sub>n<sup>2</sup>logn-c<sub>2</sub>n<sup>2</sup>, then it is also O(n<sup>2</sup>logn), but that also didn't work and I got T(n)&lt;=c<sub>1</sub>n<sup>2</sup>log(n/2)-c<sub>2</sub>n<sup>2</sup>+n<sup>2</sup>`. </p>
  
  <p>How can I solve this recurrence?</p>