chap analysis techniques this bookincluding the cost of series of union/find operations (section )the cost of series of splay tree operations (section )and the cost of series of operations on self-organizing lists (section section discusses the topic in more detail summation techniques we begin our study of techniques for finding the closed-form solution to summation by considering the simple example = in section it was proved by induction that this summation has the well-known closed form ( )/ but while induction is good technique for proving that proposed closed-form expression is correcthow do we find candidate closedform expression to test in the first placelet us try to approach this summation from first principlesas though we had never seen it before good place to begin analyzing summation it is to give an estimate of its value for given observe that the biggest term for this summation is nand there are terms being summed up so the total must be less than actuallymost terms are much less than nand the sizes of the terms grows linearly if we were to draw picture with bars for the size of the termstheir heights would form lineand we could enclose them in box units wide and units high it is easy to see from this that closer estimate for the summation is about ( )/ having this estimate in hand helps us when trying to determine an exact closed-form solutionbecause we will hopefully recognize if our proposed solution is badly wrong let us now consider some ways that we might hit upon an exact value for the closed form solution to this summation one particularly clever approach we can take is to observe that we can "pair upthe first and last termsthe second and ( )th termsand so on each pair sums to the number of pairs is / thusthe solution is ( )/ this is prettyand there' no doubt about it being correct the problem is that it is not useful technique for solving many other summations now let us try to do something bit more general we already recognized thatbecause the largest term is and there are termsthe summation is less than if we are luckythe closed form solution is polynomial using that as working assumptionwe can invoke technique called guess-and-test we will guess that the closed-form solution for this summation is polynomial of the form