sec summations and recurrences summations and recurrences most programs contain loop constructs when analyzing running time costs for programs with loopswe need to add up the costs for each time the loop is executed this is an example of summation summations are simply the sum of costs for some function applied to range of parameter values summations are typically written with the following "sigmanotationn (ii= this notation indicates that we are summing the value of (iover some range of (integervalues the parameter to the expression and its initial value are indicated below the symbol herethe notation indicates that the parameter is and that it begins with the value at the top of the symbol is the expression this indicates the maximum value for the parameter thusthis notation means to sum the values of (ias ranges from through this can also be written ( ( ( (np within sentencesigma notation is typeset as ni= (igiven summationyou often wish to replace it with direct equation with the same value as the summation this is known as closed-form solutionand the process of replacing the summation with its closed-form solution is known as solvp ing the summation for examplethe summation ni= is simply the expression " summed times (remember that ranges from to nbecause the sum of is nthe closed-form solution is the following is list of useful summationsalong with their closed-form solutions ( ( ( )( ( = = log xn log ( = = ai for - (