Divide and conquer algorithms often follow a generic pattern: they tackle a problem of size n by recursively solving say a, sub-problems, of size n/b and then combining these answers in O(nd ) time, for some a,b,d > 0. Their running time can therefore be captured by the equation T(n) = aT(n/b) + O(nd ). We studied a closed-form solution to this general recurrence so that we no longer have to solve it explicitly in each new instance. This is the Master Theorem we studied in the class. Can you give the proof that the theorem is correct?