sec recurrence relations + - + = - ( ) + = break the second summation into two partsn- - - + + + + = cancel like termsn + - = = + = again shift ' value in the summationsubstituting for ( ) + = replace the new summation with solution that we already known + + finallyreorganize the equation( ) + recurrence relations recurrence relations are often used to model the cost of recursive functions for examplethe standard mergesort (section takes list of size nsplits it in halfperforms mergesort on each halfand finally merges the two sublists in steps the cost for this can be modeled as ( ( / in other wordsthe cost of the algorithm on input of size is two times the cost for input of size / (due to the two recursive calls to mergesortplus (the time to merge the sublists together againthere are many approaches to solving recurrence relationsand we briefly consider three here the first is an estimation techniqueguess the upper and lower bounds for the recurrenceuse induction to prove the boundsand tighten as required the second approach is to expand the recurrence to convert it to summation and then use summation techniques the third approach is to take advantage